All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Tiling 3x110 grid (Posted on 2018-08-21)
You are given 165 rectangular tokens, they are all indistinguishable sizewise, but only 2 of them are red. The tokens are 2x1 and you are asked to tile a 3x110 grid keeping the red tokens parallel each to the other.
In how many ways can such task be done?

a. No other restrictions.
b. The red tokens cannot be parallel to any of the non-red tokens.

Comments: ( Back to comment list | You must be logged in to post comments.)
 attempted solution | Comment 1 of 9

On 22 Aug. I revised (corrected :-) ) my answer substantially.....

We picture three long rows. The non-red tiles must all be horizontal. Why? They cannot be mixed H and V by the constraints on the red.  Also, they cannot be all V, since otherwise many H tiles would be needed to fill in above or below the vertical tiles. Consequently, the non-red tiles are all horizontal and the two red tiles are vertical.

If we number the columns 1 to 110, the two reds must lie on an odd and an even column so as to allow the H tiles to fill evenly. Also, the two reds must be standing vertically within the same two rows: both in rows 1,2 or both in 2,3 (else, they would make an odd length horizontal gap that could not be filled.)

So, we list the column pairings possible for the two reds:

(1,2  1,4  1,6 ... 1,110)

(3,4  3,6  3,8 ... 3,110)

...

(119,110)

So, how to tally these?

Let's take simpler examples. If there were 4 columns rather than 110

we would have possibilities (1,2) (1,4) (3,4)   (3 ways for the reds)

likewise with 6 columns we have (1,2) (1,4) (1,6) (3,4), (3,6) (5,6) (6 ways for red)

and so forth. For n=4, 6, 8, 10, 12 columns, there are N=3, 6, 10, 15, 21 ways. Each time we have added 3, 4, 5, 6, ...  So, for n>4 (and even)

N_n = 3 + (3 + 4 + ... + n/2).

Now make an expression using the Method of Gauss:

2 N_n = 3 + (3 +    4 +          5 +     + ... n/2)

+ 3 + (n/2 + (n/2-1)+ (n/2-2) + ... +3)

2 N_n = 6 + (n/2-2) (n/2+3) = 6 + (n^2)/4 + n/2 - 6

which gives N_n = (n^2+2n)/8

so N_110 = 1540.

But these two reds can be on rows 1,2 or 2,3, so there are twice the possibilities: 3080 ways.

Edited on August 22, 2018, 6:21 pm
 Posted by Steven Lord on 2018-08-22 03:44:11

 Search: Search body:
Forums (0)