Συνδιαστική

Petros N. · #1

Έχουμε $\frac{n(n+1)}{2}$ κέρματα πάνω σε ενα τραπέζι χωρισμένα σε κάποιες στήλες. Μια κίνηση αποτελείται απο την αφαίρεση ενός νομίσματος απο κάθε στήλη που έχει τουλάχιστον ένα νόμισμα και επανατοποθέτηση των νομισμάτων αυτών σε μια καινούρια στήλη. Να αποδειχθεί οτι μετά από κάποιες κινήσεις θα καταλήξουμε με

στήλες που θα έχουν 1,2,...,n

νομίσματα η κάθε μια.

#2

Δύσκολο!!!!

Βοηθάει να σκεφτούμε την διαδικασία ως εξής:

Μπορούμε να σκεφτούμε κάθε φάση της διαδικασίας ως ένα διάνυσμα $(n_1,\ldots,n_k)$ όπου έχουμε

μη στήλες με $n_1,\ldots,n_k$ νομίσματα αντίστοιχα, με όλα τα n_i

μη μηδενικά.

Κάθε κίνηση γίνεται σε δύο βήματα

Βήμα 1: Από το διάνυσμα $(n_1,\ldots,n_k)$ πάμε στο διάνυσμα $(k,n_1-1,\ldots,n_k-1)$ .
Βήμα 2: Αν το διάνυσμα που πάρουμε στο πρώτο βήμα έχει κάποια μηδενικά στοιχεία τα διαγράφουμε.

Π.χ. αν έχουμε στήλες με 5,3,1,1,2,3

νομίσματα αντίστοιχα, ξεκινάμε από το διάνυσμα (5,3,1,1,2,3)

. Στο πρώτο βήμα αυτό γίνεται (6,4,2,0,0,1,2)

. Στο δεύτερο βήμα γίνεται (6,4,2,1,2)

. Αυτό είναι το τέλος της πρώτης κίνησης στην δεύτερη κίνηση θα καταλήξουμε στο διάνυσμα (5,5,3,1,1)

μέσω του

κ.τ.λ.

Αν έχω ένα διάνυσμα $v = (n_1,\ldots,n_k)$ ορίζω το βάρος του ως $\displaystyle{ w(v) = \sum_{i=1}^k [(n_i+i)^2 - i^2].}$

Λήμμα 1: Μετά από κάθε βήμα 1, το βάρος του διανύσματος παραμένει το ίδιο.

Απόδειξη: Αν $v = (n_1,\ldots,n_k)$ τότε μετά από το βήμα 1 θα πάρουμε το διάνυσμα $v' = (k,n_1-1,\ldots,n_k-1)$ . Απλός έλεγχος δείχνει ότι τα δύο βάρη ισούνται.

Λήμμα 2: Μετά από κάθε βήμα 2, το βάρος του διανύσματος μειώνεται εκτός και αν όλα τα μηδενικά στοιχεία του νέου διανύσματος βρίσκονται στο τέλος του διανύσματος.

Απόδειξη: Χρησιμοποιούμε τον ισοδύναμο τύπο $\displaystyle{ w(v) = \sum_{i=1}^k n_i(n_i+2i)}$ . Μπορούμε να σπάσουμε το βήμα 2 σε πιο μικρά βηματάκια όπου αν έχουμε n_i = 0

και $n_{i+1} \neq 0$ εναλλάσσουμε τα n_i

με τα $n_{i+1}$ . Είναι άμεσο ότι σε κάθε τέτοιο βηματάκι το βάρος θα μειωθεί. [Η διαφορά των βαρών θα ισούται με $n_{i+1}(n_{i+1}+2(i+1)) - n_{i+1}(n_{i+1}+2i) = 2in_{i+1} > 0$ .]

Επειδή το βάρος είναι πάντα μη αρνητικός ακέραιος από ένα σημείο και μετά το βάρος θα παραμείνει σταθερό και άρα πάντα όταν εφαρμόζουμε το βήμα 1, τα μηδενικά στοιχεία θα εμφανίζονται στο τέλος του διανύσματος. Θα ονομάζουμε ένα τέτοιο διάνυσμα τελικό διάνυσμα. (Μπορεί να υπάρχουν πολλά τελικά διανύσματα.)

Λήμμα 3: Για κάθε τελικό διάνυσμα $(n_1,\ldots,n_k)$ και κάθε $1 \leqslant i < j \leqslant k$ ισχύει ότι $n_i - n_j \geqslant (j-i-1)$ .

Απόδειξη: Θα δουλέψουμε με επαγωγή στο j-i

. Για

, θέλουμε να δείξουμε ότι $n_i \geqslant n_{i+1}$ . Ας υποθέσουμε ότι αυτό δεν ισχύει. Ας υποθέσουμε λοιπόν ότι $n_i < n_{i+1}$ . Μετά όμως από t=n_i

κινήσεις θα έχουμε $n_{i+t} = 0$ και $n_{i+1+t} = n_{i+1} - t > 0$ . Οπότε τα μηδενικά στοιχεία δεν εμφανίζονται στο τέλος, άτοπο.

Γνωρίζουμε τώρα λοιπόν ότι για κάθε τελικό διάνυσμα έχουμε $n_1 \geqslant n_2 \geqslant \cdots \geqslant n_k$ .

Για το επαγωγικό βήμα υποθέτουμε ότι ο ισχυρισμός ισχύει για $j-i \leqslant r-1$ . Θα δείξουμε ότι ισχύει και για j-i = r

.

Ας υποθέσουμε λοιπόν ότι $n_i - n_{i+r} < (r-1)$ . Μετά από $t=n_{i+r}-1$ κινήσεις, θα έχουμε $n_1 \geqslant n_2 \geqslant \cdots \geqslant n_{i+r+t} = 1$ και $n_{i+t} - 1< r-1$ , δηλαδή $n_{i+t} \leqslant r-1$ . Στην επόμενη κίνηση θα έχουμε n_1 = i+r+t

και $n_{i+t+1} \leqslant r-2$ .

Αν r=2

τότε είναι $n_{i+t+1} = 0$ οπότε έχουμε το πολύ i+t

μη μηδενικά στοιχεία και στην επόμενη κίνηση θα είναι $n_1 \leqslant i+t$ ενώ n_2 = i+r+t-1 = i+t+1 > n_1

, άτοπο.

Αν r>2

εφαρμόζουμε s=r-3

κινήσεις για να λάβουμε $n_{s+1} = i+r+t-s = i+t+3$ και $n_{i+t+s+1} = 1$ . Στην επόμενη κίνηση $n_{s+2} = i+t+2$ και $n_{i+t+s+2} = 0$ . Δηλαδή θα έχουμε το πολύ i+t+s+1

στοιχεία. Οπότε στην επόμενη κίνηση θα είναι $n_1 \leqslant i+t+s+1$ αλλά $n_{s+3} = i+t+1$ . Όμως τότε για i'=1,j'=s+3

έχουμε

αλλά $n_{i'} - n_{j'} = s < j'-i'-1$ , άτοπο από την επαγωγική υπόθεση.

Λήμμα 4: Για κάθε τελικό διάνυσμα $(n_1,\ldots,n_k)$ και κάθε $1 \leqslant i < j \leqslant k$ ισχύει ότι $n_i - n_j \leqslant (j-i+1)$ .

Απόδειξη: Έστω ότι έχουμε $n_i - n_j \geqslant j-i+2$ για κάποια i < j

. Μετά από t=n_j

κινήσεις έχουμε $n_{i+t} = n_i -t \geqslant j-i+2$ . Επιπλέον έχουμε το πολύ j+t-1

μη μηδενικά στοιχεία. Οπότε στην επόμενη κίνηση είναι $n_1 \leqslant j+t-1$ ενώ $n_{i+t+1} \geqslant j-i+1$ . Τότε όμως για i'=1,j'=i+t+1

έχουμε $n_{i'} - n_{j'} \leqslant t+i-2 = j' - i' - 2$ κάτι που αντιβαίνει το λήμμα 3.

Έστω λοιπόν ένα τελικό διάνυσμα $(n_1,\ldots,n_k)$ της διαδικασίας. Μπορούμε να υποθέσουμε ότι n_k=1

, αλλιώς κάνουμε κάποιες επιπλέον κινήσεις.

Από τα λήμματα

και

για κάθε $1 \leqslant i \leqslant k-1$ είναι n_i = (k-i+1) + m_i

όπου $m_i \in \{0,1,-1\}$ και επιπλέον δεν μπορούμε να έχουμε m_i = 1

και

για κάποια $i \neq j$ . Οπότε είναι $|m_1 + \cdots + m_{k-1}| \leqslant k-1$ και άρα

$\displaystyle{ n_1 + \cdots + n_k \geqslant \frac{k(k+1)}{2} - (k-1) > \frac{k(k-1)}{2} }$

και

$\displaystyle{ n_1 + \cdots + n_k \leqslant \frac{k(k+1)}{2} + (k-1) < \frac{(k+1)(k+2)}{2} }$

Όμως $\displaystyle{ n_1 + \cdots + n_k \geqslant \frac{n(n+1)}{2} }$ οπότε πρέπει k=n

. Τότε όμως πρέπει $m_1 + \cdots + m_{k-1} = 0$ και επειδή δεν μπορούμε να έχουμε κάποιο m_i

θετικό και κάποιο άλλο αρνητικό, πρέπει m_i = 0

για κάθε

. Άρα σε αυτό το βήμα έχουμε

στήλες με $1,2,\ldots,n$ νομίσματα αντίστοιχα όπως θέλαμε να δείξουμε.

$\rule{300pt}{1pt}$

Πιο γενικά, με ελάχιστη διαφοροποίηση στο τέλος, αν έχουμε

νομίσματα όπου N = n(n+1)/2 + r

με $0 \leqslant r < n+1$ τότε κάθε τελικό διάνυσμα είναι της μορφής $(n+m_1,n-1+m_2,\ldots,1+m_n,m_{n+1})$ όπου ακριβώς

από τα

ισούνται με 1 και τα υπόλοιπα ισούνται με 0.

Petros N. · #3

Φοβερή λύση!! Περιμενά να υπάρχει κάτι πιο απλό με ενα invariant αλλά δεν βρήκα κάτι...

chris · #4

Πρόκειται για το Deterministic Bulgarian Solitaire αν δεν κάνω λάθος που είχε γίνει γνωστό από τον Gardner στη δεκαετία του 80.

http://perso.ens-lyon.fr/eric.thierry/Articles/bulg.pdf

#5

Ευχαριστούμε Χρήστο. Το πέτυχα πρόσφατα και εδώ αλλά αμέλησα να το αναρτήσω σκοπεύοντας να το διαβάσω πρώτα και μετά ξεχνώντας το.

Συνδιαστική

Συνδιαστική

Re: Συνδιαστική

Re: Συνδιαστική

Re: Συνδιαστική

Re: Συνδιαστική

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