All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Finding the Knight (Posted on 2009-01-06)
An apple seller sells only one apple every day to one of 3 persons(2 are habitual liars and the other is an always truth telling knight).

You have to determine who is the knight by asking each of the 3 persons every day, "Did the apple seller sell you the apple today?"

Find the probability that you can find the knight in exactly n days, where n is a positive integer.

 See The Solution Submitted by Praneeth No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution Comment 1 of 1

On any given day the seller will sell to either one of the liars or the knight. If sold to a liar, the answers will be a yes and two no's. If sold to the knight, the answers will all be yes. So information is gained only on a day when the apple is sold to a liar, in which case the person saying yes is the liar to whom the apple was not sold.

The only way to find the knight is to identify the two liars. This takes at least two days. So the probability sought is the probability that on day n the apple seller will have sold an apple for the first time to a given liar, having previously sold an apple to the other liar.

If we call the liars L1 and L2, this is twice the probability that L1 was sold an apple previously and on this day L2 is sold one for the first time, as it's equally likely to be the other way around.

The probability that L2 had never been sold an apple before this day is (2/3)^(n-1).

Independently, the probability that L2 will be sold an apple on this day is 1/3.

Given that on the previous days L2 was not sold an apple, there are only two possible people to whom apples were sold. So the probability that L1 was in fact sold an apple some time during those days was (1 - 1/2^(n-1)), given that L2 was not sold any.

So, from the preceding four paragraphs, we have factors of 2, (2/3)^(n-1), 1/3 and (1 - 1/2^(n-1)), making the overall probability

2 * (2/3)^(n-1) * 1/3 * (1 - 1/2^(n-1)) = (2/3)^n * (1 - 1/2^(n-1))

That quantity is evaluated in the middle column below, and accumulated in the right hand column.

` 1 0.0000000 0.0000000 2 0.2222222 0.2222222 3 0.2222222 0.4444444 4 0.1728395 0.6172840 5 0.1234568 0.7407407 6 0.0850480 0.8257888 7 0.0576132 0.8834019 8 0.0387136 0.9221155 9 0.0259107 0.948026210 0.0173077 0.965333911 0.0115497 0.976883612 0.0077036 0.984587213 0.0051370 0.989724214 0.0034251 0.993149215 0.0022835 0.995432816 0.0015224 0.996955117 0.0010149 0.997970118 0.0006766 0.998646719 0.0004511 0.999097820 0.0003007 0.999398521 0.0002005 0.999599022 0.0001337 0.999732723 0.0000891 0.999821824 0.0000594 0.999881225 0.0000396 0.999920826 0.0000264 0.999947227 0.0000176 0.999964828 0.0000117 0.999976529 0.0000078 0.999984430 0.0000052 0.999989631 0.0000035 0.999993032 0.0000023 0.999995433 0.0000015 0.999996934 0.0000010 0.999997935 0.0000007 0.999998636 0.0000005 0.999999137 0.0000003 0.999999438 0.0000002 0.999999639 0.0000001 0.999999740 0.0000001 0.999999841 0.0000001 0.999999942 0.0000000 0.999999943 0.0000000 0.999999944 0.0000000 1.000000045 0.0000000 1.0000000`
`DEFDBL A-ZCLSFOR n = 1 TO 45  p = (2 / 3) ^ n * (1 - 1 / 2 ^ (n - 1))  t = t + p  PRINT USING "### #.####### #.#######"; n; p; t`
`NEXT`
`A simulation verifies the reasonableness of the numbers:`
`DIM days(100)FOR trial = 1 TO 10000  day = 0: had1 = 0: had2 = 0  DO    day = day + 1    r = INT(RND(1) * 3 + 1)    SELECT CASE r     CASE 1: had1 = 1     CASE 2: had2 = 1    END SELECT  LOOP UNTIL had1 AND had2  days(day) = days(day) + 1  IF day > max THEN max = dayNEXTFOR i = 1 TO max tot = tot + days(i) PRINT USING "### ##### #####"; i; days(i); totNEXT`
`  1     0     0  2  2223  2223  3  2188  4411  4  1707  6118  5  1319  7437  6   852  8289  7   576  8865  8   391  9256  9   251  9507 10   173  9680 11   106  9786 12    67  9853 13    48  9901 14    32  9933 15    16  9949 16    23  9972 17    11  9983 18     6  9989 19     6  9995 20     2  9997 21     1  9998 22     1  9999 23     0  9999 24     0  9999 25     0  9999 26     1 10000`

 Posted by Charlie on 2009-01-06 16:57:08

 Search: Search body:
Forums (1)