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.
For those not conversant with "knights and liars" please address the category at the home page.
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.9480262
10 0.0173077 0.9653339
11 0.0115497 0.9768836
12 0.0077036 0.9845872
13 0.0051370 0.9897242
14 0.0034251 0.9931492
15 0.0022835 0.9954328
16 0.0015224 0.9969551
17 0.0010149 0.9979701
18 0.0006766 0.9986467
19 0.0004511 0.9990978
20 0.0003007 0.9993985
21 0.0002005 0.9995990
22 0.0001337 0.9997327
23 0.0000891 0.9998218
24 0.0000594 0.9998812
25 0.0000396 0.9999208
26 0.0000264 0.9999472
27 0.0000176 0.9999648
28 0.0000117 0.9999765
29 0.0000078 0.9999844
30 0.0000052 0.9999896
31 0.0000035 0.9999930
32 0.0000023 0.9999954
33 0.0000015 0.9999969
34 0.0000010 0.9999979
35 0.0000007 0.9999986
36 0.0000005 0.9999991
37 0.0000003 0.9999994
38 0.0000002 0.9999996
39 0.0000001 0.9999997
40 0.0000001 0.9999998
41 0.0000001 0.9999999
42 0.0000000 0.9999999
43 0.0000000 0.9999999
44 0.0000000 1.0000000
45 0.0000000 1.0000000
DEFDBL A-Z
CLS
FOR 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 = day
NEXT
FOR i = 1 TO max
tot = tot + days(i)
PRINT USING "### ##### #####"; i; days(i); tot
NEXT
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 |
solution
