Maurice Kelly lives in a very big house in the country. Outside his house he has a lot of big gardens. In one of them he has ten beautiful red flowers. These flowers are arranged in a 2x5 rectangular grid as follows:
+--+--+--+--+--+
|F |F |F |F |F |
+--+--+--+--+--+
|F |F |F |F |F |
+--+--+--+--+--+
The flowers had always lived in peace in this garden, until the day he allowed his stupid dog to go into the garden. This dog has only one goal in his life: it wants to eat as many red flowers as possible.
But the flowers are not normal flowers. They can think, and are able to talk to each other. And they now need a good plan to be able to save as many flower-lives as possible.
Each of the red flowers has the option to develop poison. If the dog is so unlucky to eat a poisonous flower it will surely die, and thus cannot eat any more flowers. So, when the dog arrives in the garden, it will start to eat flowers in random order as long as it is alive. Since the dog cannot see which flowers contain poison, the dog will certainly eat all of them.
But how many flowers should make poison? Unfortunately, its not possible to save every flower. The problem is that the creation of poison is a hard task to do. When one flower develops poison, it will use all the food and water that is in the ground around it. This will kill the flower to the left, if that position is not vacant.
The flowers are not sure about how many flowers should make poison. They think that maybe only the two flowers to the very left do it, but they are not sure. Therefore, they need your help.
(1) What is the maximum number of flowers that without risk can be guaranteed to survive?
(2) The flowers are risk neutral, and want to minimize the expected number of dead flowers. How many flowers should make poison to afford this?
(1)
Five could without risk be guaranteed survival by making 6 poisonous, thereby killing 4 and allowing 1 of the remaining 6, all poisonous, to be eaten.
(2)
clc
for n=1:6
dead=max([0,n-2]);
alive=10-dead;
t=0; exVal=0;
for killed = 1:alive
prob=1;
for i=1:killed-1
prob=prob*(alive-n-i+1)/(alive-i+1);
end
prob=prob*n/(alive-killed+1);
t=t+prob;
exVal=exVal+killed*prob;
fprintf('%2d %3d %14.12f\n',n, killed, abs(prob));
end
fprintf('%2d %5.3f %10.7f\n\n',n, t,exVal+dead);
end
finds
# # probability of
poisonous eaten this # eaten
1 1 0.100000000000
1 2 0.100000000000
1 3 0.100000000000
1 4 0.100000000000
1 5 0.100000000000
1 6 0.100000000000
1 7 0.100000000000
1 8 0.100000000000
1 9 0.100000000000
1 10 0.100000000000
1 1.000 5.5000000
2 1 0.200000000000
2 2 0.177777777778
2 3 0.155555555556
2 4 0.133333333333
2 5 0.111111111111
2 6 0.088888888889
2 7 0.066666666667
2 8 0.044444444444
2 9 0.022222222222
2 10 0.000000000000
2 1.000 3.6666667
3 1 0.333333333333
3 2 0.250000000000
3 3 0.178571428571
3 4 0.119047619048
3 5 0.071428571429
3 6 0.035714285714
3 7 0.011904761905
3 8 0.000000000000
3 9 0.000000000000
3 1.000 3.5000000
4 1 0.500000000000
4 2 0.285714285714
4 3 0.142857142857
4 4 0.057142857143
4 5 0.014285714286
4 6 0.000000000000
4 7 0.000000000000
4 8 0.000000000000
4 1.000 3.8000000
5 1 0.714285714286
5 2 0.238095238095
5 3 0.047619047619
5 4 0.000000000000
5 5 0.000000000000
5 6 0.000000000000
5 7 0.000000000000
5 1.000 4.3333333
6 1 1.000000000000
6 2 0.000000000000
6 3 0.000000000000
6 4 0.000000000000
6 5 0.000000000000
6 6 0.000000000000
6 1.000 5.0000000
The last line in each group verifies the total of the individual probabilities, as a sanity check, and then the expected value of the total of the number of flowers eaten and the number of sacrificed flowers.
The lowest of these expected losses is 3.5, when 3 of the flowers decide to produce poison. This includes the inevitably sacrifice single flower that was necessary as one of the poisonous flowers had to be positioned away from the eastern edge. In addition an expected 2.5 flowers would be eaten by the dog.
Programming note: The abs() function surrounding prob in the fprintf is for cosmetic purposes and affected only
changing
-0.000000000000
to
0.000000000000
|
|
Posted by Charlie
on 2022-08-29 10:45:51 |
solution
