We will call one of the cells of a rectangle 11 x 13 “peculiar” , if after removing it the remaining figure can be cut into squares 2 x 2 and 3 x 3. How many of the 143 cells are “peculiar”?
Problem
Source: IX International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade
Tags: table, combinatorics
Pinko
22.09.2018 01:28
4
We will write in each cell the number of the column that it is in. Each square 2 x 2 covers equal number of odd and even numbers and each square 3 x 3 covers 3 more even or 3 more odd numbers (depends on its position). As the odd numbers are 11 more than the even ones, then the square 1 x 1 that should be removed can be only on an even numbered column and the remaining difference of odd and even numbers will be 12 which can be covered by squares 3 x 3. Also each square 3 x 3 covers equal number of cells from each of the remainders modulo 3, whereas 2 x 2 covers 2 numbers from 2 of the remainders modulo 3 and zero numbers from the third remainder. As there is even number of cells of remainders “0” and “2” modulo 3 and odd number of cells with remainder “1” modulo 3, the square 1 x 1 should be on a column with remainder “1”. Combining this with the previous finding we come to the conclusion that the removed square can be only in columns 4 and 10. Through similar reasoning we get that the square 1 x 1 that should be removed can be only in rows 3 and 9. Each of these 4 cells, that we have as intersections of the columns and rows, is “peculiar”, because the table now can be separated into the following rectangles for which it easy to see that they can be covered by squares 2 x 2 and 3 x 3: 3 x 3, 2 x 10, 9 x 9, and 4 x 8.