Σημεία τομής κύκλων.

panos misiakos · #1

Θεωρούμε

κύκλους στο επίπεδο έτσι ώστε ανά δύο να τέμνονται και ανά τρεις να μην διέρχονται από το ίδιο σημείο. Αρχικά υπάρχει ένα κέρμα σε κάθε σημείο τομής που ορίζουν οι κύκλοι. Δύο παίκτες A,B

παίζουν το εξής παιχνίδι. Ξεκινάει ο

και οι παίκτες παίζουν εναλλάξ αφαιρώντας ένα κέρμα την φορά. Η μόνη προϋπόθεση είναι ότι όταν ένας παίκτης αφαιρεί ένα κέρμα από το σημείο τομής δύο κύκλων , τότε ο άλλος παίκτης στην αμέσως επόμενη κίνηση απαγορεύεται να αφαιρέσει κέρμα από σημείο που ανήκει σε έναν από τους δύο κύκλους (ή και στους δύο ). Ένας παίκτης χάνει όταν δεν μπορεί να πραγματοποιήσει επιπλέον κίνηση. Να βρείτε τα

για τα οποία ο

έχει στρατηγική νίκης.

#2

Έχουμε

δυάδες $\{i,j\}$ με $1 \leqslant i,j \leqslant n$ και $i \neq j$ . Την δυάδα $\{i,j\}$ θα την χρησιμοποιήσω δύο φορές, από μία για κάθε ένα σημείο τομής των κύκλων C_i

και

.

Το παιχνίδι λέει ότι κάθε παίκτης επιλέγει μια δυάδα που έχει επιλεχθεί το πολύ μία φορά αρκεί κανένα από τα στοιχεία της δυάδας του να μην ισούται με κάποιο από τα στοιχεία της δυάδας που επέλεξε ο άλλος παίκτης στην αμέσως προηγούμενη κίνηση. Αν κάποιος παίκτης δεν μπορεί να κινηθεί χάνει.

Για n=3

είναι προφανές πως κερδίζει ο πρώτος

αφού επιλέγει την $\{1,2\}$ και ο

δεν μπορεί να κάνει τίποτα.

Θα δείξω ότι για κάθε $n \geqslant 4$ κερδίζει ο

.

Αρχικά ο

χωρίζει τις πιο πάνω δυάδες σε ζεύγη ως εξής:

(α) Την δυάδα $\{i,j\}$ με $|i-j| \neq 1,n-1$ την βάζει μια φορά με την δυάδα $\{i+1,j+1\}$ και μια με την $\{i-1,j-1\}$ . Εδώ όλες οι πράξεις είναι $\bmod n$ .

(β) Την δυάδα $\{i,i+1\}$ την βάζει μια φορά με την $\{i+2,i+3\}$ και μια με την $\{i-2,i-1\}$ . [Επιτρέπεται διότι $n \geqslant 4$ .]

Τώρα έχουμε n(n-1)/2

ζεύγη δυάδων. Κάθε φορά που ο

επιλέγει μία δυάδα, ο

επιλέγει μια άλλη που βρίσκεται στο ίδιο ζεύγος με την δυάδα του

και διαγράφει αυτό το ζεύγος. Οπότε όταν το παιγνίδι τελειώσει πρέπει να είναι η σειρά του

να κινηθεί και ο

δεν χάνει όπως θέλαμε να δείξουμε.

$\rule{300pt}{1pt}$

Αν γνωρίζουμε το θεώρημα του γάμου., δεν χρειάζεται καν να κάνουμε την κατασκευή. Βάζουμε στην ομάδα

τα ζεύγη $\{i,j\}$ από μία φορά το κάθε ένα και στην ομάδα

τα ίδια ζεύγη από μία φορά το κάθε ένα. Συνδέουμε ένα ζεύγος του

με ένα ζεύγος του

αν και μόνο αν τα δύο ζεύγη δεν έχουν κοινό στοιχείο.

Αρκεί να βρούμε ένα πλήρες ταίριασμα για να χρησιμοποιήσουμε την προηγούμενη στρατηγική. Κάθε κορυφή είτε του

είτε του

έχει βαθμό ακριβώς d = (n-2)(n-3)/2

. Είναι όμως απλή συνέπεια του θεωρήματος του γάμου ότι κάθε διμερές γράφημα όπου όλες οι κορυφές έχουν τον ίδιο βαθμό έχει ένα πλήρες ταίριασμα. Το αφήνω ως άσκηση.

Σημεία τομής κύκλων.

Σημεία τομής κύκλων.

Re: Σημεία τομής κύκλων.

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