Προβλήματα Μαθηματικών

Ιουνίου 17, 2008

Κινούμενα κενά

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 9:52 μμ

Στην παραπάνω εικόνα βλέπετε ένα συνηθισμένο τύπο puzzle. Στο κενό τετραγωνάκι μπορεί κάθε φορά να μετακινηθεί ένα οποιοδήποτε από τα γειτονικά του τετράγωνα.

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

Advertisements

6 Σχόλια »

  1. Παραθέτω δύο links για όποιον ενδιαφέρεται να μάθει περισσότερα για την ιστορία αυτού του προβλήματος, καθώς και μία σελίδα για τον μεγάλο συνθέτη προβλημάτων Σαμ Λοιντ.
    Προειδοποιήση: Το πρώτο link περιέχει τη λύση, οπότε αν θέλετε να προσπαθήσετε μόνοι σας μην το ανοίξετε! (Εγώ ήξερα το πρόβλημα από παλιότερα, οπότε δε θα κάνω τον έξυπνο λέγοντας την…)

    http://en.wikipedia.org/wiki/Fifteen_puzzle
    http://en.wikipedia.org/wiki/Sam_Loyd

    Μου αρέσει!

    Σχόλιο από sonzi — Ιουνίου 18, 2008 @ 12:04 πμ

  2. sonzi:

    Η λύση που περιγράφεται στα links που δίνεις είναι πολύ δυσνόητη.

    Θα ήταν καλό αν κάποιος μας την περιέγραφε εδώ σε ξακάθαρη μορφή.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 18, 2008 @ 12:12 πμ

  3. Να πω δύο λόγια για το πώς δείχνουμε ότι δε γίνεται να πάμε στην τελική κατάσταση που περιγράφεται στο ερώτημα από την αρχική που φαίνεται.

    Κατ’ αρχήν, υπάρχουν 16 αντικείμενα, οι 15 αριθμοί και το κενό, τα οποία αλλάζουν θέση με κάθε μας πράξη. Είναι σημαντικό ότι κάθε μας πράξη είναι αντιμετάθεση του κενού με ένα από τους (το πολύ) 4 γείτονές του.

    Ας υποθέσουμε ότι υπάρχει μια πεπερασμένη ακολουθία t_1,\ldots,t_n από τέτοιες πράξεις μετά από τις οποίες το αποτέλεσμα είναι το επιθυμητό (όλα στη θέση τους με τα 1 και 2 αλλαγμένα). Τα t_1, \ldots, t_n είναι στοιχεία της ομάδας S_{16} των μεταθέσεων 16 στοιχείων, και η σύνθεσή τους είναι

    t_n \cdot t_{n-1} \cdots t_1 = (1\ 2)

    όπου με (1 2) συμβολίζουμε τη μετάθεση που αλλάζει τα 1 και 2 και αφήνει τα άλλα απείραχτα.

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 28, 2008 @ 7:42 μμ

  4. Ιδέα:
    Εφόσον η μετάθεση (1 2) είναι περιττή, 8α πρέπει
    και το αριστερό μέλος της ισότητας να είναι περιττή
    μετάθεση. Με άλλα λόγια εφόσον κάθε τ(ι)
    συμβολίζει μία αντιμετάθεση 2 αριθμών, το δεξί
    μέλος μας λέει ότι πρέπει να πάμε στην τελική
    κατάσταση με περιττό πλήθος αντιμεταθέσεων.

    Το άδειο λοιπόν αρχικό τετράγωνο μετακινείται μέσα στον πίνακα, ακολουθεί μία πορεία και καταλήγει πάλι εκεί απ’ όπου ξεκίνησε. Αν έχει μετακινηθεί a θέσεις προς αριστερά, b προς τα δεξιά, c προς τα κάτω και d προς τα πάνω, τότε πρέπει να μετακινηθεί ακριβώς a θέσεις προς τα δεξιά, b προς τα αριστερά, c προς τα πάνω και d προς τα κάτω για να επιστρέψει στην αρχική θέση.

    Δηλαδή σε κάθε περίπτωση χρειαζόμαστε άρτιο
    πλήθος κινήσεων το οποίο περιγράφεται ως
    γινόμενο άρτιου πλήθους αντιμεταθέσων, δηλαδή,
    είναι μια αρτια μετάθεση, ενώ η (1 2) είναι περιττή.
    Καταλήγουμε λοιπόν σε άτοπο.

    Μία άλλη σκέψη είναι είναι να μην
    χρησιμοποιήσουμε άμεσα το γεγονός ότι η (1 2) είναι μία περιττή μετάθεση.

    Θεωρούμε λοιπόν την τελική κατάσταση εφικτή. Υποθέτουμε ότι το 1 έχει πάει στη θέση του 2, και τα τετράγωνα 3 εως 15 καθώς και το άδειο βρίσκονται στην αρχική τους θέση. Τότε προκύπτει άμεσα ότι το 2 θα έχει πάει στη θέση του 1.

    Μένει να βρούμε αν η παραπάνω κατάσταση προκύπτει με άρτιο ή περιττό πλήθος κινήσεων.

    Παρόμοιος συλλόγισμός όπως και στην περίπτωση του άδειου τετραγώνου, για να πάει το 1 στη θέση
    του 2:
    Το πλήθος των κινήσεων προς τα πάνω αναιρεί
    αυτές προς τα κάτω, αλλά δε συμβαίνει το ίδιο
    με τις αριστερά και δεξία κινήσεις. Αν μετακινηθεί
    συνολικά χ θέσεις προς τα δεξιά τότε θα
    μετακινηθεί μία λιγότερη προς τα αριστερά για
    να πάει στη θέση του 2. Αρα το συνολίκο
    πλήθος κινήσεων για να καταλήξουμε στην
    τελική κατάσταση είναι περιττό.

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

    Καταλήγουμε πάλι σε άτοπο.

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουνίου 29, 2008 @ 1:56 πμ

  5. xatzial:

    Η αρχική σου λύση είναι πολύ σωστή. Μια απλοποίηση όσον αφορά το γιατί το n (πλήθος κινήσεων) είναι αναγκαστικά άρτιο για να γυρίσει το κενό στη θέση του: θεωρείστε τα τετράγωνα βαμμένα ασπρόμαυρα σα σκακιέρα. Τότε σε κάθε κίνηση το κενό γίνεται από άσπρο μαύρο και ανάποδα. Άρα το n είναι άρτιο.

    Η δεύτερή σου λύση όμως δεν είναι σωστή. Ο λόγος είναι ότι δε μπορείς να συμπεράνεις ότι το πλήθος κινήσεων είναι περιττό απλά και μόνο επειδή το 1 (ή το 2) μετακινείται περιττό αριθμό φορών. Μπορεί να υπάρχουν και κινήσεις που δεν μετακινούν το 1 ή το 2. Αυτό το τελευταίο δεν ισχύει για το κενό που μετέχει σε κάθε κίνηση, και γι’ αυτό η πρώτη λύση είναι σωστή.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 29, 2008 @ 8:03 πμ

  6. Πολύ σωστά, πράγματι, οι κινήσεις καθορίζονται από άδειο τετράγωνο, αφού αυτό μετακινείται κάθε φορά.

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουνίου 29, 2008 @ 12:40 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Blog στο WordPress.com.

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