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

#1

Δίνεται θετικός ακέραιος

. Ορίζουμε συνάρτηση $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

με

.

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

για τα οποία ο f (i, j)

είναι περιττός.

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

#2

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

Η βασική παρατήρηση είναι ότι για κάθε $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)} }$

το άθροισμα των στοιχείων της

-οστής διαγωνίου (από πάνω αριστερά προς κάτω δεξιά) του πίνακα

.

Το πλήθος των ζευγών $\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}$ για αρκετά μεγάλο

(δηλαδή η αντίστοιχη

-οστή διαγώνιος αποτελείται μόνο από μηδενικά).

Πράγματι, η $\displaystyle{\left( {{a_n}} \right)}$ είναι μια φθίνουσα ακολουθία μη αρνητικών ακεραίων, οπότε είναι τελικά σταθερή, δηλαδή υπάρχουν μη αρνητικοί ακέραιοι

και

τέτοιοι, ώστε $\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

και θεωρούμε τον ελάχιστο θετικό ακέραιο

για τον οποίο ισχύει $\displaystyle{{f\left( {i,{n_0} - i} \right) > 0}.}$

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

ισχύει

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

Αν επιλέξουμε τον

έτσι, ώστε $\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)}}$ να είναι περιττός είναι ίσο με

.

#3

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

Στο πρώτο βήμα βάζουμε

νομίσματα στο σημείο (1,1)

. Στο βήμα

, για $k \geqslant 2$ , κοιτάζουμε όλα τα σημεία της μορφής (a,b)

με

. Αν το σημείο έχει άρτιο αριθμό νομισμάτων, μεταφέρουμε τα μισά νομίσματα στο (a+1,b)

και τα μισά στο (a,b+1)

. Αν έχει περιττό αριθμό νομισμάτων, αφήνουμε ένα νόμισμα στο (a,b)

, και από τα υπόλοιπα, μεταφέρουμε τα μισά νομίσματα στο (a+1,b)

και τα μισά στο (a,b+1)

.

Είναι εύκολο να δειχθεί επαγωγικά ότι στο τέλος του

βήματος, κάθε σημείο (a,b)

με

έχει ακριβώς f(a,b)

νομίσματα. Επίσης, κάθε σημείο (a,b)

με $a+b \leqslant k$ , θα έχει είτε

είτε

νομίσματα ανάλογα με το αν ο f(a,b)

είναι περιττός ή άρτιος.

Η διαδικασία σίγουρα θα φτάσει σε ένα βήμα όπου δεν μεταφέρουμε πλέον άλλα νομίσματα. Πράγματι σε αντίθετη περίπτωση, από ένα βήμα και μετά σε κάθε σημείο μεταφέρεται άρτιος αριθμός νομισμάτων. Κοιτάζουμε το μικρότερο

ώστε σε αυτό το βήμα στο (a,b)

μεταφέρθηκε άρτιος αριθμός νομισμάτων. Το (a,b+1)

θα πάρει ακριβώς τα μισά από αυτά τα νομίσματα αφού εν υπάρχουν νομίσματα στο (a-1,b-1)

. Από την υπόθεση ο αριθμός αυτών των νομισμάτων θα είναι επίσης άρτιος. Το ίδιο και στο (a,b+2)

κ.ο.κ., άτοπο.

Στο τέλος της διαδικασίας θα παραμείνουν

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

είναι περιττοί.

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

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

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

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

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