Problem 469

[jochenkeutel]

Hello,
can someone confirm that E(10) = 228/420?

Thanks, Jochen.

[domsj]

That value for E(10) is not correct

[cornica]

I keep getting E(10) = 14/25. Could anyone confirm that to be right (or wrong)?

[domsj]

That ain't correct either.
I wouldn't mind giving E(10) but I supposed that's not allowed...?

[mpiotte]

...
I wouldn't mind giving E(10) but I supposed that's not allowed...?

Giving away additional test values is very premature. This problem was released less than a week ago. If the development team had wanted additional test values, they would be part of the official question.

[pobrien89]

The question is a little ambiguous...

When there aren't any suitable chairs left, the fraction C of empty chairs is determined.

This should really be:

When there aren't any suitable chairs left, the fraction C, the average of empty chairs is determined.

Slight wording change but makes a huge difference when calculating C.

@admin, perhaps a change in the wording of the question is needed?

[mpiotte]

There is no ambiguity. Read the next line:

We also define E(N) as the expected value of C.

C is the fraction for one given experiment. The "expected value" is the average over all possible experiments.
See http://en.wikipedia.org/wiki/Expected_value.

[pobrien89]

Ah yes, was not familiar with the term 'expected value'.

Thanks for the clarification & link

[ffff0]

I also belive that E(10)=14/25.

There are 360 ways of sitting for 4 knights:

Code: Select all

**1**2*3*4
**1**2*4*3
**1**3*2*4
**1**3*4*2
**1**4*2*3
**1**4*3*2
**1*2**3*4
**1*2**4*3
**1*2*3**4
**1*2*4**3
**1*3**2*4
**1*3**4*2
**1*3*2**4
**1*3*4**2
**1*4**2*3
**1*4**3*2
**1*4*2**3
**1*4*3**2
**2**1*3*4
**2**1*4*3
**2**3*1*4
**2**3*4*1
**2**4*1*3
**2**4*3*1
**2*1**3*4
**2*1**4*3
**2*1*3**4
**2*1*4**3
**2*3**1*4
**2*3**4*1
**2*3*1**4
**2*3*4**1
**2*4**1*3
**2*4**3*1
**2*4*1**3
**2*4*3**1
**3**1*2*4
**3**1*4*2
**3**2*1*4
**3**2*4*1
**3**4*1*2
**3**4*2*1
**3*1**2*4
**3*1**4*2
**3*1*2**4
**3*1*4**2
**3*2**1*4
**3*2**4*1
**3*2*1**4
**3*2*4**1
**3*4**1*2
**3*4**2*1
**3*4*1**2
**3*4*2**1
**4**1*2*3
**4**1*3*2
**4**2*1*3
**4**2*3*1
**4**3*1*2
**4**3*2*1
**4*1**2*3
**4*1**3*2
**4*1*2**3
**4*1*3**2
**4*2**1*3
**4*2**3*1
**4*2*1**3
**4*2*3**1
**4*3**1*2
**4*3**2*1
**4*3*1**2
**4*3*2**1
*1**2**3*4
*1**2**4*3
*1**2*3**4
*1**2*3*4*
*1**2*4**3
*1**2*4*3*
*1**3**2*4
*1**3**4*2
*1**3*2**4
*1**3*2*4*
*1**3*4**2
*1**3*4*2*
*1**4**2*3
*1**4**3*2
*1**4*2**3
*1**4*2*3*
*1**4*3**2
*1**4*3*2*
*1*2**3**4
*1*2**3*4*
*1*2**4**3
*1*2**4*3*
*1*2*3**4*
*1*2*4**3*
*1*3**2**4
*1*3**2*4*
*1*3**4**2
*1*3**4*2*
*1*3*2**4*
*1*3*4**2*
*1*4**2**3
*1*4**2*3*
*1*4**3**2
*1*4**3*2*
*1*4*2**3*
*1*4*3**2*
*2**1**3*4
*2**1**4*3
*2**1*3**4
*2**1*3*4*
*2**1*4**3
*2**1*4*3*
*2**3**1*4
*2**3**4*1
*2**3*1**4
*2**3*1*4*
*2**3*4**1
*2**3*4*1*
*2**4**1*3
*2**4**3*1
*2**4*1**3
*2**4*1*3*
*2**4*3**1
*2**4*3*1*
*2*1**3**4
*2*1**3*4*
*2*1**4**3
*2*1**4*3*
*2*1*3**4*
*2*1*4**3*
*2*3**1**4
*2*3**1*4*
*2*3**4**1
*2*3**4*1*
*2*3*1**4*
*2*3*4**1*
*2*4**1**3
*2*4**1*3*
*2*4**3**1
*2*4**3*1*
*2*4*1**3*
*2*4*3**1*
*3**1**2*4
*3**1**4*2
*3**1*2**4
*3**1*2*4*
*3**1*4**2
*3**1*4*2*
*3**2**1*4
*3**2**4*1
*3**2*1**4
*3**2*1*4*
*3**2*4**1
*3**2*4*1*
*3**4**1*2
*3**4**2*1
*3**4*1**2
*3**4*1*2*
*3**4*2**1
*3**4*2*1*
*3*1**2**4
*3*1**2*4*
*3*1**4**2
*3*1**4*2*
*3*1*2**4*
*3*1*4**2*
*3*2**1**4
*3*2**1*4*
*3*2**4**1
*3*2**4*1*
*3*2*1**4*
*3*2*4**1*
*3*4**1**2
*3*4**1*2*
*3*4**2**1
*3*4**2*1*
*3*4*1**2*
*3*4*2**1*
*4**1**2*3
*4**1**3*2
*4**1*2**3
*4**1*2*3*
*4**1*3**2
*4**1*3*2*
*4**2**1*3
*4**2**3*1
*4**2*1**3
*4**2*1*3*
*4**2*3**1
*4**2*3*1*
*4**3**1*2
*4**3**2*1
*4**3*1**2
*4**3*1*2*
*4**3*2**1
*4**3*2*1*
*4*1**2**3
*4*1**2*3*
*4*1**3**2
*4*1**3*2*
*4*1*2**3*
*4*1*3**2*
*4*2**1**3
*4*2**1*3*
*4*2**3**1
*4*2**3*1*
*4*2*1**3*
*4*2*3**1*
*4*3**1**2
*4*3**1*2*
*4*3**2**1
*4*3**2*1*
*4*3*1**2*
*4*3*2**1*
1**2**3*4*
1**2**4*3*
1**2*3**4*
1**2*3*4**
1**2*4**3*
1**2*4*3**
1**3**2*4*
1**3**4*2*
1**3*2**4*
1**3*2*4**
1**3*4**2*
1**3*4*2**
1**4**2*3*
1**4**3*2*
1**4*2**3*
1**4*2*3**
1**4*3**2*
1**4*3*2**
1*2**3**4*
1*2**3*4**
1*2**4**3*
1*2**4*3**
1*2*3**4**
1*2*4**3**
1*3**2**4*
1*3**2*4**
1*3**4**2*
1*3**4*2**
1*3*2**4**
1*3*4**2**
1*4**2**3*
1*4**2*3**
1*4**3**2*
1*4**3*2**
1*4*2**3**
1*4*3**2**
2**1**3*4*
2**1**4*3*
2**1*3**4*
2**1*3*4**
2**1*4**3*
2**1*4*3**
2**3**1*4*
2**3**4*1*
2**3*1**4*
2**3*1*4**
2**3*4**1*
2**3*4*1**
2**4**1*3*
2**4**3*1*
2**4*1**3*
2**4*1*3**
2**4*3**1*
2**4*3*1**
2*1**3**4*
2*1**3*4**
2*1**4**3*
2*1**4*3**
2*1*3**4**
2*1*4**3**
2*3**1**4*
2*3**1*4**
2*3**4**1*
2*3**4*1**
2*3*1**4**
2*3*4**1**
2*4**1**3*
2*4**1*3**
2*4**3**1*
2*4**3*1**
2*4*1**3**
2*4*3**1**
3**1**2*4*
3**1**4*2*
3**1*2**4*
3**1*2*4**
3**1*4**2*
3**1*4*2**
3**2**1*4*
3**2**4*1*
3**2*1**4*
3**2*1*4**
3**2*4**1*
3**2*4*1**
3**4**1*2*
3**4**2*1*
3**4*1**2*
3**4*1*2**
3**4*2**1*
3**4*2*1**
3*1**2**4*
3*1**2*4**
3*1**4**2*
3*1**4*2**
3*1*2**4**
3*1*4**2**
3*2**1**4*
3*2**1*4**
3*2**4**1*
3*2**4*1**
3*2*1**4**
3*2*4**1**
3*4**1**2*
3*4**1*2**
3*4**2**1*
3*4**2*1**
3*4*1**2**
3*4*2**1**
4**1**2*3*
4**1**3*2*
4**1*2**3*
4**1*2*3**
4**1*3**2*
4**1*3*2**
4**2**1*3*
4**2**3*1*
4**2*1**3*
4**2*1*3**
4**2*3**1*
4**2*3*1**
4**3**1*2*
4**3**2*1*
4**3*1**2*
4**3*1*2**
4**3*2**1*
4**3*2*1**
4*1**2**3*
4*1**2*3**
4*1**3**2*
4*1**3*2**
4*1*2**3**
4*1*3**2**
4*2**1**3*
4*2**1*3**
4*2**3**1*
4*2**3*1**
4*2*1**3**
4*2*3**1**
4*3**1**2*
4*3**1*2**
4*3**2**1*
4*3**2*1**
4*3*1**2**
4*3*2**1**

And 240 ways of sitting for 5 knights:

Code: Select all

*1*2*3*4*5
*1*2*3*5*4
*1*2*4*3*5
*1*2*4*5*3
*1*2*5*3*4
*1*2*5*4*3
*1*3*2*4*5
*1*3*2*5*4
*1*3*4*2*5
*1*3*4*5*2
*1*3*5*2*4
*1*3*5*4*2
*1*4*2*3*5
*1*4*2*5*3
*1*4*3*2*5
*1*4*3*5*2
*1*4*5*2*3
*1*4*5*3*2
*1*5*2*3*4
*1*5*2*4*3
*1*5*3*2*4
*1*5*3*4*2
*1*5*4*2*3
*1*5*4*3*2
*2*1*3*4*5
*2*1*3*5*4
*2*1*4*3*5
*2*1*4*5*3
*2*1*5*3*4
*2*1*5*4*3
*2*3*1*4*5
*2*3*1*5*4
*2*3*4*1*5
*2*3*4*5*1
*2*3*5*1*4
*2*3*5*4*1
*2*4*1*3*5
*2*4*1*5*3
*2*4*3*1*5
*2*4*3*5*1
*2*4*5*1*3
*2*4*5*3*1
*2*5*1*3*4
*2*5*1*4*3
*2*5*3*1*4
*2*5*3*4*1
*2*5*4*1*3
*2*5*4*3*1
*3*1*2*4*5
*3*1*2*5*4
*3*1*4*2*5
*3*1*4*5*2
*3*1*5*2*4
*3*1*5*4*2
*3*2*1*4*5
*3*2*1*5*4
*3*2*4*1*5
*3*2*4*5*1
*3*2*5*1*4
*3*2*5*4*1
*3*4*1*2*5
*3*4*1*5*2
*3*4*2*1*5
*3*4*2*5*1
*3*4*5*1*2
*3*4*5*2*1
*3*5*1*2*4
*3*5*1*4*2
*3*5*2*1*4
*3*5*2*4*1
*3*5*4*1*2
*3*5*4*2*1
*4*1*2*3*5
*4*1*2*5*3
*4*1*3*2*5
*4*1*3*5*2
*4*1*5*2*3
*4*1*5*3*2
*4*2*1*3*5
*4*2*1*5*3
*4*2*3*1*5
*4*2*3*5*1
*4*2*5*1*3
*4*2*5*3*1
*4*3*1*2*5
*4*3*1*5*2
*4*3*2*1*5
*4*3*2*5*1
*4*3*5*1*2
*4*3*5*2*1
*4*5*1*2*3
*4*5*1*3*2
*4*5*2*1*3
*4*5*2*3*1
*4*5*3*1*2
*4*5*3*2*1
*5*1*2*3*4
*5*1*2*4*3
*5*1*3*2*4
*5*1*3*4*2
*5*1*4*2*3
*5*1*4*3*2
*5*2*1*3*4
*5*2*1*4*3
*5*2*3*1*4
*5*2*3*4*1
*5*2*4*1*3
*5*2*4*3*1
*5*3*1*2*4
*5*3*1*4*2
*5*3*2*1*4
*5*3*2*4*1
*5*3*4*1*2
*5*3*4*2*1
*5*4*1*2*3
*5*4*1*3*2
*5*4*2*1*3
*5*4*2*3*1
*5*4*3*1*2
*5*4*3*2*1
1*2*3*4*5*
1*2*3*5*4*
1*2*4*3*5*
1*2*4*5*3*
1*2*5*3*4*
1*2*5*4*3*
1*3*2*4*5*
1*3*2*5*4*
1*3*4*2*5*
1*3*4*5*2*
1*3*5*2*4*
1*3*5*4*2*
1*4*2*3*5*
1*4*2*5*3*
1*4*3*2*5*
1*4*3*5*2*
1*4*5*2*3*
1*4*5*3*2*
1*5*2*3*4*
1*5*2*4*3*
1*5*3*2*4*
1*5*3*4*2*
1*5*4*2*3*
1*5*4*3*2*
2*1*3*4*5*
2*1*3*5*4*
2*1*4*3*5*
2*1*4*5*3*
2*1*5*3*4*
2*1*5*4*3*
2*3*1*4*5*
2*3*1*5*4*
2*3*4*1*5*
2*3*4*5*1*
2*3*5*1*4*
2*3*5*4*1*
2*4*1*3*5*
2*4*1*5*3*
2*4*3*1*5*
2*4*3*5*1*
2*4*5*1*3*
2*4*5*3*1*
2*5*1*3*4*
2*5*1*4*3*
2*5*3*1*4*
2*5*3*4*1*
2*5*4*1*3*
2*5*4*3*1*
3*1*2*4*5*
3*1*2*5*4*
3*1*4*2*5*
3*1*4*5*2*
3*1*5*2*4*
3*1*5*4*2*
3*2*1*4*5*
3*2*1*5*4*
3*2*4*1*5*
3*2*4*5*1*
3*2*5*1*4*
3*2*5*4*1*
3*4*1*2*5*
3*4*1*5*2*
3*4*2*1*5*
3*4*2*5*1*
3*4*5*1*2*
3*4*5*2*1*
3*5*1*2*4*
3*5*1*4*2*
3*5*2*1*4*
3*5*2*4*1*
3*5*4*1*2*
3*5*4*2*1*
4*1*2*3*5*
4*1*2*5*3*
4*1*3*2*5*
4*1*3*5*2*
4*1*5*2*3*
4*1*5*3*2*
4*2*1*3*5*
4*2*1*5*3*
4*2*3*1*5*
4*2*3*5*1*
4*2*5*1*3*
4*2*5*3*1*
4*3*1*2*5*
4*3*1*5*2*
4*3*2*1*5*
4*3*2*5*1*
4*3*5*1*2*
4*3*5*2*1*
4*5*1*2*3*
4*5*1*3*2*
4*5*2*1*3*
4*5*2*3*1*
4*5*3*1*2*
4*5*3*2*1*
5*1*2*3*4*
5*1*2*4*3*
5*1*3*2*4*
5*1*3*4*2*
5*1*4*2*3*
5*1*4*3*2*
5*2*1*3*4*
5*2*1*4*3*
5*2*3*1*4*
5*2*3*4*1*
5*2*4*1*3*
5*2*4*3*1*
5*3*1*2*4*
5*3*1*4*2*
5*3*2*1*4*
5*3*2*4*1*
5*3*4*1*2*
5*3*4*2*1*
5*4*1*2*3*
5*4*1*3*2*
5*4*2*1*3*
5*4*2*3*1*
5*4*3*1*2*
5*4*3*2*1*

So E(10)=(360*0.6+240*0.5)/600=336/600=14/25.

Where I am wrong?

[Moonypoony]

Did you take in consideration that the table is round?
Use pen and paper, it takes just a few minutes to get the 10 chairs case.

[ffff0]

Yes. That's why, for example, solution 1*2**3*4*5 is not possible.

Actually, I've wrote a program that make brute force for 10:

[Brute force code removed]

[Moonypoony]

There is something wrong, but my mathematical knowledge is not sufficient enough to point it out.
I think it's because not all seating patterns are equal as likely.
Let's say you start with 1 knight, place doesn't matter as the table is round. There are 7 possibilities left, of wich 3 directly lead to a solution with 6 empty seats (3/7*6/10). Continue with the other possibilities.
Doing this by pen and paper should give you the right fraction of empty chairs.
I think I found a pattern in the sequence, but this gives me the wrong answer

[mpiotte]

I also belive that E(10)=14/25.
...
So E(10)=(360*0.6+240*0.5)/600=336/600=14/25.
Where I am wrong?

Moonypoony is correct:

... I think it's because not all seating patterns are equal as likely...

I want to elaborate on this since it appears to be a common mistake, related to the understanding of the question.

Knights enter one by one, and select a chair at random amongst the available ones, i.e. the unoccupied chairs not adjacent to an occupied chair. This implies that the probability of selecting any of the available chair is the same, i.e 1/number_or_available_chairs, for a given knight selecting a chair. Furthermore, the number of available chairs a knight has depends on the choices made by the previous knights. This is different from making the each final position equiprobable.

Let's take the example with 10 chairs, numbered from #1 to #10. Knight #1 has the choice of 10 chairs, so the probability of knight #1 sitting on chair #1 is 1/10. Enters knight #2 which has a choice of 7 chairs (#3 to #9). The probability of knight #2 sitting on chair #3 (knowing knight #1 is on chair #1) is 1/7. Thus the probability of knights #1 and #2 sitting respectively on chairs #1 and #3 is 1/70. According to ffff0 tables, this leads to 12 valid final positions.

The probability of knight #1 and #2 sitting on chairs #1 and #4 respectively is also 1/70. However this leads to only 6 valid final positions according to the same tables. Since these 6 positions together have the same aggregate weight (1/70) as the 12 from the first configuration, they can't all have the same probability. On average, the final positions derived from #1+#4 have higher weights than final positions derived from #1+#3.

@fff0 Code is not permitted on this forum, please remove your code sample.

[outsidepasser]

Would it be inappropriate for me to ask if I have the correct value for E(10) in this forum?

[mpiotte]

Would it be inappropriate for me to ask if I have the correct value for E(10) in this forum?

Send me a private message with your value.

[CromeXza]

Am I correct in saying that there is no-one has solved this?

I'm wondering if I am reading the stats correctly?
469 0 59 (0.011%) as of 2015-09-08

Would be helpful to have the solution for E(20) to debug the code.

[nicolas.patrois]

No, it means that no one solved exactly 469 puzzles.

[swordys]

Can i send value for E(10) to one of the moderators for confirmation?

[Tron-X]

I haven't solved the problem yet, but I did calculate that this table would have to be at least 15 light-years across! And at one knight sitting at the table per second, it would take approximately the current age of the universe to fill the table, depending on the actual value of C. I guess I'm not solving this problem using simulation.

[v6ph1]

So your idea for solution is not as efficient as needed for the solution...