consider the test case in problem statement. Will the kid really wait for 0.6875 sec, when 2 kids are riding merry-go round?? Mb this value should be 0.625 = 5/8???

Edited by author 30.01.2011 13:22

The test case is correct.

it seems to be wrong at all
there are 6 posibilities in this hypothesis (there are 2 childrens) they are:
1100  -  2
1010  -  1
1001  -  1
0110  -  0
0101  -  0
0011  -  0
so, the posibility must be 2*1/6 + 1*1/6 + 1*1/6 = 0.66666667
isn't it right??

Edited by author 30.01.2011 14:15

_________________________________________


test case is right. there are sub-hypothesis with different posibilities

Edited by author 30.01.2011 14:54

Seems like the possibility of each case isn't equal to 1/6, some of the cases have more then 1/6, others - less.

How did you do that??



Edited by author 30.01.2011 16:45

Yes, test case is correct.

Look:
1010 you can get from 1000 and 0010, p = 2/16
0101 you can get from 0100 and 0001, p = 2/16
But:
1100 you can get from 1000 (2 times!) and 0100, p = 3/16
0110 you can get from 0100 (2 times!) and 0010, p = 3/16
0011 you can get from 0010 (2 times!) and 0001, p = 3/16
1001 you can get from 0001 (2 times!) and 1000, p = 3/16

Thus, we get:
p(1100) = 3/16, p(1001) = 3/16, p(1010) = 2/16
And the answer is:
(3/16)*2 + (3/16)*1 + (2/16)*1 = 11/16 = 0.6875

Nice problem!

Can you please explain why for
1010 -> p = 2/16
but 1100 -> p = 3/16
How does 1000 come 2 times in this case ?

1000 -> 1010 if start position = 3
0010 -> 1010 if start position = 1
(2 times)

1000 -> 1100 if start position = 1
1000 -> 1100 if start position = 2
0100 -> 1100 if start position = 1
(3 times)

"And the answer is:
... + (3/16)*1 + = 11/16 = 0.6875"

Could you explain why (3/16)*1 but not (3/16)*2,
though max waiting time is 2 (1001 - if we stand at place 1)??

Mask Time
0011  0
0101  0
0110  0
1001  1
1010  1
1100  2

Sorry, but why 11/16? Why not 3/16 + 3/16 + 3/16 + 3/16 + 2/16 + 2/16 = 16/16

I understand that

4/16 == 0.250000 ======

1000 1/16
0100 1/16
0010 1/16
0001 1/16


24/16 == 1.500000 =====

1110 (3+2+1=6)/16
1101 (3+2+1=6)/16
1011 (3+2+1=6)/16
0111 (3+2+1=6)/16

But why 11/16?

Just some basic knowledge from probability theory...

3/16 + 3/16 + 3/16 + 3/16 + 2/16 + 2/16 = 16/16
It's a normalization requirement (p1 + p2 + ... + pn = 1).

And mean MX = p1*x1 + p2*x2 + ... + pn*xn,
where pi - probabilities, xi - values.

So we have (3/16)*2 + (3/16)*1 + (2/16)*1 + (3/16)*0 + (3/16)*0 + (2/16)*0 = 11/16.

In Buffon problem there are 3 different
solution and all of them are right.
Answer depend on exact understanding
all conditions of random experiment.
I think that this problem also safer from too
brief explanation.

i've used this explanation of test:
let it be some kind of class:
1100 0110 0011 1001 - first class, maked by all rotations of first one, and it's representative would be a smallest, so:
[1100] : {1100 0110 0011 1001}
[1010] : {1010 0101 1010 0101} - second class, we have repeatings here, but it must be always n rotations
so, we could get [1100] from:
1000 - waiting 1 sec,
0001 - not waiting
0100 - not waiting
all of them is class [1000] which comes from [0000] with 100% posibility
so posibilities of [1000] would be:
1000 - 100% * 1 / 4
0001 - 100% * 1 / 4
0100 - 100% * 1 / 4
so posibility of getting in class [1100] is 3/4
[1010] we could get from:
0010 which posibility is 100% * 1 / 4
so our classes have such posibilities:
[1100] - 3 / 4
[1010] - 1 / 4

[1100]:
mask sec posibility
1100 2 1/4*3/4
0110 0 1/4*3/4
0011 0 1/4*3/4
1001 1 1/4*3/4

[1010]:
mask sec posibility
1010 1 1/4*1/4
0101 0 1/4*1/4
1010 1 1/4*1/4   - it repeats, but it is another rotation, 3rd
0101 0 1/4*1/4   - 4th
so, our result would be:
MX = 2 * 3/16 + 1 * 3/16 + 1 * 1/16 + 1 * 1/16 = 11/16 = 0.6875
like in our test case

i've used DP for this problem, just filling array of posibilities in recursive with saving way, rotating my current mask, and looking from where i could go here

What answer for n=20?