13
$\begingroup$

Oskar van Deventer has created the “haunted vending machine puzzle”.

enter image description here

You have to insert coins into the slots 1, 2, 3 or 4. A coin that hits a green switch on its head rests there; a coin that hits a switch on its leg changes switch position. A starting position is shown on the left side. The goal is to have 7 coins in the machine (one on each switch). Partial solution is shown on right side (3 out of 7 coins are on the right places). You can insert as many coins as you need, your supply of coins is unlimited.

You can try this game here (a java applet).

Is it always possible to solve the puzzle? Is there a way to calculate the solution?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ If a coin hits a switch on the head when the switch already has a coin on its leg, what happens? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jun 14, 2014 at 21:28
  • 1
    $\begingroup$ A coin on a leg always switches the switch. A second coin on a coin rolls to the free way down. (I.e. you insert a first coin in 1, it stops on the first switch. You insert a second coin in 1, it rolls to the right (slope2)and hits the leg of the switch what means changing the switch an releasing the first coin. The first coin is now falling (slope 1), touching the leg of the switched switch and re-switching it.So if you insert another coin in 1 it will stop on the first switch) $\endgroup$
    – Harvey
    Commented Jun 14, 2014 at 23:04
  • $\begingroup$ I saw a similar switch mechanism used for a binary adding machine. $\endgroup$
    – user88
    Commented Jun 15, 2014 at 12:51
  • $\begingroup$ Do we always start with zero stuck coins? $\endgroup$
    – greg m
    Commented Jun 17, 2014 at 11:24
  • $\begingroup$ @greg m - yes, at the start there are zero coins in the machine but as you can see in the applet there are different starting positions for the switches possible $\endgroup$
    – Harvey
    Commented Jun 18, 2014 at 7:06

3 Answers 3

Reset to default
7
$\begingroup$

First of all if either of the top two switches has a coin on it, drop another to clear it. Now, if either of them are leaning in (and by leaning I always mean the top of the switch leaning that way), drop a coin on their outside so that lean out. From now on we will only ever hit a top-row switch with pairs of coins (one each side), so they will always stay clear and lean out. (until the final two or coins, anyway!)

Now, if the central switch has a coin on it, drop a pair of coins on either top-row switch. One of them will fall through and clear the central switch. We will also be keeping the central switch clear until right near the end.

Observe that we can now drop a set of four coins one each into the four slots - in any order - and these three switches will all end up clear, and the top row leaning out.

Consider the outside switches on the middle row. After the first coin strikes them, they can only ever lean in. Let's drop a set of four coins so we know they're leaning in. The only possible states are with-coin and without.

If we were to drop a pair of coins on the side away from which the central switch leans, we change the state of the outer-middle switch on that side while keeping the central switch clear and the top switches unchanged. If the two out-middle switches are in different states, do this to bring them into alignment.

If the outer-middle switches do not have coins on them, drop a set of four so that they will.

Now we have the top and central switches clear, the outer-middle switches laden, the top switches leaning out and the outer-middle switches laden. This can be preserved by dropping two sets of four in a row, to make a set of eight.

(I'm going to ask that the very first coin of each set of eight be placed directly above the exposed leg of the central switch. This is to constrain the order in which the coins arrive at the lower switches. It doesn't actually make a difference to the outcome in the next paragraph but does make it easier to calculate.)

What happens to the lower switches when we drop a set of eight? They each get hit inside, then outside, then inside again. The effect this has depends on their initial state.

  • out+laden -> out+unladen
  • out+unladen -> in+unladen
  • in+laden -> in+unladen
  • in+unladen -> in+laden

Drop two sets of eight. Now both bottom switches must leaning in, and will remain leaning in after any number of sets of eight after that.

Next, we deal with the bottom switch toward which the central switch is leaning. We want it to be in+laden. If it is in+unladen, drop a set of eight. Now it is in+laden.

If the other bottom switch is also in+laden then the bottom row is complete. Otherwise we complete is as such:

Drop two pairs (preserving the state of all but the bottom row because the outer-middle switch gets toggled twice) on the side toward which the central switch is leaning (the side that is currently in+laden). The first pair will drop a coin on the outside of the near bottom switch, making it in+unladen just like the other bottom switch. The second pair will drop coins on the inside of both switches, loading them up.

Once the bottom row is complete, we simply drop a coin from directly above the head of the central switch to load it up, then do the same for the two switches on the top row.

Okay, now you can all have fun spotting the mistakes I no doubt made. :)

Improve this answer
$\endgroup$
3
  • $\begingroup$ You say "if either of them are leaning in (and by leaning I always mean the top of the switch leaning that way), drop a coin on their inside so that lean out." But if they are leaning in, and you drop a coin on their inside, won't the coin simply stay on their head? $\endgroup$
    – Trenin
    Commented Jun 20, 2014 at 11:17
  • $\begingroup$ Worked like a charm! $\endgroup$
    – Trenin
    Commented Jun 20, 2014 at 11:22
  • $\begingroup$ This answer is good! And it also makes the nice observation that the outer-middle switches can only ever lean in after the first coin strikes them. $\endgroup$
    – justhalf
    Commented Jun 26, 2014 at 9:31
1
$\begingroup$

This can be modelled as a graph transition problem. There are $(2 \times 2)^7 = 16~384$ possible states the machine can be in, with each switch being either on the left or the right, and the coin on the switch or off of it. This is represented as a directed graph with $16~384$ points.

Each point has four out edges, representing inserting a coin into one of the four slots, and a varying number of in edges, depending on which states get to that state by inserting a coin into them.

Your goal is to get from one of the $128$ states where none of the switches have coins on them to one of the $128$ states where all the switches have coins on them. This is equivalent to finding a path in the graph from the first state to the second state, which is doable with a computer using breadth-first search. The length of the path represents the total number of coins you need to insert.

Improve this answer
$\endgroup$
0
$\begingroup$

The starting position shown cannot be solved in 7 coins. Look at the rightmost switch. You can't land a coin on its head without first flipping it. When you flip it, the coin will continue on through the bottom switch and out of the machine. Unless you've flipped the bottom switch already, which again means you've lost a coin out the bottom.

Edit: turns out I was misunderstanding the question, the wording was a bit confusing. You can use more than seven coins in order to get seven coins stuck.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, you are right, the supply of coins is unlimited. $\endgroup$
    – Harvey
    Commented Jun 15, 2014 at 8:32
  • $\begingroup$ I think you mean the rightmost switch, but the argument is correct. $\endgroup$
    – Ross Millikan
    Commented Jun 15, 2014 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.