Νομίσματα και πίνακες

simantiris j. · #1

Θεωρούμε ένα $10\times 10$ πίνακα.Σε κάθε κίνηση τοποθετούμε από ένα νόμισμα στα 4 τετράγωνάκια που σχηματίζονται από την τομή δυο (όχι απαραίτητα διαδοχικών) σειρών με δυο (όχι απαραίτητα διαδοχικές) στήλες.Μια κίνηση μπορεί να γίνει αν τουλάχιστον ένα από τα 4 τετράγωνα δεν έχει νομίσματα.Να βρεθεί ο μέγιστος αριθμός κινήσεων που μπορούν να γίνουν αν στην αρχή δεν υπάρχουν νομίσματα στον πίνακα.

#2

Επαναφορά!

#3

Δεν μου αρέσει και πολύ η απόδειξή μου αλλά αυτήν κατάφερα να βρω.

Θα δείξω ότι η απάντηση για ένα $m \times n$ πίνακα είναι το πολύ (m-1)(n-1)

τοποθετήσεις.

Αυτές οι τοποθετήσεις είναι εύκολο να επιτευχθούν ως εξής: Αρχικά γεμίζουμε τις πρώτες δύο σειρές με n-1

κινήσεις. Μετά συμπληρώνουμε τις πρώτες δυο στήλες με άλλες m-2

κινήσεις. Στο υπόλοιπο (m-2)(n-2)

κομμάτι του πίνακα δεν έχει ακόμη τοποθετηθεί νόμισμα. Σε κάθε επιπλέον κίνηση μπορούμε να γεμίζουμε μόνο ένα καινούργιο κελί χρησιμοποιώντας την πρώτη σειρά και πρώτη στήλη. Άρα συνολικά μπορούμε να κάνουμε
$\displaystyle{ (n-1) + (m-2) + (m-2)(n-2) = (n-1) + (m-2)(n-1) = (m-1)(n-1)}$
τοποθετήσεις.

Θα δείξω τώρα με επαγωγή στο m+n

ότι δεν μπορούμε να κάνουμε περισσότερες τοποθετήσεις. Για m=1

ή

είναι απλό. Για m=n=2

είναι επίσης απλό. Έστω λοιπόν ότι έχω ένα $m \times n$ πίνακα. Από συμμετρία μπορώ να υποθέσω ότι $m \geqslant n$ . Έστω ότι το αποτέλεσμα ισχύει για τους $(m-1) \times n$ .

Ας υποθέσουμε ότι μπορώ να κάνω (m-1)(n-1)+1

τοποθετήσεις. Σε κάθε τοποθέτηση υπάρχει τουλάχιστον ένα καινούργιο νόμισμα. Για κάθε τοποθέτηση επιλέγω ένα από τα καινούργια νομίσματα και μαρκάρω το κελί του. Οπότε έχω ένα $m \times n$ πίνακα με (m-1)(n-1) + 1

μαρκαρισμένα κελιά.

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

Ας υποθέσω τώρα ότι κάθε σειρά έχει δύο αμαρκάριστα κελιά. Τότε έχω μαρκαρισμένα το πολύ
$\displaystyle{m(n-2) = (m-1)(n-1) + n-m-1 < (m-1)(n-1)}$
κελιά, άτοπο.

Άρα υπάρχει μια σειρά η οποία έχει μαρκαρισμένα όλα τα κελιά της εκτός από ένα. Χωρίς βλάβη της γενικότητας η πρώτη σειρά έχει όλα τα κελιά της μαρκαρισμένα εκτός από το τελευταίο. Αυτό σημαίνει ότι όποτε χρησιμοποιώ την πρώτη σειρά σε κάποια κίνηση θα μαρκάρω και κελί αυτής της σειράς. (Αλλιώς θα είχε τουλάχιστον δύο μη μαρκαρισμένα κελιά.) Δηλαδή έχω χρησιμοποιήσει την πρώτη σειρά ακριβώς n-1

φορές.

Τότε όμως αγνοώντας όλες τις n-1

κινήσεις που χρησιμοποιούν την πρώτη σειρά, θα μου μείνουν
$\displaystyle{ [(m-1)(n-1)-1] - (n-1) = (m-2)(n-1)+1}$
κινήσεις που θα λάβουν χώρα στον $(m-1) \times n$ πίνακα που προκύπτει αν αγνοήσω την πρώτη σειρά. Αυτό όμως είναι άτοπο από την επαγωγική υπόθεση.

Νομίσματα και πίνακες

Νομίσματα και πίνακες

Re: Νομίσματα και πίνακες

Re: Νομίσματα και πίνακες

Μέλη σε σύνδεση