Σωρός από πέτρες

MoV · #1

έχουμε έναν σωρό από $n \geq 1$ πέτρες . Μεταβαίνουμε στο

.

αν υπάρχουν

σωροί της μίας πέτρας τότε σταματάμε αλλιώς μεταβαίνουμε στο

.

επιλέγουμε έναν σωρό με τουλάχιστον

πέτρες . Μεταβαίνουμε στο

.

διαχωρίζουμε τον επιλεγμένο σωρό σε

νέους σωρούς ο ένας εκ των οποίων περιλαμβάνει $s_i \geq 1$ πέτρες και ο άλλος περιλαμβάνει $r_i \geq 1$ πέτρες . Μεταβαίνουμε στο

.

Δείξετε ότι το βήμα

θα εκτελεσθεί n-1

φορές και ότι $\displaystyle{ \sum_{i=1}^{n-1}s_ir_i=\frac{n(n-1)}{2} }$ .

nickthegreek · #2

Να δώσω την σκέψη μου στο 1ο ερώτημα,το δεύτερο τώρα θα το κοιτάξω...

Ξεκινάμε με μικρές απλοποιήσεις για να κατανοήσουμε το πρόβλημα.Ορίζουμε ως f(n)

τον αριθμό των φορών που πραγματοποιείται το βήμα (3) σε έναν σωρό με

πέτρες.Έχουμε:

1)Έστω ότι n=1

.Τότε

2)Για

.Tότε

3) $n=3 \Rightarrow f(n)=2$
Άρα εικασία μας ότι f(n)=n-1

.Θα δείξουμε την πρόταση αυτή με την μέθοδο της τέλειας επαγωγής:
α)Η πρόταση ισχύει για n=1,n=2

κτλ.
β)Υποθέτουμε ότι ισχύει για όλα τα $n\in N$ με $n\leq k$ ,για κάποιο $k\in N$
γ)Θα αποδείξουμε ότι ισχύει και για n=k+1

.

Έστω ένας σωρός με k+1

πέτρες.Την πρώτη φορά πραγματοποίησης του βήματος (3),ο ένας σωρός θα διασπαστεί σε δύο νέους σωρούς με $\alpha$ και $k+1-\alpha$ πέτρες σε κάθε σωρό αντίστοιχα.Από εδώ και πέρα,το βήμα (3) θα πραγματοποιηθεί άλλες
$f(\alpha) +f(k+1-\alpha )$ φορές.Οπότε θα ισχυεί ο τύπος $f(k+1)=1+f(\alpha )+f(k+1-\alpha )$ για κάθε
$\alpha \in N :\alpha \leq k$ .

Τέλος μένει να αποδείξουμε ότι για κάθε $\alpha \leq k$ ,το άθροισμα $f(\alpha )+f(k+1-\alpha)$ παραμένει σταθερό!!!!
Πράγματι από το επαγωγικό βήμα έχουμε ότι $f(\alpha )+f(k+1-\alpha) =\alpha -1+k+1-\alpha -1=k-1$ ,σταθερό!!!
Οπότε f(k+1)=1+k-1=k=(k+1)-1

και το ζητούμενο εδείχθη επαγωγικά!!!
Ελπίζω να μην έχω χάσει κάπου...

nickthegreek · #3

Μετά το προβλεπόμενο διάλειμμα για μεσημεριανό επιστρέφουμε στο Mathematica

Προχωράμε στο δεύτερο σκέλος του προβλήματος.

Ορίζουμε ως p(n)

το ζητούμενο άθροισμα $\sum_{i=1}^{n-1} s_{i}r_{i}$ .Πάλι κάνουμε κατάλληλες απλοιποιήσεις για να ξεκινήσουμε...Ισχύουν ότι:
1) p(1)=0

2)

Πάμε να βρούμε το p(3)

.H σωρός των τριών πετρών θα διασπαστεί σε δύο σωρούς των 2 και μιας πέτρας αντίστοιχα. $1\times 2=2$ .
Η σωρός των δύο συνεχίζει για δεύτερη φορά και φτάνει στο βήμα τρία όπου διασπάται σε δύο σωρούς της μίας πέτρας. $1\times 1=1$ .Άρα
p(3)=2+1=3

.Eικασία μας ότι $p(n)=\frac{n(n-1)}{2}$ .Θα το δείξουμε αυτό πάλι με την μέθοδο της τέλειας επαγωγής.

1)Ισχύει για n=1

,

2)Υποθέτουμε ότι ισχύει για όλα τα $n\leq \lambda$ ,όπου λ φυσικός.
3)Θα αποδείξουμε ότι ισχύει και για $n= \lambda+1$ .Έστω μια σωρός αρχική από $\lambda+1$ πέτρες.Αυτή στο πρώτο βήμα διασπάται σε δύο σωρούς από $\alpha$ και $\lambda +1-\alpha$ πέτρες,για κάποιο $\alpha \leq \lambda$ .Aπό αυτό βγάζουμε το συμπέρασμα ότι $p(\lambda +1)=\alpha (\lambda +1-\alpha)+p(\alpha)+p(\lambda+1-\alpha)$ .Αρκεί να βρούμε λοιπόν την τιμή του $p(\lambda +1)$ .

Έχουμε από το επαγωγικό βήμα ότι $p(\alpha )=\frac{\alpha (\alpha -1)}{2}$ και
$p(\lambda +1-\alpha )=\frac{(\lambda -\alpha)(\lambda +1-\alpha )}{2}$ .Άρα μετά από πράξεις έχουμε ότι
$p(\lambda +1)=\frac{\lambda (\lambda +1)}{2}$ και άρα το ζητούμενο εδείχθη!
Πάλι ελπίζω να μην έχω κάνει κάποιο λάθος...
Φιλικά

#4

Να προσθέσω και μια συνδιαστική λύση:

Έστω t_i

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

και έστω

ο αρχικός αριθμός ζευγαριών από πέτρες που βρίσκονται στην ίδια σωρό. Τότε $t_0 = \binom{n}{2}, t_{n-1} = 0$ και για κάθε $1 \leqslant i \leqslant n-1$ έχουμε $t_i = t_{i-1} - r_is_i$ αφού μετά το βήμα

ακριβώς

ζευγάρια από πέτρες δεν βρίσκονται πλέον στην ίδια σωρό.

Άρα $\displaystyle{ \sum_{i=1}^{n-1} r_is_i = \sum_{i=1}^{n-1} (t_{i-1} - t_i) = t_0 - t_{n-1} = \binom{n}{2}}$

Σωρός από πέτρες

Σωρός από πέτρες

Re: Σωρός από πέτρες

Re: Σωρός από πέτρες

Re: Σωρός από πέτρες

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