mathematica.gr

Δημοσιεύτηκε: **Τρί Ιουν 21, 2011 12:00 pm**

Έστω θετικός ακέραιος

. Να δειχθεί ότι ο αριθμός των $0 \leqslant m \leqslant n$ ώστε ο διωνυμικός συντελεστής $\displaystyle{\binom{n}{m}}$ να είναι περιττός, είναι δύναμη του 2.

Δημοσιεύτηκε: **Τρί Ιουν 21, 2011 4:29 pm**

Θα αποδείξουμε το εξής γενικότερο αποτέλεσμα:

Έστω $\displaystyle{p}$ πρώτος αριθμός και $\displaystyle{n}$ θετικός ακέραιος. Συμβολίζουμε με $\displaystyle{{f_p}\left( n \right)}$ το πλήθος των ακεραίων αριθμών $\displaystyle{m}$ με $\displaystyle{0 \le m \le n}$ για τους οποίους ο διωνυμικός συντελεστής $\displaystyle{\left( \begin{array}{l} n\\ m \end{array} \right)}$ δεν είναι πολλαπλάσιο του $\displaystyle{p.}$
Έστω ακόμη ότι το ανάπτυγμα του $\displaystyle{n}$ με βάση το $\displaystyle{p}$ είναι

$\displaystyle{n = \sum\limits_{i = 0}^k {{a_i}} {p^i},}$

όπου $\displaystyle{{a_i} \in \left\{ {0,1, \ldots ,p - 1} \right\}}$ για $\displaystyle{i = 0,1, \ldots ,k.}$
Τότε ισχύει ότι

$\boxed{\displaystyle{{f_p}\left( n \right) = \prod\limits_{i = 0}^k {\left( {{a_i} + 1} \right)}}}.$

Για $\displaystyle{p = 2}$ βρίσκουμε άμεσα ότι το πλήθος των περιττών διωνυμικών συντελεστών της μορφής $\displaystyle{\left( \begin{array}{l} n\\ m \end{array} \right)},$ όπου $\displaystyle{0 \le m \le n},$ είναι ίσο με

$\displaystyle{{f_2}\left( n \right) = {2^{r\left( n \right)}},}$

όπου $\displaystyle{r\left( n \right)}$ το πλήθος των μη μηδενικών ψηφίων του αναπτύγματος του $\displaystyle{n}$ με βάση το $\displaystyle{2}$ και το ζητούμενο του προβλήματος έπεται.

Για την απόδειξη του γενικότερου ισχυρισμού, θα χρησιμοποιήσουμε ένα γνωστό αποτέλεσμα του Lucas:

Αν $\displaystyle{n = \sum\limits_{i = 0}^k {{a_i}} {p^i}}$ και $\displaystyle{m = \sum\limits_{i = 0}^k {{b_i}} {p^i}},$ όπου $\displaystyle{{a_i}, {b_i} \in \left\{ {0,1, \ldots ,p - 1} \right\}}$ για $\displaystyle{i = 0,1, \ldots ,k},$ τότε ισχύει

$\displaystyle{\left( \begin{array}{l} n\\ m \end{array} \right) \equiv \left( \begin{array}{l} {a_0}\\ {b_0} \end{array} \right)\left( \begin{array}{l} {a_1}\\ {b_1} \end{array} \right)\left( \begin{array}{l} {a_2}\\ {b_2} \end{array} \right) \cdots \left( \begin{array}{l} {a_k}\\ {b_k} \end{array} \right)\left( {\bmod p} \right).}$

Παρατηρούμε τώρα ότι ο $\displaystyle{p}$ δε διαιρεί το διωνυμικό συντελεστή $\displaystyle{\left( \begin{array}{l} n\\ m \end{array} \right)}$ αν και μόνο αν ο $\displaystyle{p}$ δε διαιρεί κανέναν από τους διωνυμικούς συντελεστές $\displaystyle{\left( \begin{array}{l} {a_i}\\ {b_i} \end{array} \right)}$ με $\displaystyle{i = 0,1, \ldots ,k}.$ Εφόσον, όμως, $\displaystyle{{a_i} < p,}$ αυτό θα συμβαίνει αν και μόνο αν ο $\displaystyle{{b_i}}$ παίρνει μια από τις $\displaystyle{{a_i} + 1}$ τιμές $\displaystyle{0,1, \ldots ,{a_i},}$ για κάθε $\displaystyle{i = 0,1, \ldots ,k}.$ Ο ισχυρισμός έπεται τώρα άμεσα από την πολλαπλασιαστική αρχή απαρίθμησης.

Δημοσιεύτηκε: **Τετ Ιουν 22, 2011 2:52 pm**

Είναι το πρόβλημα Α7 από τον διαγωνισμό Putnam του 1956

mathematica.gr

Περιττοί διωνυμικοί συντελεστές

Περιττοί διωνυμικοί συντελεστές

Re: Περιττοί διωνυμικοί συντελεστές

Re: Περιττοί διωνυμικοί συντελεστές