(Q). Consider a decomposition of an 8×8 chessboard into p non overlapping rectangles with the following condition:- Condition (i):- Number of white and number of black squares are same Condition (ii):- If aᵢ is the number of white squares in the iᵗʰ rectangle then a₁ < a₂ < a₃ < ………<aₚ .
(i). Find the maximum possible value of p.
(ii). How many such different cases are possible if p is maximum.
Solution:-
Number of white square in 2ⁿᵈ rectangle = a₂
Number of white square in 3ʳᵈ rectangle = a₃
.
.
.
.
.
Number of white square in pᵗʰ rectangle = aₚ
Since these rectangles are non-overlapping & number of white square and black square are same in each rectangle. So addition of above all number of white square & number of black squares is equal to total number of squares in chessboard because rectangles are non-overlapping.
∴ 2(a₁ + a₂ + a₃ + ……… + aₚ) = 64
⇒ a₁ + a₂ + a₃ + ……… + aₚ = 32 ………….(i)
(i). Now to get maximum value of aₚ ⇒ the values of a₁, a₂, a₃, ………. should be minimum.
now it is given that
a₁<a₂<a₃<…………<aₚ
& a₁ will have minimum value of 1.
∴ a₁≥ 1
Hence a₂ ≥ 2
a₃ ≥ 3
Put these vallues in equation (i)
1 + 2 + 3 + …………. + P ≤ 32
⟹ ≤ 32
⟹ P(P+1) ≤ 64
Hence P = 7
∴ maximum value of p = 7 Answer
(ii). So we are to divide 8×8 chess board into 7 non-overlapping rectangles such that
⦿ number of white squares is same as number of black squares i.e. each rectangle has Even number of squares
⦿ & a₁<a₂<a₃<a₄<a₅<a₆<a₇
i.e. 2a₁<2a₂<2a₃<2a₄<2a₅<2a₆<2a₇
i.e number of squares in 1ˢᵗ rectangle < number of squares in 2ⁿᵈ rectangle < number of squares in 7ᵗʰ rectangle.
& 2a₁+2a₂+2a₃+2a₄+2a₅+2a₆+2a₇ = 64
now the different cases can be:-
No other division is possible.
So there are 4 different cases possible if p is maximum Answer