## Combinatorics : Castle, rooms and doors

**Moderators:** gmalivuk, Moderators General, Prelates

### Combinatorics : Castle, rooms and doors

Hi evrybody,

A castle is built like a grid nxn.

Each room have 4 walls.

At most one door is opened on each wall.

Each room have exactly 2 doors.

Depending on the value of n how many configurations m are possible?

Example : n=1 m=6

If we note the walls A,B,C,D then we have 6 possibilities :

A,B

A,C

A,D

B,C

B,D

C,D

What about n>1 ?

Can you find a close formula to compute the configurations possible?

For each value n what is the minimal number of doors satisfying the conditions above?

Thank you for any clue.

A castle is built like a grid nxn.

Each room have 4 walls.

At most one door is opened on each wall.

Each room have exactly 2 doors.

Depending on the value of n how many configurations m are possible?

Example : n=1 m=6

If we note the walls A,B,C,D then we have 6 possibilities :

A,B

A,C

A,D

B,C

B,D

C,D

What about n>1 ?

Can you find a close formula to compute the configurations possible?

For each value n what is the minimal number of doors satisfying the conditions above?

Thank you for any clue.

### Re: Combinatorics : Castle, rooms and doors

I'll start with some clues. First try to tackle the problem recursively, then you can see if your recursive formula has a nice closed form.

Here's a useful propery: for a given castle shape, if there are m configurations, pick ANY wall. Exactly m/2 configurations have a door in that wall. The proof is trivial with the right idea.

So, let's extend to 2x1. We have 3 configurations each where the connecting wall has a door (so 3x3 new configurations) and 3 configurations each where the connecting wall has no door (so 3x3 more configurations) for a total of 3x3+3x3=18.

This will lead you to a recursive formula for castles sizes 1 x n, which has a simple closed form.

Then you'll notice that this formula doesn't just work for 1 x n castles, but for all castle shapes of n rooms that can you can recursively create by adding rooms that touch exactly one single existing room. For example, a L shape covering the leftmost column and the bottom row of a square castle. The remaining rooms can be filled in one at a time, but they will touch two existing walls, and you'll need a new formula for those. You will also need to prove an additional property of wall placement.

Have fun!

Here's a useful propery: for a given castle shape, if there are m configurations, pick ANY wall. Exactly m/2 configurations have a door in that wall. The proof is trivial with the right idea.

So, let's extend to 2x1. We have 3 configurations each where the connecting wall has a door (so 3x3 new configurations) and 3 configurations each where the connecting wall has no door (so 3x3 more configurations) for a total of 3x3+3x3=18.

This will lead you to a recursive formula for castles sizes 1 x n, which has a simple closed form.

Then you'll notice that this formula doesn't just work for 1 x n castles, but for all castle shapes of n rooms that can you can recursively create by adding rooms that touch exactly one single existing room. For example, a L shape covering the leftmost column and the bottom row of a square castle. The remaining rooms can be filled in one at a time, but they will touch two existing walls, and you'll need a new formula for those. You will also need to prove an additional property of wall placement.

Have fun!

### Re: Combinatorics : Castle, rooms and doors

Thank you for your comments.

1xn is easy to solve.

I was asking for a square nxn (2x2,3x3....) which is different.

The 2th question remain unanswered.

1xn is easy to solve.

I was asking for a square nxn (2x2,3x3....) which is different.

The 2th question remain unanswered.

### Re: Combinatorics : Castle, rooms and doors

Is it not homework. It is in fact a part of an abstract game.

Does it seem too hard (maybe) or am I wrong?

Does it seem too hard (maybe) or am I wrong?

### Re: Combinatorics : Castle, rooms and doors

The questions I`m asking for are not easy to solve.

It requires time.

If you have any documentation about similar problems please let me know.

Thank you.

It requires time.

If you have any documentation about similar problems please let me know.

Thank you.

### Re: Combinatorics : Castle, rooms and doors

For n=2 grid 2x2 there are 82 configurations possible

For n=3 grid 3x3 there are 2604 configurations possible

Is there any way to have a close formula?

For n=3 grid 3x3 there are 2604 configurations possible

Is there any way to have a close formula?

### Re: Combinatorics : Castle, rooms and doors

I get 86 for 2x2.

Starting from 54 for the 3-room"L", 11 have two open doors towards the fourth room (->11 options), 11 have no open door (->11 options), and 32 have one open door (->2*32 options), for a total of 86 options.

Finding that number of 11 was not trivial, so I don't see an easy way to generalize it.

Starting from 54 for the 3-room"L", 11 have two open doors towards the fourth room (->11 options), 11 have no open door (->11 options), and 32 have one open door (->2*32 options), for a total of 86 options.

Finding that number of 11 was not trivial, so I don't see an easy way to generalize it.

### Re: Combinatorics : Castle, rooms and doors

mfb wrote:I get 86 for 2x2.

Starting from 54 for the 3-room"L", 11 have two open doors towards the fourth room (->11 options), 11 have no open door (->11 options), and 32 have one open door (->2*32 options), for a total of 86 options.

Finding that number of 11 was not trivial, so I don't see an easy way to generalize it.

82 is correct. I get 13 L's with two doors/no doors towards the 4th room, and 14+14 with one door. This results in 2*28+13+13 = 82 possibilities for the 2x2.

In fact, the number of 2xn grids of rooms is a(n+1) where a() is the sequence A052913 on oeis, defined by the recurrence relation a(n) = 5*a(n-1) - 2*a(n-2), with a(0) = 1, a(1) = 4.

For 3xn grids there is a similar recurrence relation but where each term depends on the previous three terms, but this sequence is not on the oeis. I haven't found a general formula for nxn.

There is a very easy formula if rooms were also allowed 0 or 4 doors, i.e. any even number.

### Re: Combinatorics : Castle, rooms and doors

Finding a general formula for nxn is doable using a trick.

What are the configurations for n=1 with 0,1,3,4 doors ?

0 1

1 4

2 6

3 4

4 1

So for any nxn 0 and 4 doors wil be = 1.

Finding 1 door is like finiding 3 doors (symmetrical)

If we find a general formula for nxn with 0,1,2,3,4 doors then we wil obtain 2 doors by substraction.

Is it easy easy to find formula for 1 door?

Is it easy to find a general formula for 0,1,2,3,4 doors?

I`m working on.

What are the configurations for n=1 with 0,1,3,4 doors ?

0 1

1 4

2 6

3 4

4 1

So for any nxn 0 and 4 doors wil be = 1.

Finding 1 door is like finiding 3 doors (symmetrical)

If we find a general formula for nxn with 0,1,2,3,4 doors then we wil obtain 2 doors by substraction.

Is it easy easy to find formula for 1 door?

Is it easy to find a general formula for 0,1,2,3,4 doors?

I`m working on.

### Re: Combinatorics : Castle, rooms and doors

Goahead52 wrote:If we find a general formula for nxn with 0,1,2,3,4 doors then we wil obtain 2 doors by substraction.

Subtraction from what? The number of nxn configurations where all the rooms have the same number of doors? How will that be calculated?

Anyway, here are the results that I got by computer:

Code: Select all

`x 1 2 3 4 5 6 7 8 9 10 11`

1 6 18 54 162 486 1458 4374 13122 39366 118098 354294

2 18 82 374 1706 7782 35498 161926 738634 3369318 15369322

3 54 374 2604 18150 126534 882180 6150510 42881094 298965276

4 162 1706 18150 193662 2068146 22091514 235994086 2521075822

5 486 7782 126534 2068146 33865632 554916090 9094954740

6 1458 35498 882180 22091514 554916090 13956665236

7 4374 161926 6150510 235994086 9094954740

8 13122 738634 42881094 2521075822

9 39366 3369318 298965276

10 118098 15369322

11 354294

So for nxn with n=1..6 we have 6, 82, 2604, 193662, 33865632, 13956665236.

### Re: Combinatorics : Castle, rooms and doors

Thank you.

Your results look like OEIS sequence :

https://oeis.org/search?q=6%2C82%2C2604 ... &go=Search

and we have an explicit formula here

https://oeis.org/A078099

Your results look like OEIS sequence :

https://oeis.org/search?q=6%2C82%2C2604 ... &go=Search

and we have an explicit formula here

https://oeis.org/A078099

### Re: Combinatorics : Castle, rooms and doors

I tried to make a connection between 3-colorings and doors, using the colors at the corners and the vertices between the colors as walls. The numbers match but I don't see an intuitive connection yet.

### Re: Combinatorics : Castle, rooms and doors

mfb wrote:I tried to make a connection between 3-colorings and doors, using the colors at the corners and the vertices between the colors as walls. The numbers match but I don't see an intuitive connection yet.

I'm pretty sure I see the connection. If we number the colors 1, 2, and 3, then traversing around the four vertices of a room cyclically, we see that the color goes up by one or down by one each time. Since the net change in color must be a multiple of three since we start and end at the same color, and it also must be one of +4, +2, +0, -2, and -4 by parity, it must be +0, so there'll be two +1's and two -1's. Assign the doors to the +1's. We now checkerboard the castle, and assign the black rooms to be traversed counterclockwise and the white rooms to be traversed clockwise so that adjacent rooms agree on their shared wall. This gives a unique door assignment for each coloring that starts with 1 at the upper left vertex, and conversely each assignment of doors generates a unique coloring as long as we start with 1 in the upper right corner.

(∫|p|

Thanks, skeptical scientist, for knowing symbols and giving them to me.

^{2})(∫|q|^{2}) ≥ (∫|pq|)^{2}Thanks, skeptical scientist, for knowing symbols and giving them to me.

### Re: Combinatorics : Castle, rooms and doors

Yeah, just figured that out as well.

Was confused by the odd 3, but once you consider a "direction", it works nicely.

An interesting connection.

Was confused by the odd 3, but once you consider a "direction", it works nicely.

An interesting connection.

- SuicideJunkie
**Posts:**431**Joined:**Sun Feb 22, 2015 2:40 pm UTC

### Re: Combinatorics : Castle, rooms and doors

After doing math for a while you get used to 3 being odd.

### Who is online

Users browsing this forum: No registered users and 14 guests