Ο Γρίφος του Las Vegas ©

chessboard 

Ο παρακάτω γρίφος είναι αποτέλεσμα δικής μου κατασκευής και οφείλει την ύπαρξη του στα δημιουργικά κενά της αναμονής, που εμφανίζονται συχνά πυκνά στην έντονη καθημερινότητά μου. Η πηγή της έμπνευσης του είναι μεγάλη και αστεία ιστορία, την οποία όμως δεν θα σας πω, παρα μόνο όταν λύσετε το γρίφο! Ειδάλλως, θα σας προδώσω έμμεσα τη λύση του…

Γρίφος στο Las Vegas: Ένας διάσημος αρχιτέκτονας σας φέρνει αντιμέτωπο με το εξής παράξενο πρόβλημα. Σε μία αχανή ερημική έκταση, λίγο έξω από το Las Vegas, έχει κάνει μία τεράστια κατασκευή στο έδαφος. Η κατασκευή, μοιάζει με σκακιέρα με τις μόνες διαφορές ότι είναι ορθογώνια (αντί για τετράγωνη) και ότι οι διαστάσεις της είναι μεγάλες και άγνωστες (αντί για 8×8). Παρ’ όλα αυτά, αποτελείται από τετράγωνα όπως ακριβώς μία σκακιέρα. (Ένα παράδειγμα τέτοιας κατασκευής είναι μία “σκακιέρα” διαστάσεων 200×150 που (άρα) διαθέτει 30.000 τετράγωνα).

Ο Αρχιτέχτονας έχει στη διάθεση του τόσες ταμπέλες, όσα και τα τετράγωνα της σκακιέρας του. Κάθε ταμπέλα είναι αριθμημένη, με την αρίθμηση να ξεκινάει από το 1. (Για παράδειγμα, αν η “σκακιέρα” ήταν όπως παραπάνω, τότε θα είχαμε 30.000 ταμπέλες αριθμημένες από το 1 έως το 30.000). Φυσικά, αφού δεν γνωρίζετε το μέγεθος της “σκακιέρας”, το πλήθος των ταμπελών σας είναι επίσης άγνωστο. Οι ταμπέλες προορίζονται για να τοποθετηθούν στη “σκακιέρα”, μία σε κάθε τετράγωνο.

Η πρόκληση του Αρχιτέκτονα έχει ως εξής: Πρώτα σας δίνει τη δυνατότητα να με συναντήσετε για να καταστρώσουμε ένα στρατηγικό σχέδιο. Στη συνέχεια, οδηγεί εμένα στο Las Vegas όπου και τοποθετώ τις ταμπέλες (μία σε κάθε τετράγωνο!) σύμφωνα με το σχέδιο που καταστρώσαμε. Ακολούθως, αφαιρεί όλες τις ταμπέλες πλην από 4 που αντιστοιχούν σε συνορεύοντα τετράγωνα (δηλαδή σε τετράγωνα που σχηματίζουν μία σκακιέρα 2×2). Το ποιες ταμπέλες θα αφαιρέσει είναι δική του επιλογή (αρκεί στο τέλος, να μην πειράξει τέσσερις, οι οποίες και θα ανήκουν σε κάποια 2×2 σκακιέρα). Τέλος, σας οδηγεί μπρος σ’ αυτή τη 2×2 σκακιέρα όπου και σας ρωτάει: Ποιες είναι οι διαστάσεις της “σκακιέρας”? Κοιτάτε τις 4 ταμπέλες, κάνετε τα μαγικά σας και του δίνετε αμέσως τη σωστή απάντηση!

Το ερώτημα λοιπόν είναι το εξής: Τι διαβολικό στρατηγικό σχέδιο καταστρώσαμε?

Bonus Ερώτημα: Τι χρειάζεται ν’ αλλάξει στην παραπάνω στρατηγική έτσι ώστε να μπορείτε πάντα να βρίσκετε και τις συντεταγμένες σας, ως προς κάποιο από τα 4 γωνιακά τετράγωνα του οικοδομήματος? (Προσοχή!)   

Και για να μην ξεχνιόμαστε: Δε θέλω παγαποντιές!

(Σημείωση: Η πρώτη σωστή λύση δόθηκε από τον “Paschouale” και υπάρχει στα σχόλια)

Marble_Chess_Board

Advertisements

20 Σχόλια

  1. Paschouale said,

    Μαΐου 6, 2009 στις 4:01 πμ

    Άκου τι σκέφτηκα! Δεν είναι σωστό αλλά τα σπάει…
    Με αυτό τον τρόπο μπορώ να βρω το συνολικό αριθμό των πλακακίων αλλά μόνο αν στο σύνολο είναι περιττóς αριθμός.

    Πως πρέπει να τα τοποθετήσει:

    for(i=1;i<=max;i+=2)
    {
    printf(«%d»,i);
    printf(«%d»,max-i);
    }

    Έτσι έστω ότι είναι συνολικά 15 δηλαδή 3χ5…
    Τότε θα έμπαιναν ως εξής:
    1 14 3 12 5
    10 7 8 9 6
    11 4 13 2 15
    Όποια τετράδα και αν πάρεις: αν κάνεις πρόσθεση στη γραμμή στην οποία είναι πρώτος ο περιττός τότε βγάζεις το συνολικό αποτέλεσμα.
    πχ.
    8 9
    13 2
    Που είναι 1ος περιττός στην 2η γραμμή άρα 13 + 2 = 15 ….
    😛 Μαλακία αλλά δεν μπορούσα να μην το γράψω…

  2. Duncan said,

    Μαΐου 6, 2009 στις 4:20 πμ

    Nice! Real nice!

    Η κατασκευή σου χρησιμοποιεί λίγο πολύ το κόλπο του Gauss (βλέπε υπολογισμό του 1+2+…+n) αλλά σε δύο διαστάσεις!

    Μπορεί να μη λειτουργεί, αλλά έχει σίγουρα χαβαλέ. Καλά έκανες και το ανέβασες…

    Το ‘ξερα ότι θα εξάψει τη φαντασία αυτό το πρόβλημα!

    Good job 😉

  3. gvaranx said,

    Μαΐου 6, 2009 στις 2:15 μμ

    Εσυ και τα πονηρα σου σχεδια! Ζαλιστηκα μονο και μονο που διαβασα τα δεδομενα… Θα (απο)τρελανεις τους τρελαμενους..

  4. Duncan said,

    Μαΐου 6, 2009 στις 2:28 μμ

    Γι’ αυτό δεν ήμαστε εδώ άλλωστε? Για να φανταζόμαστε να προκαλούμε να ζαλίζουμε να κινούμε και ν’ αλλάζουμε?

    Πάντως για την ιστρορία, η διατύπωση του προβλήματος είναι πιο απλή απ’ ότι φαίνεται. Στην ουσία σε ρωτάει:

    Πώς θα πρέπει να τοποθετήσεις τις ταμπέλες έτσι ώστε να μπορείς να βρεις τις διαστάσεις του οικοδομήματος, κοιτάζοντας μόνο οποιεσδήποτε «γειτονικές» τέσσερις!

    Τα υπόλοιπα είναι εφέ και διευκρινήσεις για τον πιο απαιτητικό αναγνώστη. 🙂

  5. Paschouale said,

    Μαΐου 7, 2009 στις 4:15 πμ

    Για να παίξουμε μπαλίτσα να δούμε τι ψάρια θα ποιάσουμε…(zdoing)!!!

    Λοιπόν αυτή η στρατιγική έχει ως εξής:
    Χωρίζουμε τα πλακάκια τα μισά άσπρα και τα άλλα μισά μαύρα. Δηλαδή αν έχουμε 30.000 από το 1-15000 άσπρα και από το 15001 μέχρι το 30000 μαύρα.Για το παράδειγμα μας θα χρησιμοποιησω 30.
    Τα 1-15 άσπρα τα 16-30 μαύρα.

    Τοποθετεί πάντα το ένα μαύρο από την αρχή και ένα μάυρο από το τέλος.
    Άρα για τα 30 θα βγει έτσι:
    1 30 2 29 3 28 4 27 5 26
    25 6 24 7 23 8 22 9 21 10
    11 20 12 19 13 18 14 17 15 16

    Αμ=άσπρο μονό Αζ=άσπρο ζυγό Μμ=μαύρο μονό Μζ=μαύρο ζυγό

    Έστω οποιαδήποτε 2 συνεχόμενα νουμεράκια σαν ζευγάρι.
    Αν εχουμε Αμ Μζ ή Μμ Αζ ή Μζ Αμ ή Αζ Μμ τότε κάνοντας το άθροισμα Αμ+Μζ-1 βρίσκω πάντα το σύνολο.
    Αν έχουμε Αμ Μμ ή Αζ Μζ τότε κάνοντας το άθροισμα Αμ+Μμ βρίσκω πάντα το σύνολο.
    Αν έχουμε Μμ Αμ ή Μζ Αζ τότε κάνοντας το άθροισμα Μμ+Αμ-2 βρίσκω πάντα το σύνολο.

    Λοιπόν με αυτό τον τρόπο όποιο 2χ2 και αν σου δώσει βρίσκεις το σύνολο από οποιαδήποτε από τις 2 γραμμές…

    Για να βρεις τώρα το πόσο επί πόσο είναι το μόνο που κάνεις είναι να κάνεις αφαίρεση τις διαγωνίους(απόλυτη) και πρόσθεση μεταξύ τους.

    πχ: μου δίνει το κομμάτι :
    8 22
    18 14
    Τι είπαμε…. αν Αζ Μζ τοτε το σύνολο είναι μόνο το άθροισμα τους άρα 8+22 = 30
    Πόσο επί πόσο όμως:
    |8-14|+|18-22| = 6+4 = 10 (Με αυτό τον τρόπο βρίσκουμε τον αριθμό των στυλών)
    Άρα μετά κάνουμε 30/10 = 3
    Και του λέμε με σιγουριά πια.. είναι 3×10

    Για να βρούμε τώρα τις συντεταγμένες παίρνουμε ένα οποιοδήποτε άσπρο τετράγωνο από τα 2 που έχουμε το πολλαπλασιάζουμε χ2 και μετά κάνοντας μαγικά (αφού γνωρίζουμε τον αριθμό των στυλών το βρίσκουμε). Στο παράδειγμα μας:
    Παίρνουμε το 8 το κάνουμε χ2 σημαίνει οτι βρίσκετε στην 16 θέση… ε αφού κάθε σειρά έχει 10 στύλες σημαίνει οτι βρίσκεται στην 2η σειρά 6 στύλη. (2,6).

  6. Duncan said,

    Μαΐου 7, 2009 στις 7:25 μμ

    Πολύ ευρηματικός ως συνήθως! Πώς όμως αντιμετωπίζεις το περιττό γινόμενο? Πχ:

    Έστω η σκακιέρα 3×3 (κ γενικά οποιαδήποτε περιτού «εμβαδού»).
    Τότε η προτεινόμενη κατασκευή δίνει

    1 9 2
    8 3 7
    4 6 5

    Έστω επίσης το εξής 2×2:

    1 9
    8 3

    Τότε το (1,9) είναι Μμ και Αμ ==> οπότε 1+9 πρέπει να κάνει 9…

    Έχε υπόψη σου ότι δεν γνωρίζεις εκ των προτέρων αν το γινόμενο των διαστάσεων θα είναι μονό η ζυγό…

    ΥΓ.: (Η λύση που δίνεις για άρτιο γινόμενο είναι πέρα για πέρα σωστή!)

  7. Paschouale said,

    Μαΐου 7, 2009 στις 9:27 μμ

    Δεν χρειαζόταν διόρθωση τα μικρά είναι τα άσπρα.
    Στο παράδειγμα που είχα…
    8 22 8 είναι το άσπρο ζυγό, 22 το μαύρο ζυγό:
    άρα σύμφωνα με την διόρθωση: 8 + 22 -2 =28
    πριν : 8 + 22 = 30
    Θα το ψάξω απλά σήμερα έχω να σπάσω και την κρυπτογράφηση των κωδικών του msn :P. Χρησιμοποιούν αλγόριθμο κρυπτογράφησης SHA… Αυτός είναι γρίφος… Πως σπάει ο SHA :D!!! Ξεκινάμε…

  8. Duncan said,

    Μαΐου 7, 2009 στις 9:57 μμ

    🙂

    Είπες ότι ξεκινάς από 1-μαύρο ή κάνω λάθος?

    Άκυρο το μήνυμα!

    Με μπέρδεψε το «1 μαύρο» που είχες γράψει παραπάνω. Θα αλλάξω αυτό…

  9. Paschouale said,

    Μαΐου 7, 2009 στις 10:00 μμ

    Και όμως το βρήκα υπάρχει και ποιο εύκολος τρόπος….
    Τα βάζεις όπως τα έβαλα και πριν…
    Σου δίνει το 2χ2… Κάνεις την πάνω σειρά πρόσθεση… κάνεις την κάτω:
    Αν έχουν μεταξύ τους διαφορά 1 αφαιρείς από το μεγαλύτερο το 2 και βρίσκεις το σύνολο.
    πχ. στο 3χ3 του Duncan :
    1 9 =10
    8 3 =11
    11 – 2 = 9
    Αν είναι ίσα αφαιρείς το 1 από οποιοδήποτε:
    π.χ στο δικό μου παράδειγμα:
    1 30 = 31
    25 6 = 31
    31 – 1 = 30
    Αν έχουν διαφορά 2 παίρνουμε το μικρότερο:
    π.χ στο δικό μου παράδειγμα:
    30 2 = 32
    6 24 = 30
    30…

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

  10. Duncan said,

    Μαΐου 7, 2009 στις 10:08 μμ

    Σωστός!

    Well done! 😉

    ΥΓ.: Και καλή επιτυχία με τον SHA!

  11. Paschouale said,

    Μαΐου 7, 2009 στις 10:26 μμ

    Thank you very much…
    Waiting for your next riddle…

  12. Duncan said,

    Μαΐου 7, 2009 στις 10:58 μμ

    Θα προσθέσω όλες εκείνες τις λεπτομέρειες που (ορθά) βαριέσαι να γράψεις 😉

    Έστω ότι η σκακιέρα μας έχει διαστάσεις m x n. Τότε διακρίνουμε τις εξής περιπτώσεις:

    1) m = περιττό
    Τότε όλες οι 2×2 σκακιέρες έχουν σταθερό άθροισμα 2mn + 3 (που είναι περιττός αριθμός!)

    2) m = άρτιο
    Τότε όλες οι 2×2 σκακιέρες έχουν σταθερό άθροισμα 2mn + 2 (που είναι άρτιος αριθμός!)

    Οπότε, όταν ο Αρχιτέκτονας διαλέξει για μας μια σκακιέρα (2×2) εμείς θα αθροίσουμε όλους τους αριθμούς από όλες τις ταμπέλες και θα κοιτάξουμε το άθροισμα.

    Αν είναι άρτιο, αφαιρούμε πρώτα 2, διαιρούμε μετά με το 2 και έχουμε το γινόμενο μας!

    Αν είναι περιττό, αφαιρούμε πρώτα 3, διαιρούμε μετά με το 2 και έχουμε το γινόμενο μας!

    Μένει να προσδιορίσουμε το πλήθος των στηλών.

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

  13. Paschouale said,

    Μαΐου 8, 2009 στις 2:21 πμ

    Δήλωσες:
    Η πηγή της έμπνευσης του είναι μεγάλη και αστεία ιστορία, την οποία όμως δεν θα σας πω, παρα μόνο όταν λύσετε το γρίφο! Ειδάλλως, θα σας προδώσω έμμεσα τη λύση του…

    Περιμένω την αμοιβή μου 😛

  14. Duncan said,

    Μαΐου 8, 2009 στις 3:10 πμ

    Χαχαχα! Ναι σωστά…

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

    Οπότε όπως καταλαβαίνεις, κάθε τέτοια μέρα έχω μία εσωτερική διαμάχη ανάμεσα στο να κοιμηθώ όσο το δυνατόν περισσότερο και στο να μη φτάσω αργοπορημένος. Είναι λογικό, ότι μετά από τόσο καιρό έχω βρει την κατάλληλη φόρμουλα και συνήθως φτάνω just για μάθημα.
    Παρόλα αυτά, μια στο τόσο, φτάνω είτε ελαφρώς καθυστερημένος είτε ελαφρώς νωρίτερα. Το πρώτο δεν είναι και τόσο μεγάλο πρόβλημα αλλά το δεύτερο είναι πολύ ενοχλητικό (ο «χαμένος χρόνος» και γω δεν τα πάμε πολύ καλά). Ειδικά όταν έχω μπροστά μου περίπου 10 λεπτά στο ρολόι. (Υπερβολικά πολύς χρόνος για να κάτσεις και να περιμένεις, ελάχιστος χρόνος για να κάνεις σχεδόν το οτιδήποτε). Έτσι φροντίζω να τον γεμίζω με τις σκέψεις μου!

    Μία Πέμπτη λοιπόν, εχω φτάσει ελαφρά νωρίτερα για μάθημα και αποφασίζω – τι άλλο – ν’ αράξω απ’ έξω από την τάξη και να περιμένω να πάει μία. Όπως λοιπόν έχω καθήσει στο πάτωμα και σκέφτομαι διάφορα, πέφτει το μάτι μου στην άλλη μεριά του τοίχου οπου βρίσκονται στοιβαγμένα δεκάδες ντουλαπάκια σε φάση «mini locker rooms». Σε κάθε στήλη υπήρχαν καμιά δεκαριά ντουλαπάκια και όλα είναι στοιχειοθετημένα κι αριθμημένα κάτα στήλη! Παρόλα αυτά, με μία ματιά δεν φαινόταν επακριβώς πόσα ντουλαπάκια υπήρχαν σε κάθε στήλη… Που να κάτσω να μετρήσω και γω? (Είπαμε να σκοτώσουμε την ώρα μας αλλά όχι κι έτσι!) Οπότε διαβάζω το αριθμημένο ταμπελάκι από ένα ντουλάπι, κάνω το ίδιο και με το διπλανό του, κάνω μετά και την αφαίρεση και bingo! Βρήκαμε τον αριθμό των ντουλαπιών στην κάθε στήλη χωρίς την επίπονη διαδικασία του μετρήματος…

    Τα υπόλοιπα, είναι καθώς λένε ιστορία. Μου πήρε μία ώρα (στο γυμναστήριο) να κάνω τις απαραίτητες γενικεύσεις και να βρω μια κάθως πρέπει «άκυρη» ιστορία να τον ντύσω… 🙂

  15. Paschouale said,

    Μαΐου 10, 2009 στις 9:54 μμ

    Ωραίος…
    Εγώ νόμιζα οτί ήταν αληθινή ιστορία :P!!

    Άσχετο, είναι δυνατόν η φατσούλα που έχω να είναι πράσινη???
    Την θέλω κόκκινη παρακαλώ :P!!!

  16. Duncan said,

    Μαΐου 10, 2009 στις 10:19 μμ

    Χαχαχαχαχα! Δεν έχω φτάσει ακόμα στο σημείο να εμπιστεύομαι τυχαίους «αρχιτέκτονες» που αναφέρονται σε Random κατασκευές στο Las Vegas…

    Δυστυχώς, το Avatar δεν μπορεί ν’ αλλάξει γιατί προέρχεται από έναν αυτόματο generator της wordpress… Αλλά τι σε χαλάει? Η φάτσα είναι όλα τα λεφτά!

  17. Paschouale said,

    Μαΐου 11, 2009 στις 2:48 πμ

    Ναι σιγά, πλάκα έκανα, πάλι καλά είναι αστεία…. 😀

  18. Zakacid said,

    Μαρτίου 20, 2010 στις 4:26 μμ

    δεν κοιταξα αν έχει αναφερθει παραπάνω με αυτον τον τρόπο

    αν ξεκινήσουμε με μια σκακιέρα Ν τετραγωνων βάζοντας τις ταμπέλες με τον εξης τρόπο

    1 ν 2 (ν-1) 3 (ν-2) …. κ (ν-κ+1)
    μ (ν-μ+1) (μ+1) (ν-μ) ………
    για ζυγο πλήθος στηλών

    τότε το ανα δυο άθροισμα της σειρας βγάζει ή ν+1 ή ν+2 αλλά η απο κάτω δυαδα θα έχει αθροισμα ν+1 ή ν αντίστοιχα

    αρα κάθε τετράδα τετραγωνικης μορφης θα έχει άθροισμα 2ν+2

    στην περίπτωση περιττού αριθμού στηλών η διάταξη θα είναι κ’άποως έτσι

    1 ν 2 (ν-1) 3 (ν-2) ….. (ν-κ+2) κ
    (ν-κ+1) (κ+1) (ν-κ) (κ+2)….

    εδω πάλι στην πρώτη σειρά (και στην τριτη και στην 5η κτλ.) έχουμε ανα δυαδα αθροισματα ν+1 ή ν+2 αλλα τα αθροισματα των απο κάτω δυάδων είναι ν+2 ή ν+1 αντοιστιχα …
    και το συνολικο αθροισμα της τετράδας είναι 2ν+3

    γι αυτο πρέπει να βρουμε τρόπο να ξεχωρίσουμε αυτες τις δυο περιπτώσεις….

    ευκολο … αφου το 2ν+2 είναι άρτιος ενω το 2ν+3 περιττός

    αρα με αυτον τον τρόπο αθροιζουμε όλο το τετράγωνο που μας αφήνει ο αρχιτέκτονας κι αν είναι αρτιο αφαιρούμε 2 και διαιρουμε δια του 2 αν είναι περιττος αφαιτουμε 3 και διαιρουμε δια του 2 κι έχουμε το μεγεθος της σκακιέρας…

  19. Zakacid said,

    Μαρτίου 20, 2010 στις 4:32 μμ

    αλλα οπως είδα μόλις το έχεις εξηγησει με παρόμοιο τρόπο παραπάνω…

    Υ.Γ.
    πολυ καλη και απλη σκέψη αυτη με την επιστροφη προς τα πάνω εγω αρχικα είχα χαθει ψαχνοντας που να δινει τις συντεταγμενες τις σκακιέρας…

  20. Duncan said,

    Μαρτίου 21, 2010 στις 9:21 μμ

    Zakacid, η σκέψη σου είναι απόλυτα σωστή!

    Επίσης, το γεγονός ότι η λύση έχει ήδη αναφερθεί παραπάνω είναι παντελώς άσχετο για μένα. Ξέρω ότι πολύς κόσμος δεν την διαβάζει καν, στην προσπάθεια να βρει μία μόνος του. Γι’ αυτό και γω αντιμετωπίζω κάθε λύση σαν νέα… 🙂

    Ως τέτοια λοιπόν, η δική σου λύση είναι σωστή…


Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Αρέσει σε %d bloggers: