Σελίδα 1 από 1

Απαρίθμηση

Δημοσιεύτηκε: Δευ Νοέμ 23, 2009 9:57 pm
από MoV
Έστω το σύνολο A=\{0,1,...,k-1\} . Από αυτό μπορούμε να φτιάξουμε k^n διαφορετικές διατεταγμένες n-άδες : (a_0,a_1,...,a_{n-1}) με a_i \in A. Να βρείτε μια συνάρτηση η οποία αντιστοιχεί σε κάθε μία n-άδα έναν φυσικό αριθμό , διαφορετικό για κάθε n-άδα , από το 0 εώς το k^n-1 .

Re: Απαρίθμηση

Δημοσιεύτηκε: Δευ Νοέμ 23, 2009 11:46 pm
από duperman
Να δωσω την συνάρτηση μάλλον δεν θα τα καταφέρω :)

απλα μία σκέψη....
αν πολλαπλασιάζαμε το κάθε στοιχείο της n-άδας με διαφορετική δυναμη του k δεν θα είχαμε διαφορετικό αποτέλεσμα για την κάθε n-άδα?

Για παράδειγμα

a_{0}*k^{n-1} + a_{1}*k^{n-2} + .... + a_{n-1}*k^0

(σαν να είναι ψηφία ενος αριθμού σε αριθμητικό σύστημα με βάση το k )

.... ελπίζω να έχω καταλάβει τι ζητάμε και να μην γράφω αρλούμπες

Re: Απαρίθμηση

Δημοσιεύτηκε: Τρί Νοέμ 24, 2009 7:26 pm
από MoV
Πολύ ωραία duperman . \displaystyle{ f(a_0,a_1,...,a_{n-1})=(a_{n-1}*a_{n-2}*...*a_0)_k=\sum_{i=0}^{n-1}a_i*k^i } .
Στον φυσικό αριθμό 0 \le t \le k^n-1 αντιστοιχεί η n-άδα :
\displaystyle{ f^{-1}(t)=((tdivk^{n-1})modk,(tdivk^{n-2})modk,...,(tdivk^0)modk) } .

Για k=10 έχουμε τα 10 ψηφία και μπορούμε να δούμε τις n-άδες σαν τους αριθμούς από το 0 έως το (99...99)_{10} (n το πλήθος 9).
Γενικά έχουμε k "ψηφία" και μπορούμε να δούμε τις n-άδες σαν τους αριθμούς στην βάση k από το 0 έως το ((k-1)*(k-1)*...*(k-1)*(k-1))_k (n το πλήθος (k-1)).
θα δείξω ότι : tdiv^{(n)}k=tdivk^{n} .
για n=1 προφανώς ισχύει
δέχομαι ότι ισχύει για n=m
για n=m+1 έστω t=k^{m}p_1+u_1=k^{m}(p_2k+u_2)+u_1 με u_1 < k^{m} ,u_2 < k
οπότε : tdiv^{(m+1)}k=(tdiv^{(m)}k)divk=(tdivk^{m})divk=p_1divk=p_2 και : tdivk^{m+1}=(p_2k^{m+1}+u_2k^{m}+u_1)divk^{m+1} όμως u_2k^{m}+u_1 \le k^{m+1} -1 άρα tdivk^{m+1}=p_2