Combinatorics : Castle, rooms and doors

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

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.

Tub
Posts: 475
Joined: Wed Jul 27, 2011 3:13 pm UTC

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!

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

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?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

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?

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

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.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

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.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

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      111        6        18         54         162         486         1458        4374       13122      39366    118098  3542942       18        82        374        1706        7782        35498      161926      738634    3369318  153693223       54       374       2604       18150      126534       882180     6150510    42881094  2989652764      162      1706      18150      193662     2068146     22091514   235994086  25210758225      486      7782     126534     2068146    33865632    554916090  90949547406     1458     35498     882180    22091514   554916090  139566652367     4374    161926    6150510   235994086  90949547408    13122    738634   42881094  25210758229    39366   3369318  29896527610  118098  1536932211  354294`

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

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

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

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

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.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

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|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

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.

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.

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests