Sunday, April 12, 2015
Sunday, April 5, 2015
Chameleons
On an island live 13 purple, 15 yellow and 17 maroon chameleons. When two chameleons of different colors meet, they both change into the third color. Is there a sequence of pairwise meetings after which all chameleons have the same color?
Let <p, y, m> denote a population of p purple, y yellow and m maroon chameleons. Can population <13, 15, 17> can be transformed into <45, 0, 0> or <0, 45, 0> or <0, 0, 45> through a series of pairwise meetings? Define function X(p, y, m) = (0p + 1y + 2m) mod 3. An interesting property of X is that its value does not change after any pairwise meeting because X(p, y, m) = X(p-1, y-1, m+2) = X(p-1, y+2, m-1) = X(p+2, y-1, m-1). Now X(13, 15, 17) equals 1. However, X(45, 0, 0) = X(0, 45, 0) = X(0, 0, 45) = 0. This means that there is no sequence of pairwise meetings after which all chameleons will have identical color.
Let <p, y, m> denote a population of p purple, y yellow and m maroon chameleons. Can population <13, 15, 17> can be transformed into <45, 0, 0> or <0, 45, 0> or <0, 0, 45> through a series of pairwise meetings? Define function X(p, y, m) = (0p + 1y + 2m) mod 3. An interesting property of X is that its value does not change after any pairwise meeting because X(p, y, m) = X(p-1, y-1, m+2) = X(p-1, y+2, m-1) = X(p+2, y-1, m-1). Now X(13, 15, 17) equals 1. However, X(45, 0, 0) = X(0, 45, 0) = X(0, 0, 45) = 0. This means that there is no sequence of pairwise meetings after which all chameleons will have identical color.
Saturday, April 4, 2015
Friday, April 3, 2015
Counterfeit Coin
One of twelve coins is counterfeit: it is either heavier or lighter than the rest. Is it possible to identify the counterfeit coin in three weighings on a beam balance?
This solution is first presented by "BRIAN D. BUNDY":
Solution:
This solution is first presented by "BRIAN D. BUNDY":
We may label the coins 1, 2, ..., 12 so that we can distinguish between and identify them using these labels.
1. 1. Weigh 1, 2, 3, 4 against 5, 6, 7, 8.
- They balance, so 9, 10, 11, 12 contain the odd coin. Weigh 6, 7, 8 against 9, 10, 11.
- They balance, therefore 12 is the odd coin and so weigh 12 against any other to discover whether it is heavy or light.
- 9, 10, 11 are heavy and so they contain an odd heavy coin. Weigh 9 against 10. If they balance, 11 is the odd heavy coin, otherwise the heavier of 9 and 10 is the odd coin.
- If 9, 10, 11 are light, we use the same procedure to reach the same conclusion for the odd light coin.
- 5, 6, 7, 8 are heavy and so either they contain an odd heavy coin or 1, 2, 3, 4 contain an odd light coin. Weigh 1, 2, 5 against 3, 6, 10.
- They balance, so the odd coin is 4 (light) or 7 or 8 (heavy). Thus weigh 7 against 8. If they balance 4 is light, otherwise the heavier of 7 and 8 is the odd heavy coin.
- 3, 6, 10 are heavy, so the odd coin can be 6 (heavy) or 1 or 2 (light). Thus weigh 1 against 2. If they balance 6 is heavy, otherwise the lighter of 1 and 2 is the odd light coin.
- 3, 6, 10 are light, so the odd coin is 3 and light or 5 and heavy. We thus weigh 3 against 10. If they balance 5 is heavy, otherwise 3 is light.
- If 5, 6, 7, 8 are light we use a similar procedure to that in 2.
Subscribe to:
Posts (Atom)