mathematica.gr

Δημοσιεύτηκε: **Πέμ Ιουν 15, 2017 12:29 pm**

Να βρεθεί ο ελάχιστος φυσικός

ώστε αν έχουμε

σημεία με ακέραιες συντεταγμένες στο επίπεδο τότε υπάρχουν δύο που το τετράγωνο της απόστασής τους είναι πολλαπλάσιο του 2016

.

Δημοσιεύτηκε: **Πέμ Ιουν 15, 2017 12:53 pm**

Πρόκειται για το πρόβλημα 2 της ολυμπιάδας της Βραζιλίας 2016.
https://artofproblemsolving.com/communi ... 90p7304182

Δημοσιεύτηκε: **Πέμ Ιουν 15, 2017 1:23 pm**

WLOG έγραψε:Πρόκειται για το πρόβλημα 2 της ολυμπιάδας της Βραζιλίας 2016.
https://artofproblemsolving.com/communi ... 90p7304182

Ας μην ξεχαστεί όμως. Υπάρχει απλούστερη λύση;

Δημοσιεύτηκε: **Πέμ Ιουν 29, 2017 5:31 pm**

Βάζω ουσιαστικά την λύση που υπάρχει εκεί (από εκεί πήρα την άσκηση) αλλά ελπίζω καλύτερα διατυπωμένη:

Έστω αρχικά ότι έχω τουλάχιστον $2^5 \cdot 3^2 \cdot 7^2 + 1$ σημεία. Από την αρχή του περιστερώνα, μπορούμε να βρούμε δύο σημεία (x_1,x_2),(y_1,y_2)

ώστε:

$\displaystyle{ x_1 \equiv y_1 \bmod 3}$
$\displaystyle{ x_2 \equiv y_2 \bmod 3}$
$\displaystyle{ x_1 \equiv y_1 \bmod 7}$
$\displaystyle{ x_2 \equiv y_2 \bmod 7}$
$\displaystyle{ x_1 \equiv y_1 \bmod 4}$
$\displaystyle{ x_1+x_2 \equiv y_1 +y_2 \bmod 8}$

Τότε $(x_1-x_2)^2 + (y_1-y_2)^2 \equiv 0 \bmod 9$ και $(x_1-x_2)^2 + (y_1-y_2)^2 \equiv 0 \bmod 7$ . Επίσης:

$\displaystyle{ (x_1-x_2)^2 + (y_1-y_2)^2 = (x_1-x_2)^2 + (x_1-x_2 + 8k)^2 \equiv 2(x_1-x_2)^2 + 16k(x_1-x_2) \equiv 0 \bmod 32}$

Άρα $\displaystyle{(x_1-x_2)^2 + (y_1-y_2)^2 \equiv 0 \bmod 2016}$

Για να δείξουμε ότι δεν γίνεται με λιγότερα σημεία, για κάθε σημείο (x_1,y_1)

ορίζουμε το διάνυσμα

$(x_1 \bmod 3, y_1 \bmod 3, x_1 \bmod 7, y_1 \bmod 7, x_1 \bmod 4, x_1+y_1 \bmod 8)$

Από το κινέζικο θεώρημα μπορούμε να βρούμε $2^5 \cdot 3^2 \cdot 7^2$ σημεία που να δίνουν διαφορετικά διανύσματα. Μένει να δείξουμε ότι το τετράγωνο της απόστασης δυο διαφορετικών διανυσμάτων δεν είναι πολλαπλάσιο του 2016

.

Αν τα διανύσματα διαφέρουν σε μια από τις πρώτες τέσσερις συντεταγμένες, τότε αυτό έπεται από το γνωστό λήμμα που λέει ότι αν