Fog Creek Software
Discussion Board




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 state-transition 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 coin-in or coin-out 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