Τετράγωνο απόστασης

#1

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

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

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

.

WLOG · #2

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

harrisp · #3

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

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

#4

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

Έστω αρχικά ότι έχω τουλάχιστον $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

.

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

πρώτος με $p \equiv 3 \bmod 4$ και p|(x^2+y^2)

τότε

και

.

Έστω λοιπόν ότι τα δυο διανύσματα διαφέρουν στην πέμπτη ή έκτη συντεταγμένη. Έστω a = x_1-x_2

και

και ότι είτε $4 \nmid a$ είτε $8 \nmid a+b$ . Θέλω να δείξω ότι $32 \nmid a^2+b^2$ .

Έστω λοιπόν ότι 32|a^2+b^2

. Τότε

οπότε οι

είναι άρτιοι. Έστω a=2c,b=2d

. Τότε

οπότε οι

είναι επίσης άρτιοι, έστω c=2e,d=2f

. Τότε

οπότε

. Τότε

και

οπότε

και

. Άτοπο αφού υποθέσαμε ότι αυτό δεν συμβαίνει.

Τετράγωνο απόστασης

Τετράγωνο απόστασης

Re: Τετράγωνο απόστασης

Re: Τετράγωνο απόστασης

Re: Τετράγωνο απόστασης

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