38
$\begingroup$

Dr Bees likes bees. Dr Bees is not his real name, but that is what everybody calls him.

I should actually say that he is obsessed with bees. Bees are his whole life. He knows everything about them. Anything anyone has published about bees, he knows.

He never learned the alphabet past the second letter.

Anyway. He made a fortune locating the best honey you could find anywhere in the world and selling it to people who can afford to pay ridiculous prices for a minuscule jar of honey. He wants to invest his money.

His latest project is a hotel for bee lovers. He noted that there is no bee-themed hotel, which he sees as a huge and untapped market opportunity. I mean, who doesn't like bees? Who wouldn't like to spend a night surrounded by the soft humming of bees? Or better, who wouldn't like to live like a bee for a night? So he decided that he would build the first hotel for bee lovers.

He pays a visit to an architect friend and brings along the concept he drafted for his hotel. A large hotel with 127 rooms in the shape of a beehive.

Hexagonal arrangement of hexagons with side 7

The architect looks at the plan and tries not to laugh.

  • Is it a hotel for ... bees?
  • No, no! This is a hotel for people. But I got my inspiration from an actual beehive. The rooms are hexagonal to minimize the length of the walls. Inside I wanted to show people. But I never managed to draw people.
  • Don't worry, I know you all too well. But I see a problem. Real people don't fly. How are they going to go in or out of the hotel rooms?
  • I would say "with the bees, do like the bees". But I see your point. I didn't think of that. Can you fix that?
  • I think so. First you need an entrance somewhere on the outer wall. Then you will have to replace some rooms with hallways. Every room must be adjacent to a hallway and the hallways must provide a path from the room to the hotel entrance.
  • I see. But that is not good. People pay for the rooms, not for the hallways. These hallways are just maintenance and no revenue. How many hallways do I need? I mean, what is the absolute minimum number of rooms I need to convert to hallways to make my hotel usable for real people?
  • Hmm. That is a good question. I will have to consult my wife. She is good at these things.

So, dear reader, how would you solve Dr. Bees' problem?

  • You can see a preliminary plan of the hotel. Bees represent hotel rooms.
  • You have to replace a number of rooms with hallways in order to provide a path from each room to a single main entrance. This means that the hallways must form a connected region and at least one of them must lie on the perimeter of the hexagon.
  • Every remaining room must be adjacent to at least one hallway.
  • The number of rooms converted to hallways must be minimal.

So, what is the minimum of hallways the hotel needs? Show how it can be done.

Clarification

Some solutions assume the outer rooms don't need an access to a hallway since they can have a door to the outside. While this is arguably what Dr. Bees would prefer, it is not what the puzzle asks you to solve. It explicitly says that all rooms must be adjacent to a hallway and the hallways must form a connected region.

I will add to the specifications that the outside of the hotel must not be considered a giant hallway.

This is my own creation. I have a solution; I am curious to see if you can find a better one.

$\endgroup$
9
  • $\begingroup$ Considering your clarification, there must be only a single hallway? Can it/them be branched? $\endgroup$ Oct 26, 2022 at 11:05
  • 8
    $\begingroup$ Can't Dr. Bees tell his guests to climb on top of the combs, walk along the edges and then drop down into their room? At least. that's how the bees do it :^) $\endgroup$
    – QBrute
    Oct 26, 2022 at 14:35
  • 1
    $\begingroup$ I guess people would pay a premium for rooms that have windows, as most of them would be entirely interior... $\endgroup$ Oct 26, 2022 at 15:28
  • 1
    $\begingroup$ FWIW, there's a bee-lovers hotel in Czechia, where you effectively sleep on top of a hive. Their website seems down ATM, but you can see some photos in this report about it. $\endgroup$ Oct 27, 2022 at 13:25
  • 1
    $\begingroup$ Awesome puzzle! $\endgroup$ Oct 28, 2022 at 0:03

8 Answers 8

22
$\begingroup$

I got a solution with:

42 cells as hallways.

Here it is:

enter image description here


Proof of optimality

Start with 0 hallways. Add the entrance in some edge. This will make 4 rooms accessible. If you start in a corner instead, this will give you 1 less accessible room and will only make your solution less optimal.

Starting add new hallways connected to an existing hallway. Every time you do that, the previous hallway will give access to 1 less room than it used to do. Every time you add a new hallway, at most 3 new rooms become accessible, but if that new hallway will not be a dead-end, one of those new rooms will be turned to the next hallway, so, with the exception of the entrance, each hallway section gives access to at most 2 rooms. Also, to get a new dead-end that gives access to 3 new rooms, you will also need to make a bifurcation that gives you 1 less room, so you still get 2 new reachable rooms per hallway in the best case.

This means that the best you can get is 2 new accessible rooms per hallway, and 1 more than that because the entrance started giving 4. So the number of cells is one more than the triple of the number of hallways. Or put in the other way around, the number of hallways is a third of the number of cells minus one. Hence, $(127 - 1) \div 3 = 42$. So this is the best solution possible.

Thanks to Kruga for the sketch of the proof in a comment and also for Daniel Wagner that also gave something similar in another comment.

$\endgroup$
8
  • 4
    $\begingroup$ This feels optimal $\endgroup$
    – JLee
    Oct 26, 2022 at 14:07
  • 1
    $\begingroup$ Congratulations! This is the solution I found. The center can also turn the other way round and the entry cell could be moved. But it is just small variations. It tends to show the solution is essentially unique. $\endgroup$
    – Florian F
    Oct 26, 2022 at 18:49
  • $\begingroup$ @FlorianF Yes, I found that too. Also, reflecting and rotating the whole thing is obviously possible too. But those are all essentially the same thing. Like you, I also conjecture that this is the only approach that gives that (also conjectured) optimal result. $\endgroup$ Oct 26, 2022 at 19:15
  • 4
    $\begingroup$ This is the minimum solution. We need to cover all cells, and each hallway covers itself plus its adjacent cells. The entrance can cover 5 at most. The rest must be next to existing hallways, and can only cover 3 uncovered cells. So N hallways can cover 3N+2 cells. To cover all 127 we need at least 42 hallways. $\endgroup$
    – Kruga
    Oct 28, 2022 at 7:37
  • 1
    $\begingroup$ I made a (terrible) version with the cells fills in red for those of us that find that easier to follow. $\endgroup$ Oct 28, 2022 at 13:22
11
$\begingroup$

Here's a solution with 43 habitation cells converted to hallway cells:

43 solution

$\endgroup$
4
  • $\begingroup$ I wonder whether there is an elegant pen-and-paper way to prove this is optimal without using some brute forcing computer analysis. $\endgroup$
    – quarague
    Oct 26, 2022 at 8:18
  • $\begingroup$ Nice red carpet for the hallways. Though I am sure Dr. Bees would prefer a more honey-like color, like golden or yellow-brown. This being said, don't you wish 42 to be the answer :-)? $\endgroup$
    – Florian F
    Oct 26, 2022 at 10:27
  • 2
    $\begingroup$ @quarague I've tried, but came up short. 41 is an easy bound to get, but I don't see any obvious ways to strengthen it beyond that. $\endgroup$
    – Deusovi
    Oct 26, 2022 at 11:53
  • 4
    $\begingroup$ @quarague 42 is optimal. Each time you step from one hallway to another, there are at most three new locations you can get to that you couldn't from the previous cell. Since every hallway can be reached from one on the edge, and the one spot on the edge makes five positions available (itself and four neighbors), you can reach at most 3n+2 locations using n hallways. (This gets you to a lower bound of 42, since there are 127 cells to reach; an existing answer shows the lower bound is achievable.) $\endgroup$ Oct 27, 2022 at 17:00
5
$\begingroup$

Here's one with

44 rooms converted to hallways. There are various ways to add/remove equal numbers of rooms; not sure whether it can be improved upon.

enter image description here

$\endgroup$
5
$\begingroup$

I think its in the order of

32 cells to hallways. Considering that the outside of the hotel is considered a hallway... Every cell on the edge can have a door, so people can get in privately ;)

I think this solves Dr.Bees problem better than the problem statement from the architect, as Dr.Bees did not want any hallways and is asking the number of hallways to be minimized. The architect is so much in his human bubble, he did not consider not every room needs to border to a hallway.

hotel

$\endgroup$
3
  • 2
    $\begingroup$ This is a good answer, but I am not sure if this is compatible with the statement "First you need an entry somewhere on the outer wall." $\endgroup$
    – ACB
    Oct 26, 2022 at 10:34
  • 2
    $\begingroup$ i agree, but it is compatible with: I see. But that is not good. People pay for the rooms, not for the hallways. These hallways are just maintenance and no revenue. How many hallways do I need? I mean, what is the absolute minimum number of rooms I need to convert to hallways to make my hotel usable for real people $\endgroup$
    – busssard
    Oct 26, 2022 at 10:37
  • 5
    $\begingroup$ I thought of that. I could have added another layer of rooms around the hotel to cover this. I prefered to cover this in the instructions. Let's say there must be a reception and all people going in or out must do so via the reception. $\endgroup$
    – Florian F
    Oct 26, 2022 at 10:56
4
$\begingroup$

Another of the (many) optimal solutions.

42 hallway cells. Note that the proof of optimality is already in the comment of the accepted answer.
enter image description here

$\endgroup$
3
  • $\begingroup$ Fantastic! There are more solutions than I thought after all. $\endgroup$
    – Florian F
    Oct 28, 2022 at 14:42
  • $\begingroup$ @Florian maybe Dr Bees should ask, as a follow up question, to minimize the longest way to the exit (which can be much less than the answers here (not sure how much less). After all, who wants humans longer in the corridors than needed, they should be buzzie somewere else. $\endgroup$
    – Retudin
    Oct 28, 2022 at 15:08
  • $\begingroup$ True, that would be a good idea. But I will not change the rules after a solution was accepted. Feel free to optimize in this direction. $\endgroup$
    – Florian F
    Oct 28, 2022 at 15:16
2
$\begingroup$

I used a different approach that looks to be the best so far, but I did it by hand/eye so I'd be surprised if its optimal.

I got 38, using the idea of single-room courtyard-like entrances around the perimeter.

Here's my solution, with blue being hallways:

enter image description here

$\endgroup$
3
  • 4
    $\begingroup$ The question states in the "clarification" that there should be only one entrance. $\endgroup$
    – Deusovi
    Oct 27, 2022 at 15:06
  • $\begingroup$ Thanks; I don't know how I missed that. I just finished getting it down to 36, too. $\endgroup$ Oct 27, 2022 at 15:18
  • 1
    $\begingroup$ This is actually a nice solution if we are allowed multiple entries. $\endgroup$ Oct 28, 2022 at 0:02
1
$\begingroup$

I'm not qualified to comment yet so I could only post it as an answer though it is not. 42 is roughly 127/3, which means one hallway cell serves for 2 unique bee rooms on average (there should be one room left since 42*(2+1) = 126, 1 means room cell taken up by hallway cell). 43 is therefore easy to get following the idea that one hallway serves 2 unique rooms (just go straight and turn if you have to). What remains is how 42 can be attained and less than 42 no longer satisfies. Wondering if similar results happen if we consider bee hotels with less levels, 2 levels of 7 rooms with 2 hallway cells, 3 levels of 19 rooms with 6 hallway cells and etc.

2-level bee hotels3-level bee hotels

About the clarification it is in fact same problem since 6 levels hotel contains 91 cells and 30 hallway cells will do the trick and 1 more hallway will lead to the entrance for 7 levels hotel, that is, 31 hallways in total.

7-level bee hotels ignoring boundary

$\endgroup$
1
$\begingroup$

Following a suggestion by Retudin to minimize the distance from the entrance I searched for a new solution.

With the insight I got of Daniel's and Kruga's proof of optimality, which tells what to avoid in an optimal solution, I came up with the following, with a maximum path of 18 cells (19 if you count the room).

enter image description here

Incidentally, it can easily be converted into the solution that has the longest path to a room (among the 42-hallways solutions).

Or still better, max length 16 with Retudin's improvement (and a rotation for cosmetic reasons):

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Wow less than I expected, but looking at your solution there is an easy improvement: 16(17) if you move the entrance 2 NW and the opening in the outer ring 2 SE $\endgroup$
    – Retudin
    Oct 29, 2022 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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