1. Each of 2004 boxes contains one pebble. Some of pebbles are white and the total number of them is even. It is allowed to chose any two boxes and ask questions whether there is a white ball (at least one) among of chosen two. Find the minimal number of questions that allow to determine two boxes which contain white pebbles.
Solution. Answer: 4005.
Let us numerate boxes (and pebbles in them) by the numbers from 1 to 2004. Let pair (i, j) denote a question. Show, that 4005 questions is enough. Really, consider the following sequence of the questions: (1, 2), (1, 3), . . . , (1, 2004), (2, 3), (2, 4), . . . , (2, 2004). If all the answers are positive then first and second pebbles are white. (If first pebble is, say, black, then pebbles from 2 to 2004 are white and the total number of white pebbles is odd. Contradiction). If one of the answers is negative (say on (1, k) question), then pebble number 1 is black. Therefore, pebble j is white if on questions (1, j) the answer was positive. Let us prove, that 4005 is the minimal number. Assume, that there is a procedure which allows to determine two white pebbles for the lesser number of questions. Let to answer positively on all the questions.
Then after 4004 questions (as maximum) one is able to determine two boxes, say m and n with white pebbles. Note, that one of the questions either (m,i) or (n,i) is unanswered (since the total number of such questions is 4005 ). Let it be (m, k) . Let us place into m and k boxes black pebbles. Then all the answers stay unchanged: however, box m contains black pebble.
2. A monkey has two coconuts. It is fooling around by throwing coconut down from the balconies of M-storey building. The monkey wants to know the lowest floor when coconut is broken. What is the minimal number of attempts needed to establish that fact, if
(a) M = 15.
(b) M is arbitrary.
Solution.
Let us note that if the monkey has one coconut and the building is M = k storey high, then the number of attempts needed equals k. Also, in case of k attempts permitted, the maximal high of the building is k.
Consider the case of two coconuts. Let us fix number k, attempts permitted and find the maximal hight of the building when the answer on experiment is guaranteed. With two coconuts monkey starts from the k-th floor (if coconut is broken, it still has k − 1 attempts to investigate floors from the first to k − 1 to get the answer). If coconut is not broken, then monkey spends it second attempt, going up k − 1 floors (it is on (2k − 1)-th floor now) to continue its experiment. Again, if coconut is broken, then k−2 attempts is enough to answer the question, otherwise the monkey goes up k−2 floors. So, the maximal high of the building in case of k attempts permitted is k +(k −1)+(k −2)+· · ·+1 = k(k −1)/2. So, in order to evaluate the minimal numbers of attempts given the M is the high of the building, we should find the minimal k which satisfies inequality k(k − 1)/2 ≥ M
3. There are N trenches in a row. A soldier is hiding in one of them. A gunman shots at any particular trench, and kills the soldier if he is there. After each shot the soldier (if alive) runs to an adjacent trench. Is there a strategy for the gunman that ensures the kill after the number of shots?
(a) N = 2004.
(b) N = isarbitrary.
Answer: yes.
Solution. (i) Consider the case when N = 2k is even. Strategy: Gunman shots in sequence from number 1, 2, . . . , 2k, 2k − 1, 2k − 2, . . . , 1. Let us assume, that the soldier is hiding in a trench with odd number. Note, that after any odd number of shots the soldier be in even numbered trench, while after even number of shots he be in odd numbered trench. Let us verify, that the above strategy works. Gunman shots at trench numbered 1. Let us assume, that the soldier was not there, otherwise he is killed. After the first shot the soldier would be in an even numbered trench. The gunman shots at trench numbered 2. Assuming, that soldier was not there, after the shot he can occupy any odd numbered trench, except number 1. The gunman shots at trench numbered 3. Assuming, that soldier was not there, after the shot he can be in any even numbered trench, except 2. The gunman shots at trench numbered 4. Assuming that soldier was not there, after the shot he can be in any odd numbered trench, except number 3 and 1 (to run to number 3 he needs to be in trenches 4 or 2 prior to it, which is impossible). And so on. To a moment the gunman shots at 2k trench, he kills the soldier for sure unless our assumption was wrong and the soldier was hiding initially in an even numbered trench. So, after the gunman shot, we learn, that the soldier was not there, so prior to that he could occupy an any even numbered trench, except 2k. Next shot persuades us he is not in (2k − 1) trench, but in another trench odd numbered. The shot at (2k − 2) persuade us he was not in (2k − 3) prior to it. . . And so on.
4. 11 coins identical in appearance are arranged in a row. Among them there are 3 counterfeits, with the same weight, heavier than the real ones, and all three of them are placed next to each other. Using a simple balance find the minimal number of weighings that allow to determine all counterfeit coins. The simple balance shows whether both sides of the balance are at equilibrium or one side is heavier/lighter.
Solution.
Show that it could be done in two weighings.
Let us numerate the coins from 1 to 11. Let us start from weighing
1. (1,2,3) ? (9,10,11).
- (a) In case of equality (1, 2, 3) = (9, 10, 11) counterfeits are among (4,5,6,7,8) with 6 be counterfeit for sure. Then 2. 5 ? 7. In case of 5=7 counterfeits are (5,6,7); if 5 > 7 then 7 is a real one and counterfeits are (4,5,6). If 5 < 7 then counterfeits are (6,7,8).
- (b) If (1, 2, 3) > (9, 10, 11) then counterfeits are among (1,2,3,4,5) with 3 be counterfeit for sure. Then 2. 2 ? 4. In case of 2=4 counterfeits are (2,3,4); if 2 > 4 then 4 is a real one and counterfeits are (1,2,3). If 2 < 4 then counterfeits are (3,4,5).
- (c) (1, 2, 3) < (9, 10, 11) is considered in the similar way.
One weighing in not enough to determine counterfeit coins.
7:13 PM
Muhammad Yusuf
, Posted in
