Maths Olympiad Prep

Library / /12 of 17

Combinatorics Difficulty 6.2 National olympiad Prove it Argentina

Facu and Nico play the following game with a 13×1313 \times 13 grid square. Facu cuts the square into rectangles having a side equal to 11, in any way he wishes. Then Nico chooses a number kk among 1,2,,131, 2, \ldots, 13 and takes all the obtained rectangles 1×k1 \times k. How many grid cells can he take with certainty?

Solution

Nico can always ensure 1616 cells. Suppose that there is a partition like in the statement so that no 1616 cells can be taken. Then this partition has at most 11 rectangle 1×k1 \times k for each k=8,9,10,11,12,13k = 8, 9, 10, 11, 12, 13; at most 22 such rectangles for k=6,7k = 6, 7; at most 33 such rectangles for k=4,5k = 4, 5; at most 55 such rectangles 1×31 \times 3, at most 77 rectangles 1×21 \times 2 and at most 1515 unit cells 1×11 \times 1. Consequently the total area does not exceed

(8+9+10+11+12+13)+2(6+7)+3(4+5)+53+72+151=160. (8+9+10+11+12+13)+2(6+7)+3(4+5)+5 \cdot 3+7 \cdot 2+15 \cdot 1=160.

This is false because the 13×1313 \times 13 square has area 132=16913^2 = 169. Therefore 1616 cells can be taken regardless of how Facu plays.

On the other hand 1717 cells are not always achievable. Here is an example. The first row is untouched; the next 99 are cut as follows:

12+1,11+2,10+3,9+4,8+5,8+5,7+6,7+6,5+4+4. 12+1,11+2,10+3,9+4,8+5,8+5,7+6,7+6,5+4+4.

Rows 1111 and 1212 are 3+3+3+3+13+3+3+3+1 and 2+2+2+2+2+2+12+2+2+2+2+2+1; row 1313 is cut into 1313 unit cells. In summary, the answer is 1616 cells.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.