Ο γρίφος της εβδομάδας – Τα παιδία παίζει

1. Έχουμε ν σωρούς που περιέχουν αντιστοίχως α1,α2,…,αν πέτρες και ο Άρης με το Βασίλη, με αυτή τη σειρά, παίζουν εναλλάξ στο ακόλουθο παιχνίδι: κάθε παίχτης στη σειρά του αφαιρεί μία πέτρα από όποιον σωρό θέλει, εκτός από το σωρό από όπου αφαίρεσε πέτρα ο άλλος παίχτης στην αμέσως προηγούμενη κίνηση. Κερδίζει ο παίχτης που παίζει τελευταίος και ο άλλος δεν μπορεί πλέον να παίξει (είτε από έλλειψη επιτρεπτής κίνησης, είτε επειδή τελείωσαν οι πέτρες). Έχει κάποιος από τους δύο παίχτες νικηφόρα στρατηγική; Αν χρειάζεται, διακρίνετε περιπτώσεις.

2. Ο Άρης και ο Βασίλης, παίζοντας εναλλάξ, χρωματίζουν κόκκινες ή πράσινες τις κορυφές ενός κανονικού 99-γώνου ως εξής: πρώτος παίζει ο Άρης που επιλέγει χρώμα σε οποιαδήποτε κορυφή και στη συνέχεια κάθε παίχτης στη σειρά του επιλέγει χρώμα σε οποιαδήποτε κορυφή γειτονεύει με μια ήδη χρωματισμένη κορυφή. Στόχος του Βασίλη είναι, όταν θα έχουν χρωματιστεί όλες οι κορυφές, να σχηματίζεται ισόπλευρο τρίγωνο με τρεις κορυφές του ιδίου χρώματος, ενώ στόχος του Άρη είναι να μην υπάρχει τέτοιο τρίγωνο. Ποιος παίχτης έχει νικηφόρα στρατηγική και γιατί;

7 σχόλια

  1. macgyver

    Μια προσπάθεια για το 2:
    Αρχικά παρατηρούμε ότι ισόπλευρο τρίγωνο προκύπτει με την επιλογή τριών κορυφών που χωρίζονται ανά δύο από 33 πλευρές.
    Οι κορυφές χρωματίζονται έτσι ώστε να είναι διαρκώς χρωματισμένες διαδοχικές.Έστω ότι χρωματίστηκαν με οποιοδήποτε τρόπο οι πρώτες 33.Αυτές τις αριθμούμε διαδοχικά από το 1 μέχρι το 33 και συνεχίζουμε με την ίδια φορά την αρίθμηση μέχρι να φτάσουμε στη τελευταία (πριν την 1) που είναι η 99.Έτσι έχουμε 33 διαφορετικά ισόπλευρα των οποίων οι κορυφές είναι
    1 34 67
    2 35 68
    3 36 69
    .
    .
    .
    .
    31 64 97
    32 65 98
    33 66 99
    Τελευταίος χρωμάτισε την 33 ο Άρης, άρα τώρα παίζει ο Βασίλης έχοντας τη δυνατότητα να χρωματίσει από το 34 ή από το 99 με βάση τους κανόνες που υπάρχουν δηλαδή μετά ο Άρης θα πρέπει να χρωματίσει γειτονικό των χρωματισμένων αριθμών κοκ.Οι δύο παίχτες επομένως χρωματίζοντας τους αριθμούς θα κατεβάζουν την χρωματισμένη δεύτερη στήλη και αντίστοιχα θα ανεβάζουν την τελευταία.Το ζητούμενο του Βασίλη είναι να καταφέρει να χρωματίσει δύο αριθμούς που ανήκουν στην ίδια τριάδα.Χωρίς βλάβη της γενικότητας υποθέτουμε ότι επιλέγει να χρωματίσει το 34 (και όχι το 99) χρωματίζοντας έτσι τον πρώτο αριθμό της δεύτερης στήλης.Αν ο Άρης χρωματίσει το 99 αφήνοντας στον Βασίλη το 35 δηλαδή ο Βασίλης χρωματίσει δύο διαδοχικούς τότε ο Βασίλης θα χρωματίζει στην σειρά του συνεχώς αριθμούς από το πιο κοντινό άκρο στους τρίτους αριθμούς αυτών των τριάδων μέχρι να τους φτάσει και έτσι σίγουρα θα χρωματίσει τουλάχιστον έναν από αυτούς στην τρίτη στήλη καταφέρνοντας να νικήσει.Άρα ο Άρης δεν πρέπει να του επιτρέψει να χρωματίσει δύο διαδοχικούς.Επομένως ο Άρης θα βάψει τον 35,ο Βασίλης τον 36,ο Άρης τον 37 και λοιπά.Η δεύτερη στήλη θα ολοκληρωθεί μόλις ο Βασίλης βάψει τον 66.Σειρά του Άρη που βάφει τον 99 ή τον 67 (έναν περιττό) αφήνοντας στον Βασίλη να βάψει έναν περιττό ή έναν άρτιο στη συνέχεια.Ο Βασίλης στην δεύτερη στήλη έβαψε μόνο άρτιους.Κάθε τριάδα είναι ή
    άρτιος περιττός άρτιος
    ή
    περιττός άρτιος περιττός
    Άρα αν ο Βασίλης βάψει έναν περιττό της τρίτης στήλης νίκησε,αφού έχει αφήσει με το ίδιο χρώμα τους 2 αριθμούς των τριάδων <>. Συνεπώς θα βάψει περιττό (που μπορεί ούτως ή άλλως σε κάποια από τις υπόλοιπες κινήσεις του αν όχι στη ν ακριβώς επόμενη).

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

  2. Pantsik

    1. Αν ο συνολικός αριθμός των πετρών είναι μονός κερδίζει ο Α ενώ αν είναι ζυγός κερδίζει ο Β. Ο Α κερδίζει και στην περίπτωση δύο σωρών με ζυγό συνολικό αριθμό πετρών. Η στρατηγική νίκης του ενός ή του άλλου είναι να παίρνουν πέτρα από το σωρό με τις περισσότερες διαθέσιμες.

    2. Νικηφόρα στρατηγική έχει ο Β. Οι τριάδες ισόπλευρου τριγώνου είναι οι (1,34,67) , (2,35,68,) , … , (33,66,99) οπότε ο Β χρειάζεται μία από αυτές τις τριάδες να είναι ομόχρωμες για να κερδίσει. Χρωματίζουν διαδοχικά ο ένας μετά τον άλλον τις κορυφές μέχρι να χρωματιστούν 32 διαδοχικές κορυφές. Τώρα είναι η σειρά του Α να χρωματίσει. Αν ο Α βάψει την επόμενη κορυφή π.χ. Πράσινη τότε ο Β βάφει Πράσινη την κορυφή στην άλλη άκρη της αλυσίδας. Έτσι έχουμε δύο πράσινες κορυφές με 32 κορυφές ανάμεσά τους, δηλαδή την πρώτη προϋπόθεση για ισόπλευρο τρίγωνο. Στη συνέχεια ο Α βάφει την επόμενη κορυφή με το αντίθετο χρώμα από αυτό που υπάρχει στην άλλη πλευρά της αλυσίδας με 32 θέσεις ανάμεσά τους, αλλά ο Β βάφει την επόμενη με το ίδιο χρώμα με την αντίστοιχή της, κ.ο.κ. Έτσι ανά δύο διαδοχικές κορυφές θα έχουμε ένα ζευγάρι ομόχρωμων κορυφών σε απόσταση 33 μεταξύ τους.
    Τώρα επειδή υπάρχουν δύο διαδοχικές μονές κορυφές (η 99 και η 1) τελικά κάποια στιγμή ο Β θα μπορέσει να ταιριάξει και την τρίτη κορυφή που χρειάζεται και θα έχει φτιάξει ισόπλευρο τρίγωνο με τρεις ομόχρωμες κορυφές.

  3. pantsik

    Μια διόρθωση στο 2: ο Α κερδίζει και στην περίπτωση που οι σωροί είναι περισσότεροι από 2 και το συνολικό πλήθος των πετρων ζυγό, αλλά οι πέτρες του ενός σωρού είναι περισσότερες από το συνολικό πλήθος πετρων των υπολοίπων σωρών.

  4. ΚΣ

    Πρόβλημα 1
    1 σωρός=> κερδίζει ο Α ανεξαρτήτως πλήθους πετρών
    2 σωροί=> α. αν χ=ψ τότε κερδίζει ο Β, β. αν χ>ψ τότε κερδίζει ο Α αφού διαλέγει το σωρό με τις περισσότερες πέτρες, όπου χ και ψ το πλήθος πετρών των δύο σωρών
    3 σωροί και πάνω => α. Αν υπάρχει σωρός με πλήθος πετρών που ξεπερνά το συνολικό πλήθος των πετρών όλων των υπολοίπων σωρών, τότε κερδίζει ο Α, αφού διαλέγει αυτόν.
    β. Αν δεν υπάρχει τέτοιος σωρός, τότε αν το συνολικό πλήθος πετρών είναι μονός αριθμός κερδίζει ο Α, ενώ αν είναι ζυγός αριθμός κερδίζει ο Β.
    Αυτό γίνεται ως εξής=> Έστω ότι έχουμε μονό αριθμό πετρών. Αρκεί να φτιάξει ο παίχτης Α στο μυαλό του μια ομάδα από σωρούς (ενδεχομένως η ομάδα αυτή να εμπεριέχει κι ένα μέρος ενός σωρού) που να ξεπερνά κατά μια πέτρα σε αριθμό συγκριτικά με την άλλη ομάδα. Αυτή τη θεωρεί δική του. Ο παίχτης Α παίρνει από την ομάδα αυτή όσο ο παίχτης Β παίρνει από την άλλη. Αν ο παίχτης Β πάρει από την ομάδα του Α, τότε ο Α παίρνει από την ομάδα του Β. Στόχος του Α είναι μετά από κάθε κίνησή του να αφήνει τις δύο ομάδες με ίδιο αριθμό πετρών.
    Σε περίπτωση που η ομάδα του Α εμπεριέχει εκτός από ολόκληρους σωρούς και ένα μέρος ενός σωρού, παίρνει αρχικά μόνο από αυτόν μέχρι να εξαντληθεί είτε το μέρος της δικής του είτε της “ομάδας” του Β.
    Αν ο συνολικός αριθμός είναι ζυγός με το που παίρνει πρώτος ο Α ο συνολικός αριθμός των πετρών γίνεται μονός και το πλεονέκτημα το παίρνει ο Β.

    Πρόβλημα 2
    Πλεονέκτημα έχει ο Βασίλης.
    Υπάρχουν συνολικά 33 ισόπλευρα τρίγωνα εντός του 99γωνου.
    Παίζει ο Α στο σημείο Χ που το ορίζουμε ως κορυφή 1. Στη συνέχεια ο Β παίζει πάντα απέναντι από τη θέση που παίζει ο παίχτης Α.
    Για παράδειγμα
    Α παίζει στην 1,
    Β παίζει στη 2,
    Α παίζει στη 3,
    Ο Β παίζει απέναντι δηλαδή στην 99.
    Αυτό γίνεται για 16 δικές του κινήσεις (συνολικά έχουν γίνει 32 κινήσεις εκατέρωθεν). Χωρίς να μας ενδιαφέρει η επιλογή του χρώματος.
    Από την επόμενη όμως κίνηση και για συνολικά 32 κινήσεις (16 ο κάθε παίχτης) ο Β παίζει πάλι απέναντι αλλά προσέχει την επιλογή στο χρώμα της κορυφής που βρίσκεται αφού αυτό θα πρέπει να ταιριάζει με το χρώμα της ήδη χρωματισμένης κορυφής που απέχει 33 κορυφές. Μετά από επιπλέον 32 κινήσεις θα υπάρχουν 64 κορυφές συμπληρωμένες (32+32) και 35 κορυφές κενές. Από τις κενές κορυφές, οι 4 συνδέονται με 2 τρίγωνα που έχουν τις δυο κορυφές τους χωρίς χρώμα (ομάδα Χ), 16 κορυφές που αντιστοιχούν σε 16 τρίγωνα που έχουν δύο κορυφές τους συμπληρωμένες με το ίδιο χρώμα (ομάδα Ψ) και 15 κορυφές που αντιστοιχούν σε 15 τρίγωνα που έχουν δύο κορυφές χρωματισμένες με διαφορετικό χρώμα (ομάδα Ω). (Η ομάδα Ω προκύπτει αφού ο παίχτης Α λογικά θα παίζει ακριβώς αντίθετα από τον τρόπο που παίζει ο Β).
    Για το παιχνίδι απομένουν 35 κινήσεις εκ των οποίων οι 18 γίνονται από τον Α και οι 17 από τον Β. Για να χάσει ο Β θα πρέπει όλες τις κινήσεις να τις κάνει στα 15 τρίγωνα που δεν δίνουν μονοχρωμία (ομάδα Ω) και στα 2 τρίγωνα που έχουν τις δύο κορυφές τους ακάλυπτες (ομάδα Χ) και να κάνει από έναν χρωματισμό στο καθένα. Από τη στιγμή όμως που παίζει πρώτος ο Α ο Β μπορεί να αποφύγει να παίξει σε ένα εκ των 2 τριγώνων της ομάδας Χ και πλέον να υπάρχει μια τουλάχιστον κίνηση σε τρίγωνο της ομάδας Ψ.

  5. batman1986

    Στο πρόβλημα 1. πρέπει να διακρίνουμε τις εξής περιπτώσεις

    1. Αν η μεγαλύτερη σε πλήθος πετρών στοίβα έχει περισσότερες πέτρες απο όλες τις υπόλοιπες τότε είτε έχουμε άρττιο είτε περιττο πλήθος πετρών συνολικά, ο Αρης νικάει 100 % απλά τραβώντας συνέχεια πέτρες από αυτήν τη στοίβα.Σε κάποια στιγμή ο Β δεν θα έχει να τραβήξει από τις υπόλοιπες αλλά ούτε και από αυτές της στοίβας που τραβάει ο Α σύμφωνα με τον περιορισμό

    2. Η μεγαλύτερη σε πλήθος στοίβα έχει αριθμό πετρών ίσο ή μικρότερο από όλες τις υπόλοιπες τότε

    α. Αν το πλήθος των σορών είναι άρττιος αριθμός τότε νικηφόρα στρατηγική έχει πάντα ο Β ότι και να κάνει ο Α

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

  6. batman1986

    Γριφος 2.

    Χωρίς να είμαι σίγουρος επειδή δεν πρόλαβα να τον δω πολύ
    θεωρώ πως ο Β έχιε νικηφόρα στρατηγική
    Η λογική του είναι να βάφει ανάποδα στη φορά από τη φορά που βάφει κάθε φορά ο Α
    Ο λόγος είναι ότι αν 32 βήματα για κάθε κορυφή έχουμε πλευρά ισόπλευρου τριγώνου
    Αρα πρέπει ο Β να απαντάει συμμετρικά και με ανάποδο χρώμμα από αυτο που θα βάψει ο Α την προηγούμενη κορυφή…
    Ελπίζω να έχω πιάσει τη λογική τουλάχιστον..

  7. Θανάσης Παπαδημητρίου

    Μπράβο κι ευχαριστώ στους φίλους για τα εμπνευσμένα, ολόσωστα σχόλια / απαντήσεις τους. Ήταν ανεξαιρέτως εξαιρετικά😊!
    Λίγα (αχρείαστα ίσως) λόγια ακόμη από εμένα:

    1. Η στρατηγική του μέγιστου σωρού, που θα μπορούσε και να χαρακτηριστεί ως κοινοτοπία του προφανούς😊, κατά τη γνώμη μου αξίζει να εξηγηθεί κάπως. Ας πάρουμε π.χ. την περίπτωση, όπου ο α1+α2+..+αν είναι περιττός (η συλλογιστική είναι παρόμοια και στις υποπεριπτώσεις της άλλης περίπτωσης):
    Εφόσον ο Άρης αφαιρέσει στην πρώτη του κίνηση πέτρα από μέγιστο σωρό, θα μπορεί και στη δεύτερή του κίνηση να κάνει το ίδιο, αφού στο μεταξύ ο Βασίλης θα υποχρεωθεί να αφαιρέσει πέτρα από άλλον σωρό, ο οποίος έτσι παραμένει μικρότερος ή το πολύ ίσος με το σωρό από όπου αφαίρεσε νωρίτερα πέτρα ο Άρης. Συνεπώς και μετά από την απάντηση του Βασίλη στην πρώτη κίνηση του Άρη, όποια κι αν είναι αυτή, θα μπορεί πάλι ο Άρης να έχει την επιλογή μέγιστου σωρού και ομοίως θα εξακολουθεί να την έχει και στη συνέχεια. Για να χάσει αυτή τη δυνατότητα ο Άρης κάποια στιγμή, θα πρέπει ο ίδιος προηγουμένως να έχει αφαιρέσει πέτρα από σωρό μικρότερο του μεγίστου, οπότε ο Βασίλης θα μπορούσε να έχει αφαιρέσει αμέσως μετά πέτρα από μέγιστο σωρό (και να διατηρήσει το πλεονέκτημα αυτό μέχρι τέλους, αφού ο Άρης θα υποχρεωνόταν από εκεί και πέρα να αφαιρεί συνεχώς πέτρα από σωρό μικρότερο του μεγίστου, μέχρι κάποια στιγμή να μην υπάρχει πέτρα σε σωρό μικρότερο του μεγίστου και άρα να χάσει). Συνεπώς το να αφαιρέσει ο Άρης πέτρα από σωρό μικρότερο του μεγίστου, ενώ μπορεί να αφαιρεί συνεχώς από τον μέγιστο σωρό, θα ήταν αντίθετο στο συμφέρον του, άρα δεν μπορεί να είναι μέρος μιας νικηφόρας στρατηγικής και δεν θα το έκανε ποτέ.

    2. Για να κερδίσει ο Βασίλης αρκεί να προσέξει σε τρείς κινήσεις και συγκεκριμένα την 34η, την 36η και την τελευταία, ενώ οι υπόλοιπες είναι αδιάφορες :
    Στην 34η κίνηση επιλέγει οποιαδήποτε από τις δύο επιτρεπόμενες κορυφές, αλλά επιλέγει το χρώμα της έτσι ώστε οι δύο ακραίες κορυφές της χρωματισμένης περιοχής να έχουν το ίδιο χρώμα. Έστω Χ η αχρωμάτιστη ακόμα κορυφή που μαζί με τις δύο προαναφερόμενες χρωματισμένες σχηματίζουν ισόπλευρο τρίγωνο.
    Στην 36η κίνηση επιλέγει κορυφή στην άλλη πλευρά της χρωματισμένης περιοχής σε σχέση με την πλευρά που διάλεξε ο Άρης στην αμέσως προηγούμενη κίνησή του και την χρωματίζει στο ίδιο χρώμα που έχει η κορυφή που βρίσκεται 33 κορυφές μακρύτερα στην χρωματισμένη περιοχή. Έστω Ψ η αχρωμάτιστη ακόμα κορυφή που μαζί με τις δύο προαναφερόμενες χρωματισμένες σχηματίζουν ισόπλευρο τρίγωνο.
    Οι αχρωμάτιστες κορυφές Χ,Ψ είναι γειτονικές, επομένως ακόμα κι αν ο Άρης χρωματίσει κάποια στιγμή τη μία από αυτές σε ‘απαγορευτικό’ χρώμα, θα μπορέσει αμέσως μετά ο Βασίλης να χρωματίσει την άλλη στο κατάλληλο χρώμα για να κερδίσει..

Αφήστε μια απάντηση

Η ηλ. διεύθυνση σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *