IMC 2000/2/1

#1

(α) Να δειχθεί ότι αν το

είναι αρκετά μεγάλο τότε το μοναδιαίο τετράγωνο μπορεί να διαμεριστεί σε

μικρότερα τετράγωνα.
(β) Έστω $d \geqslant 2$ . Να δειχθεί ότι υπάρχει μια σταθερά N(d)

έτσι ώστε για κάθε $n \geqslant N(d)$ o

-διάστατος μονιαδιαίος κύβος μπορεί να διαμεριστεί σε

μικρότερους κύβους.

[Και εδώ με το (α) απαντημένο και το (β) προς το παρόν αναπάντητο.]

#2

Το ερώτημα (β) είναι πολύ γνωστό. Στην απόδειξή του θα χρησιμοποιήσουμε το παρακάτω αποτέλεσμα του Sylvester, ειδική περίπτωση του Frobenius Coin Problem:

Ισχυρισμός: Έστω $\displaystyle{p,q}$ θετικοί ακέραιοι, με $\displaystyle{\left( {p,q} \right) = 1}$ . Τότε, ο $\displaystyle{pq - p - q}$ είναι ο μεγαλύτερος ακέραιος αριθμός που δεν μπορεί να γραφεί στη μορφή $\displaystyle{px + qy}$ , όπου $\displaystyle{x,y}$ φυσικοί αριθμοί.

Απόδειξη του Ισχυρισμού: Ας υποθέσουμε ότι υπάρχουν φυσικοί αριθμοί $\displaystyle{x,y}$ τέτοιοι, ώστε

$\displaystyle{pq - p - q = px + qy.}$

Εφόσον $\displaystyle{\left( {p,q} \right) = 1}$ , ο $\displaystyle{p}$ θα διαιρεί τον $\displaystyle{y + 1}$ και ο $\displaystyle{q}$ θα διαιρεί τον $\displaystyle{x + 1.}$ Αν ήταν $\displaystyle{p = y + 1}$ , τότε θα είχαμε ότι

$\displaystyle{\left( {y + 1} \right)q - \left( {y + 1} \right) - q = \left( {y + 1} \right)x + qy \Rightarrow x = - 1,}$

που είναι άτοπο. Άρα, θα είναι $\displaystyle{p < y + 1}$ και (όμοια) $\displaystyle{q < x + 1,}$ οπότε

$\displaystyle{pq - p - q = px + qy > p\left( {q - 1} \right) + q\left( {p - 1} \right) = 2pq - p - q,}$

που είναι άτοπο.

Για το δεύτερο μέρος του Ισχυρισμού (που είναι αυτό που ουσιαστικά χρειαζόμαστε), θεωρούμε τυχαίο ακέραιο $\displaystyle{n > pq - p - q.}$ Εφόσον $\displaystyle{\left( {p,q} \right) = 1}$ , η γραμμική διοφαντική εξίσωση

$\displaystyle{px + qy = p + q + n}$

έχει ακέραια λύση $\displaystyle{\left( {{x_0},{y_0}} \right)}$ και η γενική της λύση είναι

$\displaystyle{\left( {x,y} \right) = \left( {{x_0} + kq,{y_0} - kp} \right),}$

με $\displaystyle{k \in \mathbb{Z}.}$

Επιλέγουμε $\displaystyle{k \in \mathbb{Z}}$ με $\displaystyle{ - \frac{{{x_0}}}{q} < k \le - \frac{{{x_0}}}{q} + 1}$ . Τότε, είναι

$\displaystyle{0 < x = {x_0} + kq \le q}$

και

$\displaystyle{y = {y_0} - kp \ge {y_0} - \left( { - \frac{{{x_0}}}{q} + 1} \right)p = \frac{{p{x_0} + q{y_0} - pq}}{q} = \frac{{n - \left( {pq - p - q} \right)}}{q} > 0,}$

οπότε

$\displaystyle{n = p\left( {x - 1} \right) + q\left( {y - 1} \right),}$

όπου $\displaystyle{{x - 1,y - 1 \in \mathbb{N}}}$ και η απόδειξη του Ισχυρισμού ολοκληρώνεται.

Πίσω στο αρχικό πρόβλημα: Θα λέμε ότι ο φυσικός αριθμός $\displaystyle{n}$ είναι καλός, αν ο $\displaystyle{d}$ -διάστατος κύβος μπορεί να διαμεριστεί σε $\displaystyle{n}$ κύβους.

Παρατηρούμε ότι αν ο $\displaystyle{n}$ είναι καλός, τότε και ο αριθμός $\displaystyle{n + {a^d} - 1}$ είναι καλός για κάθε ακέραιο $\displaystyle{a \ge 2}$ .

[ Πράγματι, έστω ότι ο $\displaystyle{d}$ -διάστατος κύβος διαμερίζεται σε $\displaystyle{n}$ κύβους. Παίρνουμε έναν από αυτούς και τον χωρίζουμε σε $\displaystyle{{a^d}}$ ίσους κύβους. Τότε ο αρχικός $\displaystyle{d}$ -διάστατος κύβος διαμερίζεται σε $\displaystyle{n + {a^d} - 1}$ κύβους. ]

Εφόσον ο αριθμός $\displaystyle{1}$ είναι (προφανώς) καλός, από τα παραπάνω προκύπτει ότι κάθε αριθμός της μορφής

$\displaystyle{1 + x\left( {{a^d} - 1} \right) + y\left( {{b^d} - 1} \right)}$

είναι επίσης καλός, όπου $\displaystyle{a,b,x,y \in \mathbb{Z}}$ , με $\displaystyle{a \ge 2,b \ge 2,x \ge 0,y \ge 0.}$

Επιλέγουμε τους $\displaystyle{a,b}$ έτσι, ώστε $\displaystyle{\left( {{a^d} - 1,{b^d} - 1} \right) = 1.}$ (Για παράδειγμα, μπορούμε να πάρουμε $\displaystyle{a = 2}$ και $\displaystyle{b = {2^d} - 1}$ ). Από τον ισχυρισμό, αν

$\displaystyle{n - 1 > \left( {{a^d} - 1} \right)\left( {{b^d} - 1} \right) - \left( {{a^d} - 1} \right) - \left( {{b^d} - 1} \right),}$

τότε υπάρχουν φυσικοί αριθμοί $\displaystyle{x,y }$ τέτοιοι, ώστε

$\displaystyle{n - 1 = x\left( {{a^d} - 1} \right) + y\left( {{b^d} - 1} \right).}$

Ώστε, αν θέσουμε

$\displaystyle{N\left( d \right) = \left( {{a^d} - 1} \right)\left( {{b^d} - 1} \right) - \left( {{a^d} - 1} \right) - \left( {{b^d} - 1} \right) + 1 = \left( {{a^d} - 2} \right)\left( {{b^d} - 2} \right),}$

τότε κάθε ακέραιος $\displaystyle{n > N\left( d \right)}$ είναι καλός και η απόδειξη ολοκληρώνεται.

Για $\displaystyle{d = 2}$ , προκύπτει ότι κάθε κάθε ακέραιος $\displaystyle{n \ge 15}$ είναι καλός, δηλαδή ότι κάθε τετράγωνο μπορεί να χωριστεί σε $\displaystyle{n}$ τετράγωνα, για κάθε $\displaystyle{n \ge 15.}$

Για $\displaystyle{d = 3}$ , προκύπτει ότι κάθε κάθε ακέραιος $\displaystyle{n \ge 2047}$ είναι καλός, δηλαδή ότι κάθε κύβος μπορεί να χωριστεί σε $\displaystyle{n}$ κύβους, για κάθε $\displaystyle{n \ge 2047.}$

Τα παραπάνω προέκυψαν με την επιλογή $\displaystyle{a = 2}$ και $\displaystyle{b = {2^d} - 1}$ . Φυσικά, κανείς δεν ισχυρίζεται ότι αυτή είναι η βέλτιστη επιλογή! Γεννιέται, λοιπόν, το ακόλουθο:

Ερώτημα: Για δοσμένη διάσταση $\displaystyle{{d \ge 2}}$ , ποιος είναι ο μεγαλύτερος αριθμός που ΔΕΝ είναι καλός;

(Δεν γνωρίζω την απάντηση ούτε για $\displaystyle{{d = 2}}$ ...)

#3

Για

βγάζω ότι ο n=5

δεν είναι καλός ενώ κάθε $n \geqslant 6$ είναι καλός. (Άσκηση)

Για d = 3

το ερώτημα του Βαγγέλη μου φαίνεται υπερβολικά δύσκολο. Για μεγάλα

θα μπορούσαμε να κοιτάξουμε το ερώτημα ασυμπτωτικά. Π.χ. αν συμβολίσω με M(d)

τον μεγαλύτερο αριθμό που δεν είναι καλός τότε η απόδειξη του Βαγγέλη δείχνει ότι $M(d) < 2^{d+d^2}$ . Από την άλλη μπορώ να δείξω ότι M(d) > 2^d

. Υποψιάζομαι ότι το κάτω φράγμα είναι πιο κοντά στην σωστή τιμή από το άνω φράγμα.

IMC 2000/2/1

IMC 2000/2/1

Re: IMC 2000/2/1

Re: IMC 2000/2/1

Μέλη σε σύνδεση