Παιχνίδι σε πλέγμα

[ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ]

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

[ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ]

Επαναφορά, δεν είναι δύσκολη

[Demetres]

Με 1 άτομο κερδίζει ο Κόκης αλλιώς κερδίζει ο Καρλίτος.

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

Επεξεργασία: Το υπογραμμισμένο προστέθηκε αργότερα κατόπιν παρατήρησης του Πρόδρομου.

Αν υπάρχουν δύο μέλη μπορούν να πιάσουν τον Κόκη ως εξής. Αρχικά κινούνται ώστε να βρεθούν στις πρώτες δύο θέσεις (από αριστερά) της πρώτης (από πάνω) γραμμής. Στις επόμενες λίγες κινήσεις τους κινούνται και οι δύο ένα βήμα δεξιά μέχρι τουλάχιστον ένας από αυτούς να βρίσκεται στην ίδια στήλη με τον Κόκη. Ακολούθως κινούνται ως εξής: Αν ένας από αυτούς βρίσκεται στην ίδια στήλη με τον Κόκη κινούνται προς τα κάτω. Αλλιώς, ο Κόκης στο τελευταίο του βήμα πρέπει να κινήθηκε είτε αριστερά είτε δεξιά. Τότε κάνουν και οι δύο το ίδιο βήμα. Παρατηρούμε ότι δεν μπορούν να κάνουν συνέχεια βήματα αριστερά και δεξιά. Ο Κόκης δεν μπορεί να κινείται συνέχεια αριστερά ή συνέχεια δεξιά. Επίσης κάθε φορά που ο Κόκης αλλάζει από αριστερά σε δεξιά και αντίστροφα, τα δύο μέλη θα κινηθούν προς τα κάτω. Άρα εν τέλει θα τον πιάσουν.

[ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ]

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

Αυτό το σημείο νομίζω χρειάζεται λίγη προσοχή, αν για παράδειγμα ο Κόκης εφαρμόσει μια στρατηγική τύπου "κουνιέμαι πάντα προς μια στήλη στην οποία δεν υπάρχει εχθρός, και αν στην ήδη υπάρχουσα δεν υπάρχει μένω εδώ" είναι εύκολο να δούμε ότι χάνει, π.χ ο Καρλίτος κινείται ώστε να βρεθεί στην ίδια σειρά με τον Κόκη και μετά τον πλησιάζει μέχρι την διπλανή στήλη, η στρατηγική του Κόκη του λέει ότι είναι ασφαλής όσο ο Καρλίτος δεν είναι στην ίδια στήλη, τότε όμως ο Καρλίτος τον πιάνει. Φυσικά και πάλι η κατασκευή στρατηγικής για τον Κόκη όταν έχει μόνο έναν εχθρό είναι απλή υπόθεση.

Μια εύλογη επέκταση:

Να λυθεί το ίδιο πρόβλημα στη περίπτωση που το παιχνίδι παίζεται σε ένα -διάστατο πλέγμα πλευράς .

[Demetres]

Έχεις απόλυτο δίκαιο Πρόδρομε. Το διόρθωσα.