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

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

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

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

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Μάιος 08, 2017 8:42 pm

Έστω θετικός ακέραιος k. Να βρεθεί το πλήθος των μη αρνητικών ακεραίων n οι οποίοι είναι μικρότεροι ή ίσοι του 10^k και ικανοποιούν τις ακόλουθες ιδιότητες:
(α) Ο n είναι πολλαπλάσιο του 3.
(β) Κάθε δεκαδικό ψηφίο του n είναι ένα από τα 2,0,1 και 7.



Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1366
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#2

Μη αναγνωσμένη δημοσίευση από dement » Τρί Μάιος 09, 2017 10:26 am

Αφού ο 10^k δεν είναι πολλαπλάσιο του 3, θεωρούμε απλώς τους k-ψήφιους αριθμούς (όπου το 0 θεωρείται πιθανό εξ αριστερών ψηφίο).

Η αναγκαία και ικανή συνθήκη είναι ο αριθμός μας να περιέχει ισάριθμα (modulo 3) ψηφία ισότιμα με 1 \mod 3 (1 ή 7) και ισότιμα με 2 \mod 3 (2). Αν ο αριθμός των ψηφίων modulo 1 είναι m και αυτών modulo 2 είναι m + 3n \ (n \in \mathbb{Z}), τότε έχουμε \displaystyle 2^m \binom{k}{m} \binom{k-m}{m+3n} δυνατότητες (από επιλογή θέσεων και ψηφίου modulo 1, αφού έχουμε μόνο ένα ψηφίο ισότιμο με 0 modulo 3) και συνολικά οι συνδυασμοί είναι

\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]


Δημήτρης Σκουτέρης

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

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

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Μάιος 10, 2017 11:07 am

Ωραία!
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
Διευθύνον Μέλος
Δημοσιεύσεις: 1366
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#4

Μη αναγνωσμένη δημοσίευση από dement » Τετ Μάιος 10, 2017 11:17 am

:coolspeak:

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


Δημήτρης Σκουτέρης

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

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

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Μάιος 10, 2017 11:39 am

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

Γράφουμε A_k,B_k,C_k για το πλήθος των n που ικανοποιούν το (β) αλλά είναι ισότιμα με 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 και B_1 = 2.

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

\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}}

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


Απάντηση

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

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

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