# Solution or Origin of logic puzzle

This is not my puzzle and I do not know the solution. This was shared to me by a friend. Their former boss told them this riddle. I was told this question originated from Steven's Institute of Technology and it has to do with how a computer processor works. It's been a few days and so far no one we've asked this to can figure it out. We are starting to believe that my friend does not remember the puzzle and is missing or mistaking critical information. Can you solve this? Or is it similar to an already existing puzzle and incorrectly worded, if so please share the original puzzle.

There are two dwarfs on opposite sides of the same mountain. Between them there is a single track which is the only form of transportation to reach the other side. Since it is a single track, if two carts attempted to cross, they will collide. The dwarfs are not fond of each other and cannot meet. They have an unlimited amount of buckets and rocks to communicate. Both dwarfs must reach the other side of the mountain. They cannot be on the same side of the mountain at the same time.

Rules:

• The dwarfs cannot meet or cross paths on the track.
• One dwarf can't wait or hide on one side as the other arrives or else this would count as them both being on the same side at the same time.
• They cannot speak to each other or communicate in any other way aside from using buckets and rocks.
• There is no other path aside from the single track. It is assumed both dwarfs have at least 1 cart to use on the track.
• The end goal is to have both dwarfs swap sides, they are not visiting and returning to their original side. Their final destination is the opposite side of where they started.

My thoughts so far:

The single track probably relates to a lane used in the processor. I imagine a processor like a circuit board, the traces connect various parts, in this case two sides of a mountain. The lane can only pass 1 or 0, which means there is a current or no current.

The rocks or buckets seem useless since it is unlikely that the other dwarf would be able to decipher what the message means. Maybe they are used as an obstacle or to keep track of their path or distance.

I think this is worded wrong because it seems impossible since the only way they can reach the other side is using the track and since they cannot meet or be on the same side at the same time. There is no way this is possible.

• I'm not sure if this will be helpful but it sounds like a version of some prisoner and lightbulb puzzles.
– Jay
Jul 11, 2018 at 0:12
• @Jay I just looked that up, I'm sorry but I don't see the resemblance, maybe similar to how they are trying to solve the light bulb on/off could apply to a rock being in the bucket but I think the bigger issue here is how they can cross instead of a communication issue. Jul 16, 2018 at 22:46
• @AthanasiosKaragiannis As an afterthought: if the dwarves can not meet with or without their cart then why is the cart mentioned at all? (and why the "at least one cart"?) I don't see how it changes the problem. Those N carts of theirs are why I figured out they would return once their cart has been unloaded/sold/whatever on the other side. Following your last edit it appears the problem is much simpler: they just have to go to the other side once. Jul 18, 2018 at 0:31

I do agree with you that there seems to be a major flaw in this puzzle: if the dwarves can neither be on the same side of the monntain nor on the same track, they can not move to the other side with their cart.

However:

• they may pass each other if only one of them has a cart
• they may meet at the summit and swap their cart (or swap their load). But since you say "they are not fond of each other" (I didn't understand the "and connect meet" part) I can hardly imagine they would give their cart to one another.

Putting aside the constraint that they must not be on the same side of the mountain (not that this makes the problem hard or impossible, just because it seems unnecessary to me, especially when comparing to the computing world), here is a possible scenario:

• there is a bucket on the track at the top of the mountain
• when a dwarf decide to go to the other side with his cart, he must first go without his load to the summit
• if there is already a rock in the bucket, he must wait
• if not, he puts his rock in the bucket and goes back down to fetch his cart
• he goes to the other side of the mountain (possibly meeting a waiting dwarf halfway)
• when he goes back, he picks up his rock from the bucket and goes down the mountain back to his dwelling
• if the other dwarf was waiting, he then puts his own rock in the bucket and so on

What does it have to do with computing? This is how mutual exclusion works to prevent multiple simultaneous access to a shared resource (be it a memory segment, a data bus, a peripheral, etc).

• I appreciate your well written response. From my understanding of this puzzle, the rule that they cannot meet at all, even on the track to swap carts or simply walk past each other, makes it impossible for them to be near each other to perform a simple crossing. After thinking about this for weeks now. I honestly think the description of the puzzle is flawed. Jul 16, 2018 at 22:48
• The fact that they cannot walk past each other does not invalidate my scenario: you can imagine that as soon as a dwarf has the right to go down the other side of the mountain (i.e. has put his rock into the bucket) then if the other dwarf was on the track, he must go down too and wait for the former to finish his duty on the other side before going up the track again. Jul 16, 2018 at 23:10
• I see what you mean, I misunderstood that. If one dwarf decides to proceed because of the rock in the bucket and the other dwarf retreats or is already on their side. This means the traveling dwarf would meet the other dwarf on the same side and that violates the second bullet point rule. Reading back to make sure I put that rule there, I seem to have worded it oddly. So I will revise that. Jul 18, 2018 at 0:04
• I don't see how they would meet if one dwarf retreats as soon as he sees the other. But I agree they would be on the same side, a constraint I dismissed as being unmeetable. I reread your question and I wonder if the actual constraint would rather be "the dwarfs are allowed to be on the same side as long as they are not both on the mountain track" (i.e. they may wait in their town that is beyond the mountain). Jul 18, 2018 at 0:20
• I agree, the intended problem seems to be about mutual exclusion where the answer is meant to be Dekker's algorithm or something similar. Aug 27, 2018 at 14:57

The fact that there is only 1 track, and that the dwarves cannot meet, already makes this an impossible setup. No matter what they do, they will meet somewhere along this track, probably in the middle so they could switch sides simultaneously (also forbidden..)

With lateral thinking however I can see some approaches:

lateral approach 1)

Let one dwarf excavate a new tunnel. There is no time constraint mentioned in the puzzle.

lateral approach 2)

Let the dwarves walk around the mountain. They'll always be on opposite sides of the mountain. Make sure that they leave their unlimited amount of rocks where they are, or they will hate you for making them walk so far with such heavy luggage.

lateral approach 3)

In the middle of the track/mountain, modify the track into a two-way jump like this so the carts don't collide.

The constraints are rigorous; the dwarfs can not meet at either side, nor anywhere on the track.

The puzzle suggests that they are able to communicate using buckets and rocks. Failing that... arguably the puzzle is about inventing a way of communication without being able to communicate outside of the way that they are inventing. That would be interesting... but arguably it is futile. Either way, it is not apparent how communicating would help with solving the root problem.