uniolympiads English

IMC 2000, Ημέρα 2, Θέμα 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.

Πρωτότυπο από το επίσημο 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.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 1. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;