Czy istnieje bijekcja \(\displaystyle{ f: \NN \to \NN}\) taka, że \(\displaystyle{ f(n)}\) i \(\displaystyle{ f(n+1)}\) binarnie różnią się tylko jedną cyfrą (dla dowolnego \(\displaystyle{ n}\) ) 
Własność Bijekcji
-
mol_ksiazkowy
- Użytkownik
- Posty: 11576
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3167 razy
- Pomógł: 749 razy
Własność Bijekcji
Czy istnieje bijekcja \(\displaystyle{ f: \NN \to \NN}\) taka, że \(\displaystyle{ f(n)}\) i \(\displaystyle{ f(n+1)}\) binarnie różnią się tylko jedną cyfrą (dla dowolnego \(\displaystyle{ n}\) )
Ostatnio zmieniony 28 sie 2023, o 21:00 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Jakub Gurak
- Użytkownik
- Posty: 1423
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 68 razy
- Pomógł: 84 razy
Re: Własność Bijekcji
Rozumiem, że chodzi tu o te ciągi liczb naturalnych, że dla dowolnego \(\displaystyle{ n}\) naturalnego liczby naturalne \(\displaystyle{ f(n)}\) i \(\displaystyle{ f(n+1)}\), zapisane w systemie dwójkowym, różnią się tylko jedną cyfrą
Sądzę, że jest taka bijekcja, tylko ciężko będzie ją opisać:
Oto ciąg początkowych takich liczb naturalnych (rozumianych jako skończone ciągi zero-jedynkowe):
\(\displaystyle{ \left( 0\right);\left( 1\right); \left( 1,0\right) ; \left( 1,1\right); \left( 1,1,0\right); \left( 1,1,1\right);\left( 1,0,1\right); \left( 1,0,0\right); \left( 1,0,0,0\right) ; \left( 1,0,0,1\right); \left( 1,0,1,1\right); \left( 1,0,1,0\right); \\ \left( 1,1,1,0\right); \left( 1,1,1,1\right); \left( 1,1,0,1\right); \left( 1,1,0,0\right); \left( 1,1,0,0,0\right); \left( 1,1,0,0,1\right); \left( 1,1,0,1,1 \right); \left( 1,1,0,1,0\right); \ldots}\)
Czyli, liczby naturalne zapisujemy w systemie dwójkowym; gdzie, takie skończone ciągi zero-jedynkowe, dzielimy na grupy ze względu na ich długość; i, wypisujemy kolejno: ciągi o długości jeden, potem ciągi o długości dwa, potem o długości trzy, itd.
Dokładniej, to na początek wypisujemy ciągi jednowyrazowe \(\displaystyle{ \left( 0\right)}\) i \(\displaystyle{ \left( 1\right)}\); i, przechodząc do ciągu dłuższej długości, dopisujemy zero do ostatniego wyrazu; a, pomiędzy ciągami danej grupy ciągów tej samej długości, patrzymy na ostatnie cyfry: i, jeśli zmiana ostatniej cyfry nie daje nowych możliwości tworzenia ciągów, to patrzymy na wcześniejszą poprzedzającą cyfrę ( a jeśli daje nową możliwość, to go dopisujemy), i ją zamieniamy( \(\displaystyle{ 0}\) na \(\displaystyle{ 1}\) i \(\displaystyle{ 1}\) na \(\displaystyle{ 0}\)), nie zmieniając pozostałych cyfr, w następnym kroku zachowujemy tą cyfrę zmieniając jedynie ostatnią cyfrę, i jeśli już nie ma możliwości jej zmiany, to patrzymy na przedostatnią cyfrę, itd. ...
Mam nadzieję, że to jest jasne...
Oczywiście, jest to bijekcja, bo każda liczba naturalna ma jednoznaczne przedstawienie w postaci skończonego rozwinięcia dwójkowego, i, dane skończone rozwinięcie zero-jedynkowe, wyznacza liczbę naturalną; i, z konstrukcji wynika, że te sąsiednie ciągi skończone rozwinięć zero-jedynkowych różnią się co najwyżej jedną cyfrą.\(\displaystyle{ \square}\)
Zapomniałem dodać, robimy tutaj tak, aby pierwszy wyraz tego rozwinięcia, (poza pierwszym ciągiem równym \(\displaystyle{ \left( 0\right)}\) ), był różny od zera.
Sądzę, że jest taka bijekcja, tylko ciężko będzie ją opisać:
Oto ciąg początkowych takich liczb naturalnych (rozumianych jako skończone ciągi zero-jedynkowe):
\(\displaystyle{ \left( 0\right);\left( 1\right); \left( 1,0\right) ; \left( 1,1\right); \left( 1,1,0\right); \left( 1,1,1\right);\left( 1,0,1\right); \left( 1,0,0\right); \left( 1,0,0,0\right) ; \left( 1,0,0,1\right); \left( 1,0,1,1\right); \left( 1,0,1,0\right); \\ \left( 1,1,1,0\right); \left( 1,1,1,1\right); \left( 1,1,0,1\right); \left( 1,1,0,0\right); \left( 1,1,0,0,0\right); \left( 1,1,0,0,1\right); \left( 1,1,0,1,1 \right); \left( 1,1,0,1,0\right); \ldots}\)
Czyli, liczby naturalne zapisujemy w systemie dwójkowym; gdzie, takie skończone ciągi zero-jedynkowe, dzielimy na grupy ze względu na ich długość; i, wypisujemy kolejno: ciągi o długości jeden, potem ciągi o długości dwa, potem o długości trzy, itd.
Dokładniej, to na początek wypisujemy ciągi jednowyrazowe \(\displaystyle{ \left( 0\right)}\) i \(\displaystyle{ \left( 1\right)}\); i, przechodząc do ciągu dłuższej długości, dopisujemy zero do ostatniego wyrazu; a, pomiędzy ciągami danej grupy ciągów tej samej długości, patrzymy na ostatnie cyfry: i, jeśli zmiana ostatniej cyfry nie daje nowych możliwości tworzenia ciągów, to patrzymy na wcześniejszą poprzedzającą cyfrę ( a jeśli daje nową możliwość, to go dopisujemy), i ją zamieniamy( \(\displaystyle{ 0}\) na \(\displaystyle{ 1}\) i \(\displaystyle{ 1}\) na \(\displaystyle{ 0}\)), nie zmieniając pozostałych cyfr, w następnym kroku zachowujemy tą cyfrę zmieniając jedynie ostatnią cyfrę, i jeśli już nie ma możliwości jej zmiany, to patrzymy na przedostatnią cyfrę, itd. ...
Mam nadzieję, że to jest jasne...
Oczywiście, jest to bijekcja, bo każda liczba naturalna ma jednoznaczne przedstawienie w postaci skończonego rozwinięcia dwójkowego, i, dane skończone rozwinięcie zero-jedynkowe, wyznacza liczbę naturalną; i, z konstrukcji wynika, że te sąsiednie ciągi skończone rozwinięć zero-jedynkowych różnią się co najwyżej jedną cyfrą.\(\displaystyle{ \square}\)
Zapomniałem dodać, robimy tutaj tak, aby pierwszy wyraz tego rozwinięcia, (poza pierwszym ciągiem równym \(\displaystyle{ \left( 0\right)}\) ), był różny od zera.