Dowód jednoznaczności systemie o podstawie k > 1

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
dwukwiat15
Użytkownik
Użytkownik
Posty: 246
Rejestracja: 4 cze 2006, o 09:25
Płeć: Mężczyzna
Lokalizacja: Krobia
Podziękował: 42 razy

Dowód jednoznaczności systemie o podstawie k > 1

Post autor: dwukwiat15 »

Witam, Mam problem z wykazaniem faktu, że jeżeli dowolną liczbę całkowitą dodatnią \(\displaystyle{ n}\) reprezentujemy w danym systemie o podstawie \(\displaystyle{ k > 1}\), gdzie reprezentacja jest postaci:
\(\displaystyle{ n =a_{s}k^{s} + a_{s-1}k^{s-1} + ... + a_{0}}\) to dwie różne reprezentacje w systemi o podstawie k reprezentują różne liczby całkowite. Wskazówka jest taka aby skorzystać z nierówności:
\(\displaystyle{ 0<n \le k^{s+1} - 1}\). Nierówność ta jest oczywista bo \(\displaystyle{ k^{s+1} -1 = \sum_{i=0}^{s} (k-1)k^{i}}\) czyli odpowiada to reprezentacji liczby n przy (s+1) cyfrach, gdzie poszczególne człony \(\displaystyle{ a_{i}}\) mają wartość maksymalną( równą \(\displaystyle{ k-1}\)). Czy ma ktoś jakiś pomysł jak to ruszyć?
Ja próbuję konstruować liczby typu \(\displaystyle{ n+1}\) czy \(\displaystyle{ n-1}\) ale nie dostaję żadnych sensownych nierówności, które mogłyby mi zapewnić jednoznaczność reprezentacji.
Piotr Rutkowski
Użytkownik
Użytkownik
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 390 razy

Dowód jednoznaczności systemie o podstawie k > 1

Post autor: Piotr Rutkowski »

Podpowiedź:
Jeśli masz dwie różne reprezentacje w danym systemie, wybierz najpierw pierwszą cyfrę, którą te reprezentacje się różnią (pierwszą tzn. tą przy najwyższej potędze). Czy te dwie liczby mogą się znowu zrównać poprzez różnice cyfr przy niższych potęgach?
Awatar użytkownika
dwukwiat15
Użytkownik
Użytkownik
Posty: 246
Rejestracja: 4 cze 2006, o 09:25
Płeć: Mężczyzna
Lokalizacja: Krobia
Podziękował: 42 razy

Dowód jednoznaczności systemie o podstawie k > 1

Post autor: dwukwiat15 »

Dziwnie napisałeś. Najpierw piszesz o cyfrach różniących się, które mają się zrównać? Trochę nierozumiem. Czy ta podpowiedź ma związek z nierównością którą napisałem jako podpowiedź?
Piotr Rutkowski
Użytkownik
Użytkownik
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 390 razy

Dowód jednoznaczności systemie o podstawie k > 1

Post autor: Piotr Rutkowski »

Powiedzmy że mamy dwie reprezentacje \(\displaystyle{ \overline{a_{k}...a_{1}}=\overline{b_{s}...b_{1}}}\) gdzie oczywiście \(\displaystyle{ a_{k},...,a_{1},b_{s},...,b_{1}}\) to cyfry w danym systemie. Najpierw korzystając z nierówności pokaż, że \(\displaystyle{ k=s}\). Kiedy to już zrobisz wiedząc, że są to 2 różne reprezentacje, muszą się one różnić na co najmniej jednym miejscu, w szczególności wybierz pierwszą cyfrę, na której \(\displaystyle{ a_{l}\neq b_{l}}\). Pokaż wtedy, że z założenia, że \(\displaystyle{ a_{i}=b_{i} \ i=l,l+1,...,k}\) oraz \(\displaystyle{ a_{l}>b_{l}}\) będzie wynikać \(\displaystyle{ \overline{a_{k}...a_{1}}>\overline{b_{s}...b_{1}}}\). Analogicznie doprowadź do sprzeczności z \(\displaystyle{ a_{l}<b_{l}}\).
Awatar użytkownika
dwukwiat15
Użytkownik
Użytkownik
Posty: 246
Rejestracja: 4 cze 2006, o 09:25
Płeć: Mężczyzna
Lokalizacja: Krobia
Podziękował: 42 razy

Dowód jednoznaczności systemie o podstawie k > 1

Post autor: dwukwiat15 »

hmm według mnie nie da się wykazać, że k = s chociażby z tego względu, że \(\displaystyle{ a_{s} \neq 0}\)
oraz \(\displaystyle{ a_{k} \neq 0}\) z założenia, dlatego nie dopisuje się zer z przodu. Co o tym sądzisz? Chyba,że to chodzi o dowód nie wprost?
Piotr Rutkowski
Użytkownik
Użytkownik
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 390 razy

Dowód jednoznaczności systemie o podstawie k > 1

Post autor: Piotr Rutkowski »

Tak, chodzi o dowód nie wprost. Ok, chyba niezbyt jasno napisałem, spróbuję na przykładzie systemy dziesiętnego. Weźmy dowolną liczbę i jej dwie reprezentacje. Najpierw wykaż, że jeśli obie te reprezentacje dają tę samą liczbę, to muszą mieć tą samą ilość cyfr, inaczej ta z większą ilością cyfr byłaby większa, a ma być równa. Zatem mamy 2 reprezentacje o tej samej ilości cyfr, powiedzmy \(\displaystyle{ 1234x...}\) oraz \(\displaystyle{ 1234y...}\) gdzie \(\displaystyle{ x\neq y}\). Pokaż, że jeśli \(\displaystyle{ x>y}\) to \(\displaystyle{ 1234x... > 1234y...}\) niezależnie od tego jakie cyfry występują dalej. Wszystkie wnioski będą konsekwencją wspomnianej nierówności.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Dowód jednoznaczności systemie o podstawie k > 1

Post autor: norwimaj »

Moim zdaniem sprawniej jest zapewnić równość \(\displaystyle{ k=s}\) dopisując zera na początku. Wtedy nie trzeba dwa razy pisać tego samego.
ODPOWIEDZ