The Bee Lover's Hotel

Question

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.

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.

Answer 1

I got a solution with:

42 cells as hallways.

Here it is:

---

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.}

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

Another of the (many) optimal solutions.

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

Answer 6

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:

Answer 7

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.

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.

Answer 8

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).

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):