Problem Langforda

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11360
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3153 razy
Pomógł: 747 razy

Problem Langforda

Post autor: mol_ksiazkowy »

Ustawić ciąg liczb \(\displaystyle{ 1, 1, 2, 2, ...., n, n}\) w taki sposób aby pomiędzy liczbami
\(\displaystyle{ j}\) i \(\displaystyle{ j}\) było \(\displaystyle{ j}\) innych liczb (przerwa zbudowana z \(\displaystyle{ j}\) liczb); np.
gdy \(\displaystyle{ n=4}\): \(\displaystyle{ (4,1,3,1,2,4,3,2)}\).

WskazaĆ przykłady takich ciągów dla \(\displaystyle{ n \geq 5}\).
Ukryta treść:    
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8581
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 307 razy
Pomógł: 3349 razy

Re: Problem Langforda

Post autor: kerajs »

Para Liczb parzystych zajmuje w ciągu jedno miejsce o numerze parzystym i jedno miejsce o numerze nieparzystym. Pary liczb nieparzystych zajmują albo dwa miejsca parzyste albo dwa nieparzyste. Ponieważ w ciągu jest taka sama liczba miejsc o numerze parzystym, co nieparzystym to na pewno nie można ustawić w zadany ciąg liczb dla \(\displaystyle{ n=4k+1}\) oraz \(\displaystyle{ n=4k+2}\) dla których ilość liczb stojących na miejscach parzystych i nieparzystych różni się o 2 lub wielokrotność 2 (co skutkowałoby dziurami w ciągu).
W alfabecie angielskim (jak sugeruje źródło) n jest liczbą czternastą, więc taki ciąg nie istnieje.

\(\displaystyle{ n=7:\\
51716254237643\\
\\
n=8:\\
1318637245268475}\)
ODPOWIEDZ