Puzzle – 100 Doors

I’m a big fan of logic puzzles. Normally, we only get asked these kind of questions during interviews but they are pretty fun to think about outside of an interview setting.

Here we go:

There are 100 doors in a long hallway. They are all closed. The first time you walk by each door, you open it. The second time around, you close every second door (since they are all opened). On the third pass you stop at every third door and open it if it’s closed, close it if it’s open. On the fourth pass, you take action on every fourth door. You repeat this pattern for 100 passes.

Question: At the end of 100 passes, what doors are opened and what doors are closed?

Snaps if you can figure it out. (No googling allowed!)

See answer below:

So, there are many ways to approach this problem.
Here’s how I went about solving this puzzle. There are two states a door to be in, opened or closed. On each pass of a door, the door’s state is toggled. Since all the doors starts off closed, we can say if we visit a door an even number of times, the door will be closed. If we visit the door an odd number of times, it will be opened in the door. Let’s see this in action with 5 doors (O = Opened, C = Closed)

Pass # Door 1 Door 2 Door 3 Door 4 Door 5
Initial C C C C C
Pass 1 O O O O O
Pass 2 O C O C O
Pass 3 O C C C O
Pass 4 O C C O O
Pass 5 O C C O C

One thing to note is once we pass door X X times, we never will have to toggle door X again. For example, once we pass door 10 on the 10th pass, on the 11th pass and subsequent passes, we will never have to revisit doors 10 and all the doors before 10.

Looking at the 5 doors shown in the table above, we see that only door 1 and door 4 are left open. They will remain open for the rest of the passes to 100. What’s special with 1 and 4? What makes us visit a door an odd number of times versus an even number of times? Let’s look what made us close door 2, 3, and 5 and open 1 and 4.

On the first pass, we opened all of the doors because it was the 1st pass.
Here we know door 1 is going to remain opened.
On the second pass, we closed all of the doors with numbers that were even or divisible by 2. (doors 2, 4, 6, 8, etc)
Here, we know door 2 is going to remain closed.
On the third pass, door 3 gets closed and remains closed.
On the fourth pass, door 4 gets reopened and remains opened.
On the fifth pass, door 5 is closed.

The factors of 1 are 1 and itself. It has one factor
The factors of 2, 3, and 5 are 1 and themselves. They have two factors.
The factors of 4 are 1 and itself, as well as 2. 4 has three factors.

Didn’t we say if we visit a door an odd number of times, it remains open?
It turns out the number of factors a number has is the same number of times we visit it.
If a number has an odd number of factors, we visit it an odd number of times.
If a number has an even number of factor, we visit it an even number of times.

So, the big question is what numbers have an odd number of factors?
Looking at 1 and 4 gives us some insight. Both numbers have factors that are performing double duty.
1 has 1×1 and 4 has 2×2. While factors come in pairs, we only count these factors that are performing double duty as one.

What do we call numbers that have factors that perform this double duty? Perfect squares.

The answer is doors 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 are opened. The rest are closed.

Puzzle – 100 Doors

Re: Gold Bar Riddle

As promised, click here the solution.

At the end of day two, the pharaoh is able to make one more cut and must pay the mason 2/7ths of the gold bar. The only way to do this is to use the larger (6/7th) piece and cut out a 2/7th piece. The pharaoh takes back the 1/7th piece and gives the 2/7th piece. Now the pharaoh has all made all of his alloted cuts and there are 3 pieces of gold bar: a 1/7th piece, a 2/7th piece, and the remaining 4/7th piece.

With these three pieces, the pharaoh is able to pay the mason every day the fraction amount of the entire gold bar that corresponds to the number of days work. I think the trickiest part was realizing that the mason can give back pieces as change.

Day 1: Pay with the 1/7th piece
Day 2: Pay with the 2/7th piece
Day 3: Pay with the 1/7th and 2/7th pieces (1/7 + 2/7 = 3/7)
Day 4: Pay with the 4/7th piece
Day 5: Pay with the 1/7th and 4/7th piece (1/7 + 4/7 = 5/7)
Day 6: Pay with the 2/7th and 4/7th pieces (2/7 + 4/7 = 6/7)
Day 7: Pay with all the pieces (1/7 + 2/7 + 4/7 = 7/7)

Of course, this is only possible if the mason doesn’t go off and spend his pay before the end of the week 🙂

Re: Gold Bar Riddle

Gold Bar Riddle

I was recently given this puzzle and I thought I would share it with everyone else. So the puzzle starts…

There’s a pharaoh who wants to build a huge pyramid to compensate for his lack of self confidence. He hires a stonemason to build his pyramid in 7 days and agrees to pay the mason one gold bar upon completion for his work.

The stonemason doesn’t like the pharaoh very much nor does he trust him. So, he demands that the pharaoh pay him at the end of every day an equivalent fraction of the gold bar as the number of days that he worked. That is, after the first day of work, the pharaoh must pay him 1/7 of the gold bar, 2/7 at the end of the 2nd day, 3/7 on the 3rd, etc until the end of the 7th day where he will receive his full payment of the gold bar. The kicker is the pharaoh may only make two cuts on the gold bar. Reluctantly, the pharaoh agrees to these terms.

The question is “How does the pharaoh do it?”

As with a lot of puzzles, it helps to talk it through so feel free to post a comment or question. 🙂

I’ll post the answer later for everyone or I can answer it for myself…depending if anyone else is reading this.

Hint: There’s only one way to pay him the first day.

Gold Bar Riddle