uniolympiads Ελληνικά

IMC 2000, Day 2, Problem 1

a) Show that the unit square can be partitioned into nn smaller squares if nn is large enough.

b) Let d≥2d \ge 2. Show that there is a constant N(d)N(d) such that, whenever n≥N(d)n \ge N(d), a dd-dimensional unit cube can be partitioned into nn smaller cubes.

Original from the official PDFa) Show that the unit square can be partitioned into n smaller squares if n is large enough. b) Let d ≥ 2. Show that there is a constant N (d) such that, whenever n ≥ N (d), a d-dimensional unit cube can be partitioned into n smaller cubes.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. We start with the following lemma: If aa and bb be coprime positive integers then every sufficiently large positive integer mm can be expressed in the form ax+byax+by with x,yx,y non-negative integers.

Proof of the lemma. The numbers 00, aa, 2a2a, …\dots, (b−1)a(b-1)a give a complete residue system modulo bb. Consequently, for any mm there exists a 0≤x≤b−10\le x\le b-1 so that ax≡m(modb)ax\equiv m\pmod b. If m≥(b−1)am\ge(b-1)a, then y=(m−ax)/by=(m-ax)/b, for which x+by=mx+by=m, is a non-negative integer, too.

Now observe that any dissection of a cube into nn smaller cubes may be refined to give a dissection into n+(ad−1)n+(a^d-1) cubes, for any a≥1a\ge1. This refinement is achieved by picking an arbitrary cube in the dissection, and cutting it into ada^d smaller cubes. To prove the required result, then, it suffices to exhibit two relatively prime integers of form ad−1a^d-1. In the 2-dimensional case, a1=2a_1=2 and a2=3a_2=3 give the coprime numbers 22−1=32^2-1=3 and 32−1=83^2-1=8. In the general case, two such integers are 2d−12^d-1 and (2d−1)d−1(2^d-1)^d-1, as is easy to check.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?