We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
56
3
avatar

There are 8 ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 5 grid:

 

 

Find the number of ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 50 grid.

 Nov 16, 2019
 #1
avatar+53 
+3

 

 

Let's call a \(2 \times 2\) square a 'block' and a \(2 \times 1\) rectangle consisting of a column of two \(1 \times 1\) squares a 'blank'. So a \(2\times 10\) grid, for instance, consists of 10 consecutive blanks, numbered 1 to 10 from left to right, and a block occupies two consecutive blanks, say blanks 1 and 2, which I will denote by (1, 2). The max number of blocks that can be arranged on our \(2 \times 10\)grid is, of course 5, and the places they would occupy  would be denoted as (1, 2), (3, 4), (5, 6), (7,8), and (9,10). We will first look at the number of arrangements on the \(2 \times 10\) grid and then extend the results to a \(2 \times 50\) grid.

First note that a block can occupy a \(2 \times k\) blan grid in k - 1 different ways. For instance, on a \(2 \times 10\) blank grid, the block can be placed on (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), or (9, 10).

The following table shows that the number of arrangements for a \(2 \times 10\) grid is

\({10 \choose 0 } + {9\choose 1} +{8\choose 2}+{7\choose3}+{6\choose 4}+{5\choose5}=89\)

 

 

 

 

Thiscan be generalized to a \(2 \times 50 \) Grid. see below

 

 

 

 Nov 16, 2019
 #2
avatar+53 
+1

Sorry,I posted an EXCEL chart without explanation. For the \(2 \times 50\) grid, the number of arrangements is

 

\({50 \choose 0}+{49 \choose 1} + {48 \choose 2} + ...+{26 \choose 24} +{25 \choose 25}= 20,365,011,074\) arrangements. EXCEL was the only tool I could use to calculate such an enormous sum.

I am looking for a more elegant way to count this giant number of arrangement. I am certain there is one somewhere on the web!

 Nov 16, 2019
 #3
avatar+23516 
+2

There are 8 ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 5 grid:

 

 

Find the number of ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 50 grid.

 

\(\begin{array}{|c|c|c|c|} \hline & \text{Starts with} & \text{Starts with} \\ \text{grid:} & 2\times 1 & 2\times 2 & \text{sum} \\ \hline 2 \times 1 & 1 & 0 & 1 = F_{2} \\ \hline 2 \times 2 & 1 & 1 & 2 = F_{3} \\ \hline 2 \times 3 & 2 & 1 & 3 = F_{4} \\ \hline 2 \times 4 & 3 & 2 & 5 = F_{5} \\ \hline 2 \times 5 & 5 & 3 & 8 = F_{6} \\ \hline 2 \times 6 & 8 & 5 & 13 = F_{7} \\ \hline 2 \times 7 & 13 & 8 & 21 = F_{8} \\ \hline \ldots & \ldots \\ 2 \times 10 & 55 & 34 & 89 = F_{11} \\ \hline \ldots & \ldots \\ \hline 2 \times k & F_k & F_{k-1} & F_{k+1} \\ \hline 2\times 50 & F_{50} & F_{49} & 20365011074= F_{51} \\ \hline \end{array}\)

 

\(\begin{array}{|lrcll|} \hline \mathbf{ F_k \text{ is the } k^{th} \text{ Fibonacci Number:}} \\ F_1 = 1,\ F_2 = 1,\ F_3 = 2,\ F_4 = 3,\ F_5 = 5, \\ F_6 = 8,\ F_7 = 13,\ F_8 = 21,\ F_9 = 34,\ F_{10} = 55,\ldots , \\ F_{49} = 7778742049,\ F_{50} =12586269025,\ F_{51} = 20365011074 \\ \hline \end{array}\)

 

hint:

Fibonacci Number as Sum of Binomial Coefficients:

\(\begin{array}{rcll} \displaystyle F_n &=& \displaystyle \sum_{k \mathop = 0}^{\Big\lfloor {\dfrac {n - 1} 2}\Big\rfloor } \dbinom {n - k - 1} k \\ &=&\displaystyle \binom {n - 1} 0 + \binom {n - 2} 1 + \binom {n - 3} 2 + \dotsb + \binom {n - j} {j - 1} + \binom {n - j - 1} j \quad \text{ where } \quad j = \Big\lfloor {\dfrac {n - 1} 2} \Big\rfloor \\ \end{array}\)

 

source: https://proofwiki.org/wiki/Fibonacci_Number_as_Sum_of_Binomial_Coefficients

 

laugh

 Nov 17, 2019
edited by heureka  Nov 18, 2019

6 Online Users