Maths Olympiad Prep

Library / /104 of 377

Number theory Difficulty 4.9 AIME Prove it United States

Problem:
Show that for bb even, there exists some MM such that for every m,n>Mm, n > M with mnm n even, an m×nm \times n rectangle is (1,b)(1, b)-tileable.

Solution

Solution:
By the diagram below, it is possible to tile a (2b+2)×(4b+1)(2 b+2) \times (4 b+1) rectangle.

Figure 1

Since we can already tile a (2b+2)×2b(2 b+2) \times 2 b rectangle by above, and 2b2 b is relatively prime to 4b+14 b+1, this will allow us to tile any (2b+2)×n(2 b+2) \times n rectangle for nn sufficiently large. Combining this with the previous problem, this will allow us to tile any m×nm \times n rectangle for mm and nn sufficiently large and mm even, completing the proof.

To tile the (2b+2)×(4b+1)(2 b+2) \times (4 b+1) rectangle, we first tile the following piece:

Figure 1

This is then combined with two 2×2b2 \times 2 b rectangles, a 2b×b2 b \times b rectangle, and a 2b×(2b+1)2 b \times (2 b+1) rectangle as follows:

Figure 2

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 reproduced verbatim; metadata (topic, difficulty) added by this project.