You are in a room with 2N Plaminians and C locked chests. One of the chests contains a treasure. Half of the Plaminians are consecrated, and know which chest contains the treasure. The other Plaminians do not know which chest has the treasure. All of the Plaminians know which ones are consecrated. You do not know which Plaminians are consecrated, or which chest has the treasure.
The Plaminians have agreed that you may ask each one a yes/no question, and they will answer truthfully if they know the answer, and randomly if they do not know.
What sequence of questions will give you the greatest chance of locating the chest with the treasure? For what values of N and C is success guaranteed?
There are problems with the comments I previously gave.
I ran a simulation for asking successive Plaminians. If any at any stage is known to be consecrated, ask that one if a particular one of the chests you hadn't asked about before contains the treasure. But if there's not yet a known consecrated individual, ask anyone who hasn't been asked a question before if a certain individual of unknown consecration status is in fact consecrated.
If, after all have been questioned, none has been identified by a consecrated Plaminian as containing the treasure, a random choice is made among those not identified as not containing the treasure.
10,000 trials are done for each N and C combination.
clearvars
for c=1:20
for n=1:10
succ=0;
for tr=1:10000
asked= false(1,2*n);
cons= zeros(1,2*n);
consecrated=cons;
consecrated(randperm(2*n,n))=1;
chest=zeros(1,c);
treas=randi(c);
chest(treas)=1;
done=false;
while ~done
idx=find(cons==1 & asked==false);
if ~isempty(idx)
idx2=find(chest>-1);
if chest(idx2(1))==1;
succ=succ+1;
done=true;
else
asked(idx(1))=true;
chest(idx2(1))=-1;
end
else
idx=find(asked==false);
if isempty(idx)
if randi(c-sum(chest==-1))==1
succ=succ+1;
end
break
end
idx2=find(cons==0);
idx3=find(idx2~=idx(1));
if ~isempty(idx3)
asked(idx(1))=true;
if consecrated(idx3(1))==0
cons(idx3(1))=-1;
else
cons(idx3(1))=1;
end
else
if randi(c-sum(chest==-1))==1
succ=succ+1;
end
done=true;
end
end
end
end
fprintf('%5d ',succ)
end
fprintf('\n')
end
The number of successful finding of the treasure per 10,000 tries:
N
\ 1 1 1 1 1 1 1 1 1 1
C
1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
2 7528 7576 7502 7561 7491 7501 7529 7620 7487 7452
3 5038 5027 4952 5045 5022 5074 5020 5089 5066 4944
4 3790 3696 3778 3679 3757 3787 3739 3773 3792 3788
5 3053 3068 2955 2917 2952 3062 3067 2901 2992 2964
6 2378 2466 2456 2524 2460 2445 2486 2539 2511 2435
7 2176 2137 2057 2127 2179 2162 2088 2151 2137 2163
8 1895 1828 1850 1929 1856 1888 1882 1846 1928 1911
9 1751 1702 1666 1656 1649 1628 1654 1692 1681 1720
10 1503 1457 1508 1545 1503 1438 1499 1425 1568 1523
11 1396 1323 1330 1352 1365 1345 1406 1367 1414 1340
12 1280 1254 1267 1225 1198 1208 1243 1275 1251 1227
13 1159 1213 1131 1121 1140 1155 1165 1210 1193 1137
14 1085 1028 1059 1073 1082 987 1077 1065 1034 1059
15 961 1044 926 1015 985 959 967 1016 1021 984
16 893 899 920 926 914 892 905 925 895 962
17 891 916 868 873 851 936 891 891 883 829
18 831 794 758 860 834 834 810 834 787 809
19 774 814 791 807 809 796 751 741 833 737
20 737 713 731 786 717 767 766 773 754 759
|
|
Posted by Charlie
on 2024-03-20 13:24:49 |
simulation
