
carom and 4 coins
There is carom board with 4 pockets. It can have coin in any (or all) of these 4 pockets. At any given time you can select 2 pockets and see them. If it does not contain a coin you can put a coin in it, if it has you can take it out. You can also decide to leave the pockets as it is. The goal is to bring all pockets in same state, i.e. all of them should have a coin or all of the, should be empty. After every iteration (your selection of 2 pockets) carom is rotated randomly so you don't know your earlier selection.
Once all of them are in same state a light bulb will automatically glow to show you succeeded.
How many turns it can take at max to achieve this goal?
Pooja
Friday, May 13, 2005
It seems there is no maximum.
Let's say you take what looks like a simple strategy. Every turn you pick two pockets next to each other and remove the coins. Eventually you will get all the pockets to the empty state. You can probably come up with a beter strategy than that.
However because you are essentially picking pockets at random, it is possible that you will always pick the same two pockets! Then you can never guarantee that all the pockets are chosen in any fixed number of turns  hence you can never guarantee a maximum number of turns. Even if you sometimes choose pockets not next to each other there is always the possibility that one pocket is never chosen.
David Clayworth
Friday, May 13, 2005
Looks like 6 turns should be enough. Not totally sure if it is the best result though.
I can write down my cumbersome statetransition solution later, but for now I do not want to spoil the fun of solving this problem.
DK
Friday, May 13, 2005
Sounds like 4 is the answer.
Round 1  Check pocket next to you, and pocket on left.
Make them both filled.
Round2  Make the pocket next to you and the pocket across both filled.
Now we are sure at least 3 of the pockets have coins. If the 4th pocket has a coin, the light wud blink and we are done. Else, we know 1 pocket doesnt have a coin.
Round3  Look at pocket closest to you again. If it is a pocket with a coin (it is one of the pockets you filled in round 1 and round2). Look at the pocket in the left. If it doesnt have a coin, then this is the last pocket, put in a coin and you are done. If it has a coin, remove the coin.
Now we have a situation in which opposite pockets are either filled or either empty.
Round4  Look at the pocket closest to you again. If it has a coin, remove the coin from this pocket and opposite pocket. If it doesnt have a coin, add a coin to this pocket and to the opposite pocket.
Vinod Krishnan
Friday, May 13, 2005
Hi, Vinod.
Yes, I thought 4 may be enough too, but it seems there is always some catch. If I'm not missing anything  in your approach after round 3 you can only guarantee that either all pokets are full or precisely 2 pokets have coins. If those 2 pokets are next to each other or across carom  you can't tell for certain.
DK
Monday, May 16, 2005
Hi All,
Nice reading your comments and solutions.
The way I tried to solve is as follows:
(worst case it take 3 rounds).
1. Round 1 : Select 2 cornors along the digonal (that is across). 1st empty both of them, see if light glows or not.
(If it glows then you are done). If not, put coins in both of them, now see if light glows or not (if yes, done). If not means in other two one has a coin and one is empty for sure. Now among the select ones just put coin in one and take out out from other pocket.
2. Round2 : Now you have 2 coins and 2 empty holes in carrom. Both digonal have 1 coin/1empty. Select 2 pockets sideways this time. You'll get one of these three  (a) 2 empty pockets (b) 2 pockets with coins or (c) one pocket with coin and one empty . In (a) put the coins, in (b) take out coins and light will glow. In (c), take out coin from pocket where it was and put it in empty pocket. This will arrange both dignoal as 2 empty or 2 coin pockets.
3. Round3 : (If round 2 ended in case "c") Select 2 pockets across any digonal. You'll either get 2 empty pockets or 2 pockets with coin. Either you put the coins or take them out and you are done.
 Pooja
Pooja
Tuesday, May 17, 2005
Let's have some fun and invent our own notation.
Our system can be in 6 distinctive states:
0: 0 coins,
1: 1 coin,
2N: 2 coins next to each other,
2A: 2 coins across carom,
3: 3 coins, and
4: 4 coins.
The goal is to bring system from states 1,2N,2A,3 to a 0 or 4, and try to minimize number of steps:
1,2N,2A,3 >> Operation 1, Opeation 2 ... >> 0,4
There are two types of operations: one that deals with adjacent pokets  "pick Next(to each other)" and the one dealing with pokets across the table "pick Across".
During the operation we can test for specific condition (0,0), (0,1), (1,0) or (1,1) and set the state of examined pokets to a specific value.
When we reach states 0 or 4 the game ends. So when 0 or 4 is a potential outcome, on the next step we start from the other possible states. If 0 or 4 are the only outcome  we won.
Now  the game. The debut is the one, suggested by Vinod:
Step 1: 1,2N,2A,3 >> pick Next, set (1,1) >> 2N,3,4
Step 2: 2N,3 >> pick Across, set (1,1) >> 3,4
Step 3: 3 >> pick Next,
if (0,1) or (1,0) set (1,1) >> 4
if (1,1) set (0,1) >> 2N,2A
Step 4: 2N,2A >> pick Across,
if(0,0) set (1,1) >> 4
if(1,1) set (0,0) >> 0
if(0,1) do nothing >> 2N
Step 5: 2N >> pick Next,
if(0,0) set (1,1) >> 4
if(1,1) set (0,0) >> 0
if(0,1) set (1,0) >> 2A
if(1,0) set (0,1) >> 2A
Step 6: 2A >> pick Across,
if(0,0) set (1,1) >> 4
if(1,1) set (0,0) >> 0
.
DK
Tuesday, May 17, 2005
Ok, as Pooja showed, we can change pokets' states as many times as we want between the turns. My solution works, when we can only perform one coinin or coinout operation for each selected pocket between turns, as (I believe) it was stated originally.
DK
Tuesday, May 17, 2005
... urgh. sorry for the spelling, I'm having "trade a silent 'c' for coffee" week :)
DK
Tuesday, May 17, 2005
Recent Topics
Fog Creek Home
