$4,072,324$ rooms

Logic Level 4

There are 4,072,324 rooms arranged in an equilateral triangle, similar to the image at right (but extending much further down).

Each room has a door to all adjacent rooms with which it shares a wall. You are currently standing in the room at the top, and your mission is to enter every single room on one condition: you can't enter a room more than twice.

Employing the best strategy to accomplish your goal, what is the least number of rooms you need to enter twice?

The answer is 2017.

3 solutions

Nicola Mignoni
Feb 15, 2018

The following picture represents the path to visit all the rooms.

There is a double-visited room per 'floor', except for the top room. The number of 'floor' is

$\displaystyle\sum_{k=0}^{n} 2k+1=4072324$ , $\displaystyle n=2017$

So, the number of double-visited rooms plus $1$ is

$\displaystyle (2017-1)+1=2017$

Thank you for clearing this up. I was really wondering why my answer was wrong.

Steven Perkins - 3 years, 3 months ago

You're welcome!

Nicola Mignoni - 3 years, 3 months ago

Note that your 2 ways are actually the same, just rotated.
Always remember that to prove something is a minimum, you have to show that A) It can be achieved, B) No smaller value can be achieved. You have done A, but not B.

Calvin Lin Staff - 3 years, 3 months ago

Just fixed 1. I'll try to fix 2. and to be more rigorous in the future. Thanks for made me notice it.

Nicola Mignoni - 3 years, 3 months ago

There's a nice way to deal with 2.

Hint: There are indeed many distinct ways to get 2017 (Try playing with 4 rows in a haphazard manner.) Figure out the classification for which rooms are repeated, and use that to explain why we need at least 2017.

Calvin Lin Staff - 3 years, 3 months ago

@Calvin Lin – If you want another way to think about it, @Calvin Lin and @Nicola Mignoni , think about a possible 2 colour colouring arrangement, where all routes will alternate colours as you go through rooms.

Stephen Mellor - 3 years, 3 months ago

@Stephen Mellor – @Calvin Lin - When I started thinking about the possible paths to solve the problem, I noticed that after the first move (coming down from the top room) I could move to the side rooms in the second floor or keeping going down. In both cases there's always a room, per each foor, that remains unvisited at least. This made me think that I would be obliged to double-visit at least a room per floor (if I keep my path in a descending fashion) or one per floor (except one floor) and two at the last. I know that is not sufficient to proof it, just wanted to make you aware about my brain-racking! @Stephen Mellor - I thought something similar: considering each floor as a binary number where each non-visited room is 0 and the visited ones are 1. So the purpose of the game is to obtain the biggest odd number per floor.

Nicola Mignoni - 3 years, 3 months ago

Niranjan Khanderia
Feb 20, 2018

This is the answer, do you know how you can prove it is the lowest? Hint: Think about colouring

Stephen Mellor - 3 years, 3 months ago

Dane Yousif
Mar 5, 2018

We see that with 16 rooms there are 3 entries to be made twice which is sqrt(16)-1, if we apply the same logic to an equilateral triangle with 4,072,324 rooms we would get 2018-1=2017

4 , 072 , 324 4,072,324 4 , 0 7 2 , 3 2 4 rooms

The answer is 2017.

3 solutions

0 pending reports

$4,072,324$ rooms