Συνδυαστική ή άλγεβρα;

Συντονιστές: Demetres, silouan

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7805
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Συνδυαστική ή άλγεβρα;

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιουν 08, 2017 11:42 am

Δίνεται θετικός ακέραιος n. Ορίζουμε συνάρτηση f:\mathbb{N}_0 \times \mathbb{N}_0  \to \mathbb{N}_0 ως εξής:

f (0,i)=f (i,0)=0,f (1, 1)=n και \displaystyle{ f(i, j)= \left\lfloor\frac {f(i-1,j)}{2}\right\rfloor+ \left\lfloor\frac {f(i, j-1)}{2}\right\rfloor } για κάθε δύο θετικούς ακέραιους i, j με ij>1.

Να βρεθεί το πλήθος των ζευγών (i,j) για τα οποία ο f (i, j) είναι περιττός.

Την έβαλα στον φάκελο της συνδυαστικής με tag άλγεβρα. Ένα από τα δύο ίσως να αλλάξει μετά την λύση. :)



Λέξεις Κλειδιά:
Άβαταρ μέλους
emouroukos
Γενικός Συντονιστής
Δημοσιεύσεις: 1378
Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
Τοποθεσία: Αγρίνιο

Re: Συνδυαστική ή άλγεβρα;

#2

Μη αναγνωσμένη δημοσίευση από emouroukos » Κυρ Ιουν 18, 2017 10:27 am

Μια αλγεβρική προσέγγιση:

Η βασική παρατήρηση είναι ότι για κάθε x \in \mathbb{Z}

\displaystyle{x - 2\left\lfloor {\frac{x}{2}} \right\rfloor  = \left\{ {\begin{array}{*{20}{c}} 
{0,}&{x \equiv 0\left( {\bmod 2} \right)}\\ 
{1,}&{x \equiv 1\left( {\bmod 2} \right)} 
\end{array}} \right.}.

Θεωρούμε τον πίνακα \displaystyle{X = \left( {f\left( {i,j} \right)} \right)_{i,j = 0}^\infty }. Για κάθε ακέραιο n \ge2 συμβολίζουμε με

\displaystyle{{a_n} = \sum\limits_{i + j = n} {f\left( {i,j} \right)} }

το άθροισμα των στοιχείων της n-οστής διαγωνίου (από πάνω αριστερά προς κάτω δεξιά) του πίνακα X.

Το πλήθος των ζευγών \displaystyle{{\left( {i,j} \right)}} με i+j=n ώστε ο αριθμός \displaystyle{{f\left( {i,j} \right)}} να είναι περιττός είναι ίσο με

\displaystyle{\sum\limits_{i + j = n} {\left( {f\left( {i,j} \right) - 2\left\lfloor {\frac{{f\left( {i,j} \right)}}{2}} \right\rfloor } \right)}  = {a_n} - \sum\limits_{i + j = n} {2\left\lfloor {\frac{{f\left( {i,j} \right)}}{2}} \right\rfloor  = } }

\displaystyle{ = {a_n} - \sum\limits_{i + j = n} {\left( {\left\lfloor {\frac{{f\left( {i - 1,j + 1} \right)}}{2}} \right\rfloor  + \left\lfloor {\frac{{f\left( {i,j} \right)}}{2}} \right\rfloor } \right) = } {a_n} - \sum\limits_{i + j = n} {f\left( {i,j + 1} \right)}  = }

\displaystyle{ = {a_n} - \sum\limits_{i + j = n + 1} {f\left( {i,j} \right)}  = {a_n} - {a_{n + 1}}.}

Συνεπώς, το πλήθος των ζευγών \displaystyle{{\left( {i,j} \right)}} με i+j<n ώστε ο αριθμός \displaystyle{{f\left( {i,j} \right)}} να είναι περιττός είναι ίσο με

\displaystyle{\sum\limits_{m = 2}^{n - 1} {\left( {{a_m} - {a_{m + 1}}} \right)}  = {a_2} - {a_n} = n - {a_n}.}

Ισχυρισμός: Είναι \displaystyle{{a_n} = 0} για αρκετά μεγάλο n (δηλαδή η αντίστοιχη n-οστή διαγώνιος αποτελείται μόνο από μηδενικά).

Πράγματι, η \displaystyle{\left( {{a_n}} \right)} είναι μια φθίνουσα ακολουθία μη αρνητικών ακεραίων, οπότε είναι τελικά σταθερή, δηλαδή υπάρχουν μη αρνητικοί ακέραιοι k και n_0 τέτοιοι, ώστε \displaystyle{{a_n} = k} για κάθε \displaystyle{n \ge {n_0}.} Αυτό σημαίνει ότι ο αριθμός \displaystyle{{f\left( {i,j} \right)}} είναι άρτιος για κάθε ζεύγος \displaystyle{{\left( {i,j} \right)}} με \displaystyle{i + j \ge n_0}.

Υποθέτουμε ότι k>0 και θεωρούμε τον ελάχιστο θετικό ακέραιο i για τον οποίο ισχύει \displaystyle{{f\left( {i,{n_0} - i} \right) > 0}.}

Από την υπόθεση έπεται εύκολα (με επαγωγή) ότι για κάθε θετικό ακέραιο r ισχύει

\displaystyle{f\left( {i,{n_0} + r - i} \right) = \left\lfloor {\frac{{f\left( {i,{n_0} - i} \right)}}{{{2^r}}}} \right\rfloor }.

Αν επιλέξουμε τον r έτσι, ώστε \displaystyle{{2^r} \le f\left( {i,{n_0} - i} \right) < {2^{r + 1}},} τότε έχουμε ότι \displaystyle{f\left( {i,{n_0} + r - i} \right) = 1}, πράγμα άτοπο. Ο ισχυρισμός έπεται.

Χρησιμοποιώντας τον ισχυρισμό, βρίσκουμε ότι το ζητούμενο πλήθος των ζευγών \displaystyle{{\left( {i,j} \right)}} ώστε ο αριθμός \displaystyle{{f\left( {i,j} \right)}} να είναι περιττός είναι ίσο με n.


Βαγγέλης Μουρούκος

Erro ergo sum.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7805
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Συνδυαστική ή άλγεβρα;

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιουν 18, 2017 9:24 pm

Την άσκηση την πήρα από εδώ. Βάζω μια συνδυαστική απόδειξη που μπήκε εκεί:

Στο πρώτο βήμα βάζουμε n νομίσματα στο σημείο (1,1). Στο βήμα k, για k \geqslant 2, κοιτάζουμε όλα τα σημεία της μορφής (a,b) με a+b = k. Αν το σημείο έχει άρτιο αριθμό νομισμάτων, μεταφέρουμε τα μισά νομίσματα στο (a+1,b) και τα μισά στο (a,b+1). Αν έχει περιττό αριθμό νομισμάτων, αφήνουμε ένα νόμισμα στο (a,b), και από τα υπόλοιπα, μεταφέρουμε τα μισά νομίσματα στο (a+1,b) και τα μισά στο (a,b+1).

Είναι εύκολο να δειχθεί επαγωγικά ότι στο τέλος του k βήματος, κάθε σημείο (a,b) με a+b = k+1 έχει ακριβώς f(a,b) νομίσματα. Επίσης, κάθε σημείο (a,b) με a+b \leqslant k, θα έχει είτε 1 είτε 0 νομίσματα ανάλογα με το αν ο f(a,b) είναι περιττός ή άρτιος.

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

Στο τέλος της διαδικασίας θα παραμείνουν n νομίσματα σε κάποιες θέσεις οι οποίες θα είναι ακριβώς οι θέσεις όπου τα f(i,j) είναι περιττοί.


Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

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

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