A classic problem (or so I'm told) from Computer Science. Not too hard to figure out, bit more of a trick to come up with a computer program to figure it out.
A building has 8 floors. It has some number of elevators. Each elevator can stop at any four floors, but only four. We want to be able to take an elevator directly from any floor to any other floor. If we had one elevator that stopped at all 8 floors, the problem would be solved. But due to some outside influence (politics, the elevator operators union, insurance, royal decree, what have you), our elevators can only stop at 4 floors. So we could have 2 elevators: one that stops at the first four floors, and a second that services the top four floors (5 thru 8). All of the floors would have access to an elevator, but the people on the top four floors would be stuck on those four floors and would never be able to leave the building. Likewise the people on the bottom four floors would never be able to get to the top four floors. It would be like two different worlds.
So now maybe you understand the problem. What we want is the minimum number of elevators that would allow you to go directly from any floor to any other floor on one elevator. We don't want to have to change elevators in mid-journey. And no, you can't use the stairs. That's cheating.
Subscribe to:
Post Comments (Atom)
4 comments:
three
I think it takes more than three. Can you show me?
There would have to be 3 elevators.
First: 1, 2, 3, 8
Second: 1, 4, 5, 8
Third: 1, 6, 7, 8
That way you can go all the way up or all the way down in any elevator and still hit 2 other floors on the way up or down!
Mmmm, no. We want to be able
to go directly from any floor to any other floor on one elevator. With your plan, you can go directly from 1 to any other floor, and you can go directly from any floor to 8, but you cannot go directly from 3 to 4, or 4 to 6, or 7 to 2. If an elevator only stopped at 2 floors, it would take 28 elevators to provide this level of service (28=7+6+5+4+3+2+1). And if the elevator could stop at all eight floors, you would only need one.
Post a Comment