IMC 2000/2/1

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8113
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2000/2/1

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Σεπ 23, 2012 10:44 pm

(α) Να δειχθεί ότι αν το n είναι αρκετά μεγάλο τότε το μοναδιαίο τετράγωνο μπορεί να διαμεριστεί σε n μικρότερα τετράγωνα.
(β) Έστω d \geqslant 2. Να δειχθεί ότι υπάρχει μια σταθερά N(d) έτσι ώστε για κάθε n \geqslant N(d) o d-διάστατος μονιαδιαίος κύβος μπορεί να διαμεριστεί σε n μικρότερους κύβους.

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


Άβαταρ μέλους
emouroukos
Γενικός Συντονιστής
Δημοσιεύσεις: 1389
Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
Τοποθεσία: Αγρίνιο

Re: IMC 2000/2/1

#2

Μη αναγνωσμένη δημοσίευση από emouroukos » Τρί Σεπ 25, 2012 12:24 pm

Το ερώτημα (β) είναι πολύ γνωστό. Στην απόδειξή του θα χρησιμοποιήσουμε το παρακάτω αποτέλεσμα του 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}}...)


Βαγγέλης Μουρούκος

Erro ergo sum.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8113
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2000/2/1

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Σεπ 25, 2012 6:56 pm

Για d=2 βγάζω ότι ο n=5 δεν είναι καλός ενώ κάθε n \geqslant 6 είναι καλός. (Άσκηση)

Για d = 3 το ερώτημα του Βαγγέλη μου φαίνεται υπερβολικά δύσκολο. Για μεγάλα d θα μπορούσαμε να κοιτάξουμε το ερώτημα ασυμπτωτικά. Π.χ. αν συμβολίσω με M(d) τον μεγαλύτερο αριθμό που δεν είναι καλός τότε η απόδειξη του Βαγγέλη δείχνει ότι M(d) < 2^{d+d^2}. Από την άλλη μπορώ να δείξω ότι M(d) > 2^d. Υποψιάζομαι ότι το κάτω φράγμα είναι πιο κοντά στην σωστή τιμή από το άνω φράγμα.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες