PROG0195 - Counterfeiting
You have nine coins and a balance scale. One of the coins is lighter than the others. Is it possible to identify it in only two weighings?
This is indeed possible by applying the following strategy. Number the coins from 1 to 9. Divide the coins in three groups: a group containing the first three coins 1-2-3, a group containing the coins 4-5-6 and a group containing the coins 7-8-9. Put the group 1-2-3 to to the left of the balance scale and weigh it against the group 4-5-6 that you put to the right of the balance scale. If they don't balance, then the counterfeit coin is in the lighter group. If they do balance, then it's among the three coins in the unweighed group.
Having narrowed the field to a suspect group of three coins, we can apply the same principle in the second weighing. Put the first coin of the suspect group to the left of the balance scale and weigh it against the second coin of the suspect group. If they don't balance, the lighter coin is counterfeit, and if they do, the third coin of the suspect group must be lighter.
Input
There are two lines of input that describe the position of the balance scale upon respectively the first and the second weighing, if the above strategy is applied. If the balance scale is in equilibrium, the position is described by the term balance. Otherwise the position of the balance scale is described by the side of the scale that is highest: left or right.
Output
There is a single line of output containing the text coin #n is counterfeit, where n has to be filled up with the number of the counterfeit coin.
Example
Input:
left balance
Output:
coin #6 is counterfeit
Epilogue
J.E. Littlewood observes that a similar puzzle wasted 10.000 scientist-hours of work during World War II.
"There was even a proposal to drop it over Germany."
Resources
- Littlewood JE (1986). Littlewood's Miscellany. Cambridge University Press.
Je beschikt over negen muntstukken en een weegschaal. Je weet dat één van de muntstukken vervalst is, in die zin dat het lichter gemaakt is dan de andere muntstukken. Is het mogelijk om het vervalste muntstuk te identificeren door maar twee keer te wegen?
Dat kan inderdaad door de volgende strategie toe te passen. Nummer de muntstukken van 1 tot en met 9. Verdeel de muntstukken in drie groepen: een groep met de munstukken 1-2-3, een groep met de muntstukken 4-5-6 en een groep met de muntstukken 7-8-9. Plaats de groep 1-2-3 aan de linkerkant van de weegschaal en weeg die af tegen de groep 4-5-6 die je aan de rechterkant van de weegschaal plaatst. Als de weegschaal in evenwicht is, dan zit het vervalste muntstuk in de groep die niet werd afgewogen. Anders zit het vervalste muntstuk in de lichtste groep.
Nu de zoekruimte vernauwd is tot een groep van drie verdachte muntstukken, kunnen we bij een tweede weging hetzelfde principe toepassen. Plaats het eerste muntstuk van de verdachte groep aan de linkerkant van de weegschaal, en weeg het af tegen het tweede muntstuk van de verdachte groep. Als de weegschaal niet in evenwicht is, dan is het vervalste muntstuk het lichtste van de twee gewogen muntstukken. Anders is het derde muntstuk van de verdachte groep vervalst.
Invoer
De invoer bestaat uit twee regels, die de stand van de weegschaal aangeven bij respectievelijk een eerste en een tweede weging als je de strategie toepast zoals hierboven beschreven. Als de weegschaal in evenwicht is, dan wordt de stand beschreven door de tekst evenwicht. Anders wordt de stand van de weegschaal beschreven door de kant van de weegschaal die het hoogste staat: links of rechts.
Uitvoer
Een regel met de tekst muntstuk #n is vervalst, waarbij n ingevuld wordt met het nummer van het vervalste muntstuk.
Voorbeeld
Invoer:
links evenwicht
Uitvoer:
muntstuk #6 is vervalst
Epiloog
J.E. Littlewood merkt op dat wetenschappers meer dan 10.000 uren bezig geweest zijn met het oplossen van een soortgelijk probleem tijdens de Tweede Wereldoorlog.
"Er was zelfs een voorstel om het uit te strooien over Duitsland."
Bronnen
- Littlewood JE (1986). Littlewood's Miscellany. Cambridge University Press.
| Added by: | Peter Dawyndt |
| Date: | 2011-12-02 |
| Time limit: | 10s-30s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS