forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 24 Νοέμ 2017, 02:09

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 12 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 09 Αύγ 2014, 19:56 
Χωρίς σύνδεση
Forum Moderator

Εγγραφη: 19 Ιαν 2014, 22:08
Δημοσ.: 268
Τοποθεσια: Νίκαια
Μετά από μήνυμα ένα πολύ πιο δύσκολο πρόβλημα πάνω σε παρόμοιες ιδέες.
Έχουμε μια σκακιέρα 8x8. Σε αυτήν διαλέγουμε n τετράγωνα στα όποια βάζουμε πιόνι. Από εκεί και πέρα, κάθε τετράγωνο που έχει δύο τετράγωνα με πιόνια γειτονικά του (όπου γειτονικά εννοούμε πάνω αριστερά δεξία ή κάτω, όχι διαγώνια) παίρνει πιόνι και η διαδικασία επαναλαμβάνεται συνεχώς. Κάποια στιγμή δεν υπάρχουν καινούρια τετράγωνα που να πρέπει να πάρουν πιόνι.
Η ερώτηση είναι: Ποιο είναι το ελάχιστο n που απαιτείται ώστε με αυτό τον τρόπο να καλύψουμε όλη τη σκακιέρα με πιόνια?

_________________
\int_{M} \mathrm{d}\omega =\int_{\partial M} \omega


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 19 Αύγ 2014, 11:37 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Μιας και πέρασαν τόσες μέρες και δεν δόθηκε ακόμα απάντηση:

Να δειχθεί ότι για το παραπάνω πρόβλημα το ζητούμενο n είναι 8.

(ή γενικότερα για την k x k σκακιέρα το ζητούμενο n είναι k)


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 26 Αύγ 2014, 14:03 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Για την 1x1 σκακιέρα το 1 πιόνι είναι το ελάχιστο δυνατό.

Έστω τώρα ότι για την kxk σκακιέρα το ελάχιστο n είναι k, τότε θα δείξω ότι το ελάχιστο n για την (k+1)x(k+1) είναι το k+1.

Ισχυρισμός: Το ελάχιστο n για την (k+1)x(k+1) ικανοποιεί την σχέση: n \in \{k, k+1\}.

Απόδειξη ισχυρισμού: Προφανώς: το n δεν μπορεί να είναι μικρότερο για την (k+1)x(k+1) σκακιέρα, άρα: n \geq k.

Επιλέγουμε k πιόνια και μια τοποθέτηση τους που γεμίζει την kxk υπό-σκακιέρα της (k+1)x(k+1) σκακιέρας. Τότε, αν μετά από κάποια βήματα γεμίσει η σκακιέρα έπεται ότι n=k, αλλιώς τοποθετώντας ένα ακόμα πιόνι στο ελεύθερο τετράγωνο της κύριας διαγωνίου (θα είναι ελεύθερο καθώς αν δεν ήταν και είχαμε γεμίσει την kxk υπό-σκακιέρα της (k+1)x(k+1) σκακιέρας η σκακιέρα θα γέμιζε) τότε η σκακιέρα θα γεμίσει (θα βοηθούσε ένα σχήμα σε αυτό το σημείο). Άρα n=k+1 σε αυτή τη περίπτωση.

Τέλος της απόδειξης:

Έστω προς άτοπο, ότι υπάρχει ένα k τέτοιο ώστε το ελάχιστο n για την (k+1)x(k+1) σκακιέρα να είναι k. Τότε τοποθετούμε τα k πιόνια στη (k+1)x(k+1) σκακιέρα. Καθώς με k πιόνια γεμίζει η kxk υπό-σκακιέρα της (k+1)x(k+1) σκακιέρας, και επίσης με από την υπόθεση γεμίζει και η (k+1)x(k+1) σκακιέρα, έπεται ότι κάποτε θα πάρει πιόνι και το ελεύθερο τετράγωνο της κύριας διαγωνίου. Από εδώ προκύπτει το άτοπο, καθώς δεν μπορεί να πάρει πιόνι αυτό το τετράγωνο, καθώς θα έπρεπε πρώτα να γεμίσουν τα γειτονικά του, τα οποία πάλι δεν μπορούν να πάρουν πιόνι καθώς θα έχουν μόνο ένα γειτονικό τετράγωνο με πιόνι. (Πάλι εδώ θα βοηθούσε ένα σχήμα)


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 02 Σεπ 2014, 09:20 
Χωρίς σύνδεση
Forum Moderator

Εγγραφη: 19 Ιαν 2014, 22:08
Δημοσ.: 268
Τοποθεσια: Νίκαια
Altair δεν είμαι σίγουρος για αυτό που λες. Για παράδειγμα, πάρε την 3χ3 σκακιέρα με όλες τις γωνίες πιασμένες (που χρησιμοποιεί παραπάνω πιόνια αλλά πληροί τις προυποθέσεις σου), εκεί θα γεμισει η σκακιέρα. Πάντως η απάντηση είναι όντως n :P

_________________
\int_{M} \mathrm{d}\omega =\int_{\partial M} \omega


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 02 Σεπ 2014, 11:11 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Δεν καταλαβαίνω που είναι το πρόβλημα.

Για την 3x3 λέω ότι θα γίνεται ή με 2 ή με 3 πιόνια και έπειτα αποκλείω το να γίνεται με 2. Το 4 που κολλάει?


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 02 Σεπ 2014, 18:01 
Χωρίς σύνδεση
Forum Moderator

Εγγραφη: 19 Ιαν 2014, 22:08
Δημοσ.: 268
Τοποθεσια: Νίκαια
Μπορεί τα 4 να είναι πολλά, αλλά επειδή με δύο όντως δεν γίνεται να φέρεις αντιπαράδειγμα σε αυτό που λες (και αυτό επειδή η άσκηση ισχύει) φέρνω (νομίζω) με 4. Εδω, υπάρχει ένα ελεύθερο τετράγωνο στη διαγώνιο, όλη του τη στήλη και γραμμή κενές (το μεσαίο). Παρόλα αυτά αυτό το τετράγωνο στο τέλος θα πάρει πιόνι. Αλλιώς, μπορείς το ίδιο παράδειγμα να το κάνεις σε μια 5χ5 σκακιέρα που δε θα γεμίσει ολόκληρη αλλά και πάλι το τετράγωνο πο λες ότι θα μείνει άδειο θα γεμίσει.

_________________
\int_{M} \mathrm{d}\omega =\int_{\partial M} \omega


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 02 Σεπ 2014, 18:47 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Δεν καταλαβαίνω και πάλι που είναι το πρόβλημα.

Παραπάνω, μιλάω για το ελεύθερο τετράγωνο της διαγωνίου, στα τετράγωνα που θα μείνουν όταν βγάλεις την kxk υπό-σκακιέρα από την (k+1)x(k+1) σκακιέρα.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 02 Σεπ 2014, 20:09 
Χωρίς σύνδεση
Forum Moderator

Εγγραφη: 19 Ιαν 2014, 22:08
Δημοσ.: 268
Τοποθεσια: Νίκαια
Ναι αλλά πως ξέρεις ότι για οποιαδήποτε διάταξη k πιονιών μπορείς να βγάλεις αυτήν την kxk σκακιέρα? ας πουμε στο 5x5 παραδειγμα με τα τετραγωνα (1,5),(5,1),(1,1),(5,5) να χουν πιονια ποια ειναι η kxk σκακιερα

_________________
\int_{M} \mathrm{d}\omega =\int_{\partial M} \omega


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 02 Σεπ 2014, 21:39 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Λογικά δεν κατάλαβες το:
Altair έγραψε:
Επιλέγουμε k πιόνια και μια τοποθέτηση τους που γεμίζει την kxk υπό-σκακιέρα της (k+1)x(k+1) σκακιέρας.


Δηλαδή πρώτα γεμίζεις μια kxk σκακιέρα με k πιόνια και έπειτα βλέπεις την kxk σκακιέρα που γέμισες ως υπό-σκακιέρα της (k+1)x(k+1).

Τα τετράγωνα (1,5),(5,1),(1,1),(5,5) της 5x5 σκακιέρας δεν μπορεί να έχουν επιλεγεί.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 04 Σεπ 2014, 18:08 
Χωρίς σύνδεση
Forum Moderator

Εγγραφη: 19 Ιαν 2014, 22:08
Δημοσ.: 268
Τοποθεσια: Νίκαια
Μα ρε συ εσυ ψαχνεις να αποδείξεις ότι ΔΕΝ γίνεται να την γεμίσεις με k πιόνια ολόκληρη, με οποιονδήποτε σχηματισμό... Δεν είναι απαραίτητο να ξεκνάς με την λογική γεμίζω την kxk σκακιέρα. Αυτό θα ήταν μια αρχή λύσης αν αποδείκνυες ότι με k γίνεται να την γεμίσεις, αλλά τώρα απλά ελέγχεις κάποιους σχηματισμούς, εκείνους που είναι τέτοιοι ώστε τα πιόνια να είναι στην kxk σκακιέρα.

_________________
\int_{M} \mathrm{d}\omega =\int_{\partial M} \omega


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 04 Σεπ 2014, 18:50 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Μα επαγωγή κάνω. Ξεκινάω με το ότι η kxk γεμίζει με k πιόνια και δείχνω ότι η (k+1)x(k+1) γεμίζει με k ή με k+1 πιόνια και έπειτα απορρίπτω την περίπτωση των k πιονιων.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Πρόβλημα με σκακιέρα
ΔημοσίευσηΔημοσιεύτηκε: 05 Σεπ 2014, 14:43 
Χωρίς σύνδεση
Forum Moderator

Εγγραφη: 19 Ιαν 2014, 22:08
Δημοσ.: 268
Τοποθεσια: Νίκαια
Altair το θέμα είναι ότι υπάρχει μια ασάφεια... Εξηγείς πολύ καλά γιατί δεν μπορεί να υπάρχει τοποθέτηση με k πιόνια τα οποία βρίσκονται σε μια kxk σκακιέρα. Οκ. Επειδή όμως σκοπός είναι να δείξεις ότι δεν υπάρχει ΚΑΜΙΑ τοποθέτηση με k πιόνια που να καλύπτει τη σκακιέρα, εξήγησε μου σε ποιο σημείο της επιχειρηματολογίας σου αποκλείεται ο σχηματισμός (1,5),(1,1),(5,1),(5,5). Αν το θέμα είναι ότι έτσι δεν καλύπτεται η 4χ4 σκακιέρα, τότε θα μπορούσε να υπάρχει ένας σχηματισμός με τον οποίο αυτή θα καλυπτόταν, χωρίς όμως όλα τα αρχικά πιόνια να ανήκουν στην kxk σκακιέρα. Πχ αν βάζαμε μερικά, περισσότερα από k πιόνια (γιατί πράγματι σαυτήν την περίπτωση είναι αδύνατον αλλά για άλλους λόγους) θα μπορούσαμε να φτιάξουμε ένα σχηματισμό που να καλύπτει τη σκακιέρα αλλά να μην υπακούει στον κανόνα που λες.

_________________
\int_{M} \mathrm{d}\omega =\int_{\partial M} \omega


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 12 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group