17
$\begingroup$

I encountered this puzzle many years ago, and I think back on it often as it is unique and thought provoking. As far as I know nobody has proved the given solution as optimum, so it may still be improved upon. I will provide the link to the original problem at the end.
I did reduce the complexity of the problem so that I can be sure of the solution to my less-intense version. Here's my version:

A hotel developer is building a new hotel, but he doesn't like elevators very much - he gets very confused by all the buttons, so he decided all of his elevators will only have one button. Long story short, each elevator will only stop on two floors. Being a sensible man, he will build more than one elevator shaft - six of them to be precise. He will also be using new MagLev elevator transport system - that means no cables and that means more than one elevator can be housed in a single shaft, as long as they don't have intersecting domains (he doesn't want any collisions!). For example: in the first shaft an elevator can be built that goes from floor 1 to floor 4. Only those two floors are serviced by that elevator. However in the same shaft a second elevator can be housed that will go from floor 5 to floor 7, and only those two floors, etc. The developer wants to be able to get from any floor in his hotel to any other floor with no more than 3 elevator trips. So, again, as an example: a guest can take elevator in the first shaft from floor 1 to floor 4, then take an elevator in the second shaft from floor 4 to floor 5 and then take the elevator in the first shaft again from floor 5 to floor 7. That will be 3 trips and the end of his adventure. Of course all the floors in the hotel need to be serviced! The question is what is the maximum number of floors that this developer can build for this hotel with these conditions?

If my version is a little too easy for you, try the harder version:

Same conditions as before, except each elevator can now stop at 6 floors.

Here's the link to where I first saw this: Elevator Efficiency

A solution has been found to the hard problem, but, like I said, nobody has proved that it is optimal, so maybe there's an obscure trick that can increase the floor number. As for the 2 floor problem I'll leave a hint:

Dr. Xorile had the right idea of making a hub and spoke system, but rot13(Lbh pna unir zber guna 3 uhof. Gur gevpx vf gung zber guna bar uho pna or npprffvoyr sebz pregnva sybbef.)

$\endgroup$
  • 2
    $\begingroup$ Can parts of the trip be in the wrong direction? For example 1 to 7, 7 to 4, 4 to 9. $\endgroup$ – Weather Vane Mar 3 at 14:27
  • $\begingroup$ @Weather Vane yes, you can take elevators in any direction. $\endgroup$ – Amorydai Mar 3 at 15:37
  • 1
    $\begingroup$ When you say that all floors need to be serviced in 3 trips are less, does that mean that you can move between any two floors in 3 trips or less? or that you can move between any floor and the ground floor in 3 moves or less? $\endgroup$ – Daniel Duque Mar 3 at 21:37
  • 1
    $\begingroup$ @DanielDuque "The developer wants to be able to get from any floor in his hotel to any other floor with no more than 3 elevator trips." $\endgroup$ – Brandon_J Mar 3 at 21:42
  • $\begingroup$ This is my first question. I guess I got impatient. I realize now that I shouldn't have asked two questions either because now I don't know who to give the checkmark to. I'll be better with my next question, I promise! By the way, the answers can maybe still be improved... $\endgroup$ – Amorydai Mar 3 at 23:42
7
$\begingroup$

Here's an improved lower bound on the answer

16 floors

         04-05 06----------10 11-12
      03----05 06-------09 10-11 12-13
   02-------05 06----08 09----11 12----14
01----------05 06-07 08-------11 12-------15
            05-06 07----------11 12----------16
            05-------------------12

or equivalently:

01----------05 06----------10 11-------------16
01-------04    06-------09 10-11          15-16
01----03       06----08 09----11       14----16
01-02          06-07 08-------11    13-------16
01-------------06 07----------11 12----------16
01-------------------------------------------16

Previous solution of

14 floors

01-02          06----------10
01----03       06-------09 10----------14
01-------04    06----08    10-------13
01----------05 06-07       10----12
01-------------06          10-11
01-------------------------10

For the larger problem, you can use a similar improvement on @Brandon_J's excellent 9 hub solution, you can squeeze out an extra couple of floors:

178 floors

Here's the tweak on his method:

1'---2-3-4----5-6
           4'-5---6'-7-8-9
   1-2-3-------------7-8---9'

Then there are 13 hubs (although as with the above, the (1,1'), (4,4'), (6,6') and (9,9') service the same spokes, so that it is very similar to the 9 hub solution that @Brandon_J presented).

With this, it is still possible to get the 20,20,20,15,15,15,20,20,20 spokes. The only addition is the 4 extra hub floors. The non-primed floors (2,3,5,7,8) work as in @Brandon_J's solution. 2,3,7,8 each have 4 shafts available which each gives us 5 floors. 5 has 3 shafts and gives us 15 floors.

1 and 9 works as follows:

1'-----------------...
1' **----------01
1'-** **-------01
1'----** **----01
1'-------** **-01
1'----------** 01--...

where each ** is a group of 5 floors. This is possible because the elevator to 01 doesn't extend and so it frees up the shaft for the top group of 5 floors from 1'.

Similarly 4 and 6 work as follows:

   04-------------05--...
   04 **-------4' 05
   04-** **----4' 05
   04----** **-4' 05
   04-------** 4'-05--...
...--------------------...
$\endgroup$
  • $\begingroup$ How would you get from 14 to 02 in two trips? $\endgroup$ – Dr Xorile Mar 3 at 22:18
  • $\begingroup$ oops I didn't read the criteria I was just trying to get there from 1 lol $\endgroup$ – Yout Ried Mar 3 at 22:26
  • 1
    $\begingroup$ You can work a 15th floor in if you're allowed looping elevator shafts (e.g. one that goes up from floor 10 and arrives into floor 01 from the bottom. The wonders of MagLev, eh? $\endgroup$ – Matthew Barber Mar 3 at 23:00
  • $\begingroup$ @MatthewBarber you'd have to make the hub floor the 11th floor, (shift the tenth floor and above up by one floor), and make a looping 01-11 elevator shaft, then insert a connection between 06 and 10 in that shaft. Unfortunately, I don't think we can loop, cause it kind of adds additional shafts. Nice lateral thinking, though! $\endgroup$ – Brandon_J Mar 3 at 23:15
  • 1
    $\begingroup$ I wonder if this can be applied to the longer problem. $\endgroup$ – Brandon_J Mar 3 at 23:37
7
$\begingroup$

My solution to the harder problem is at the end.

If you want to see my old hub logic, see my edit history. However, I now have my own

16 floor

solution to the easy problem to match DrXorile's. Here it is:

01-02 03-------06 07-------10 11-------------16
01----03 04-------07 08-------11 12----------16
01-------04 05-------08 09-------12 13-------16
01----------05 06-------09 10-------13 14----16
01-------------06 07-08 09-10 11-------14 15-16
01-------------------------------------------16

Based on my old hub logic, here's my foray into the hard problem:

9 hubs-elevator problem

As I think the image makes somewhat clear,

there are 174 serviceable floors. I think that the hub approach is maximized in this way. Having 1, 2, 3, 4, 5, or 6 hubs, you can need only one hub line. More hubs is more complicated:

7 hubs - big no-no - only two extensions possible!

1-2-3-4-5-6
  2-3-4-5-6-7
1-2-3---5-6-7

8 hubs - better than 7

1-2-3-4-5-6
    3-4-5-6-7-8
1-2-3-----6-7-8

And here is 9 hubs - THE OPTIMAL HUB SETUP for the 6-stop elevators.

1-2-3-4-5-6
      4-5-6-7-8-9
1-2-3-------7-8-9

10 hubs starts to need more lines.

For 9 hubs we can have four extensions from the 6 outside hubs, and 3 extensions from the 3 inner hubs. That's $3 extensions*5*3 hubs + 4 extensions*5*6 hubs + 9 hubs=174 floors$

Thus,

six hubs on one line is not the best system, as I thought. 9 hubs is, and I think the picture plus the equation plus the hub-map is fairly clear on how my solution works.

There is likely a better solution to the hard problem, utilizing the sneaky method in Dr Xorile's new answer, or something similar.

Here's a "check" to make sure that all of Dr Xorile's new solution (second representation) works (it does):

Numbers 2, 3, 4, and 5 all act the same - they connect to 1. 7-10 all act the same for the same reasons; same goes for 12-15. We can therefore "pool" the numbers together like so:

 P1      P2      P3      P4      P5      P6      P7
{01}    {02}    {06}    {07}    {11}    {12}    {16}
{  }<-->{03}    {  }<-->{08}<-->{  }    {13}<-->{  }
{  }    {04}    {  }    {09}    {  }    {14}    {  }
{  }    {05}    {  }    {10}    {  }    {15}    {  }
 ^^              ^                ^              ^^
 ||______________|                |______________||
 |________________________________________________|

It's pretty easy to verify the solution from here.

$\endgroup$
  • $\begingroup$ Good thought process. The hub and spoke system I believe is the answer to this and the harder version. However, it wouldn't be much of a puzzle if no tricks were involved! I have a solution that has more than 14 floors. Perhaps I shouldn't have even said that much. I will leave the problem for a couple days to see if anyone has other answers. This puzzle doesn't seem to garner much interest. I will post my solution if nobody else does. $\endgroup$ – Amorydai Mar 3 at 21:22
  • $\begingroup$ Yay, you've got it! For the "harder" version, I guess it wasn't that hard after all. If only you solved the 2 floor problem! Lol. You'll probably get the check mark anyway. $\endgroup$ – Amorydai Mar 3 at 22:07
  • $\begingroup$ looking for hints, huh? Lol, I suppose I can edit my question with a hint. $\endgroup$ – Amorydai Mar 3 at 22:55
  • $\begingroup$ Yes. The comment section is angry at me for so many comments. I did post a hint in the question though. rot13(Lbh pna unir zber guna 3 uhof. Gur gevpx vf gung zber guna bar uho pna or npprffvoyr sebz pregnva sybbef.) $\endgroup$ – Amorydai Mar 3 at 23:18
  • $\begingroup$ @Amorydai I have a new, independent solution to the 2-stop problem. $\endgroup$ – Brandon_J Mar 4 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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