Πλήθος ακεραίων

#1

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

. Να βρεθεί το πλήθος των μη αρνητικών ακεραίων

οι οποίοι είναι μικρότεροι ή ίσοι του 10^k

και ικανοποιούν τις ακόλουθες ιδιότητες:
(α) Ο

είναι πολλαπλάσιο του

.
(β) Κάθε δεκαδικό ψηφίο του

είναι ένα από τα 2,0,1

και

.

dement · #2

Αφού ο

δεν είναι πολλαπλάσιο του

, θεωρούμε απλώς τους

-ψήφιους αριθμούς (όπου το

θεωρείται πιθανό εξ αριστερών ψηφίο).

Η αναγκαία και ικανή συνθήκη είναι ο αριθμός μας να περιέχει ισάριθμα (modulo

) ψηφία ισότιμα με $1 \mod 3$ (

ή

) και ισότιμα με $2 \mod 3$ (

). Αν ο αριθμός των ψηφίων modulo

είναι

και αυτών modulo

είναι $m + 3n \ (n \in \mathbb{Z})$ , τότε έχουμε $\displaystyle 2^m \binom{k}{m} \binom{k-m}{m+3n}$ δυνατότητες (από επιλογή θέσεων και ψηφίου modulo

, αφού έχουμε μόνο ένα ψηφίο ισότιμο με

modulo

) και συνολικά οι συνδυασμοί είναι

$\displaystyle \sum_{m,n} 2^m \binom{k}{m} \binom{k-m}{m+3n}$ .

Ισχύει (ταυτότητα) ότι $\displaystyle \sum_{n} \binom{k}{m + 3n} = \frac{2}{3} \left[2^{k-1} + \cos \left( \frac{\pi (k - 2m)}{3} \right) \right]$

από όπου το άθροισμά μας γίνεται

$\displaystyle \frac{1}{3} \sum_m 2^m \binom{k}{m} \left[2^{k-m} + 2 \cos \left( \frac{\pi (k - 3m)}{3} \right) \right] = \frac{2^k}{3} \sum_m \binom{k}{m} + \frac{2}{3} \cos \left( \frac{\pi k}{3} \right) \sum_m (-2)^m \binom{k}{m} =$

$\displaystyle = \frac{2}{3} \left[ 2^{2k-1} + \cos \left( \frac{4 \pi k}{3} \right) \right]$

#3

Ωραία!

dement έγραψε: Ισχύει (ταυτότητα) ότι $\displaystyle \sum_{n} \binom{k}{m + 3n} = \frac{2}{3} \left[2^{k-1} + \cos \left( \frac{\pi (k - 2m)}{3} \right) \right]$

Ας δούμε και την απόδειξη μιας και δεν νομίζω να θυμόμαστε την ταυτότητα εν ώρα διαγωνισμού:

Ξέρουμε ότι

$\displaystyle{ (1+x)^n = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \cdots + \binom{n}{n}x^n}$

Θέτουμε διαδοχικά $x=1,x=\omega,x=\omega^2$ , όπου $\omega=e^{2\pi i/3}$ και προσθέτουμε.

Για $k = 0 \bmod 3$ είναι $1 + \omega^k + \omega^{2k} = 3$ ενώ για $k = 1,2 \bmod 3$ είναι $1 + \omega^k + \omega^{2k} = 0$ . Άρα παίρνουμε

$\displaystyle{ 2^n + (1+\omega)^n + (1+\omega^2)^n = 3\left[\binom{n}{0} + \binom{n}{3} + \cdots \right]}$

Άρα

$\begin{aligned} \binom{n}{0} + \binom{n}{3} + \cdots &= \frac{1}{3}\left[ 2^n + (1+\omega)^n + (1+\omega^2)^n \right] \\ &= \frac{1}{3}\left[ 2^n + (-\omega^2)^n + (-\omega)^n \right] \\ &= \frac{1}{3}\left[2^n + (-1)^n(\omega^n + \omega^{2n})\right] \\ &= \begin{cases} \frac{1}{3}\left[2^n + 2(-1)^n\right] & n\equiv 0 \bmod 3 \\ \frac{1}{3}\left[2^n + (-1)^{n+1}\right] & n \not \equiv 0 \bmod 3 \end{cases} \end{aligned}$

Με παρόμοιο τρόπο βρίσκουμε και τα άλλα δύο. [Υπολογίζοντας π.χ. τα $(1+1)^n + \omega(1+\omega)^n + \omega^2(1+\omega^2)^n$ και $(1+1)^n + \omega^2(1+\omega)^n + \omega(1+\omega^2)^n$ αντίστοιχα.] Μπορούμε επίσης να χρησιμοποιήσουμε και συμμετρία. Π.χ. αν $n \equiv 1 \bmod 3$ είναι
$\displaystyle{ \binom{n}{0} + \binom{n}{3} + \cdots = \binom{n}{n} + \binom{n}{n-3} + \cdots + \binom{n}{1}.}$

dement · #4

Η αλήθεια είναι ότι κι εγώ δεν την θυμόμουν, την απέδειξα επί τόπου και μετά σκέφτηκα ότι αποκλείεται να μην υπάρχει κάπου ως ταυτότητα!

#5

Διαφορετικά μπορούμε να χρησιμοποιήσουμε αναδρομικές σχέσεις.

Γράφουμε A_k,B_k,C_k

για το πλήθος των

που ικανοποιούν το (β) αλλά είναι ισότιμα με $0 \bmod 3, 1\bmod 3$ και $2 \bmod 3$ αντίστοιχα. Είναι άμεσο ότι

$\displaystyle{ A_{k+1} = A_k + B_k + 2C_k}$
$\displaystyle{ B_{k+1} = 2A_k + B_k + C_k}$
$\displaystyle{ C_{k+1} = A_k + 2B_k + C_k}$

με αρχικές σχέσεις A_1 = C_1 = 1

και

.

Παρατηρώ τώρα ότι

$\begin{aligned} A_{k+1} &= (A_k+B_k+C_k) + C_k \\ &= 4^k + C_k \\ &= 4^k + 4^{k-1} + B_{k-1} \\ &= 4^k + 4^{k-1} + 4^{k-2} + A_{k-2} \\ &= 21 \cdot 4^{k-2} + A_{k-2} \end{aligned}$

Άρα είναι και

$\displaystyle{ A_{3k+1} = 21(4^1 + 4^4 + \cdots + 4^{3k-2}) + A_1 = 21 \cdot 4 \cdot \frac{4^{3k}-1}{4^3-1} + 1 = \frac{4^{3k+1}-1}{3}}$

Με παρόμοιο τρόπο βρίσκουμε

$\displaystyle{ A_{3k+2} = 21(4^2 + 4^5 + \cdots + 4^{3k-1}) + A_2 = 21 \cdot 4^2 \cdot \frac{4^{3k}-1}{4^3-1} + 5 = \frac{4^{3k+2}-1}{3}}$

και

$\displaystyle{ A_{3k+3} = 21(4^3 + 4^6 + \cdots + 4^{3k}) + A_3 = 21 \cdot 4^3 \cdot \frac{4^{3k}-1}{4^3-1} + 22 = \frac{4^{3k+3}+2}{3}}$

Την άσκηση την πήρα από εδώ. Ίσως λίγο δύσκολη για Αρχιμήδη/Προκριματικό. Την έβαλα όμως εδώ διότι απαιτεί μεν κάποιες γνώσεις αλλά είναι αρκετά τυπική και δεν χρειάζεται ιδιαίτερη σκέψη.

Πλήθος ακεραίων

Πλήθος ακεραίων

Re: Πλήθος ακεραίων

Re: Πλήθος ακεραίων

Re: Πλήθος ακεραίων

Re: Πλήθος ακεραίων

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