Project Euler Forum

Posted: **Mon Apr 28, 2014 1:56 pm**

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

Thanks, Jochen.

Posted: **Mon Apr 28, 2014 3:44 pm**

That value for E(10) is not correct

Posted: **Mon Apr 28, 2014 5:26 pm**

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

Posted: **Mon Apr 28, 2014 5:31 pm**

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

Posted: **Mon Apr 28, 2014 5:49 pm**

domsj wrote:...
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.

Posted: **Tue Apr 29, 2014 1:46 pm**

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?

Posted: **Tue Apr 29, 2014 2:11 pm**

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.

Posted: **Tue Apr 29, 2014 4:48 pm**

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

Thanks for the clarification & link

Posted: **Wed Apr 30, 2014 12:49 pm**

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?

Posted: **Wed Apr 30, 2014 2:05 pm**

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.

Posted: **Wed Apr 30, 2014 2:39 pm**

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]

Posted: **Wed Apr 30, 2014 3:33 pm**

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

Posted: **Thu May 01, 2014 12:22 am**

ffff0 wrote: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:

Moonypoony wrote:... 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.

Posted: **Mon May 19, 2014 6:54 pm**

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

Posted: **Mon May 19, 2014 7:36 pm**

outsidepasser wrote: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.

Posted: **Tue Sep 08, 2015 6:37 pm**

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.

Posted: **Tue Sep 08, 2015 7:01 pm**

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

Posted: **Tue Jul 26, 2016 5:17 pm**

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

Posted: **Tue Nov 21, 2017 5:38 am**

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.

Posted: **Tue Nov 21, 2017 6:59 pm**

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

Project Euler Forum

Problem 469

Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469

Re: Problem 469