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

Home > Probability
Finding the Knight (Posted on 2009-01-06) Difficulty: 3 of 5
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.

See The Solution Submitted by Praneeth    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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.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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information