Κινήσεις στο επίπεδο

Γιάννης Μπόρμπας · #1

Στο επίπεδο, ονομάζουμε "ακέραια" τα σημεία που έχουν ακέραιες συντεταγμένες. Ο Νίκος και ο Θανάσης παίζουν το εξής παιχνίδι: Αρχικά, ο Νίκος επιλέγει ένα ακέραιο σημείο, και στην συνέχεια επιλέγει και ο Θανάσης ένα ακέραιο σημείο, διαφορετικό από αυτό του Νίκου. Ο σκοπός του παιχνιδιού είναι ο Νίκος από το σημείο που επέλεξε, να καταφέρει να φτάσει στο σημείο του Θανάση, μέσω κινήσεων. Σε κάθε κίνηση, ο Νίκος μπορεί να μεταβεί από το σημείο

στο σημείο

εάν:
1) Το σημείο

είναι ακέραιο
2) Η απόσταση

είναι ακέραιος
3) Το ευθύγραμμο τμήμα

δεν είναι παράλληλο στους άξονες
Να βρεθεί η ελάχιστη τιμή του

, έτσι ώστε ανεξάρτητα από την επιλογή ακέραιου σημείου του Θανάση, ο Νίκος μπορεί να φτάσει στο σημείο του Θανάση, κάνοντας το πολύ

κινήσεις.

#2

Θα δείξω ότι γίνεται για n=3

αλλά όχι για n=2

.

Ας δούμε πρώτα πως γίνεται για n=3

:

Χωρίς βλάβη της γενικότητας A = (0,0)

και

για κάποια $a,b \in \mathbb{Z}$ . Θα επιλέξουμε κατάλληλα $x,y,z \in \mathbb{Z}$ και θα κάνουμε βήματα στις κατευθύνσεις (3x,4x),(5y,12y),(24z,7z)

. Αυτό επιτρέπεται επειδή τα βήματά μας έχουν μήκη 5x,13y,25z

αντίστοιχα.

Είναι απλό να ελεγχθεί (παραλείπω τις πράξεις για το πως έφτασα σε αυτό) ότι με την επιλογή x = 64a-364b,y=-19a+108b,z=-4a+23b

καταλήγουμε πράγματι στο (a,b)

.

Θα δείξω τώρα ότι δεν μπορώ με δύο βήματα να καταλήξω από το (0,0)

στο

.

Αν μπορώ αυτό σημαίνει ότι θα υπάρχουν $r,s \in \mathbb{Z}$ ώστε τα r^2 + s^2

και

είναι τέλεια τετράγωνα. [Αν πρώτα κάνω το βήμα (r,s)

μετά πρέπει να κάνω το βήμα (-r,-s+1)

.

Έστω ότι r^2 + s^2 = t^2

με

. Αφού $r \neq 0$ , πρέπει |s| < t

. Τότε όμως, για s > 0

έχουμε

$\displaystyle r^2 + (s-1)^2 < r^2 + s^2 = t^2$ και $\displaystyle r^2 + (s-1)^2 = r^2 + s^2 - 2s +1 = t^2 - 2s+1 > t^2 - 2t + 1 = (t-1)^2$

Άρα το

δεν μπορεί να είναι τέλειο τετράγωνο. Ομοίως καταλήγουμε σε άτοπο αν s < 0

. (Από τις συνθήκες είναι $s \neq 0$ .)

Κινήσεις στο επίπεδο

Κινήσεις στο επίπεδο

Re: Κινήσεις στο επίπεδο

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