Trener OMJ

Zadanie 3

2025
Etap II
Kombinatoryka
Teoria liczb
Pionek na planszy 1×1001 \times 100

Powiązane zadania:

Zad. 2 (2022)
Zad. 2 (2022)

Tytuł zadania przepisała z PDF-u AI. Poziom trudności, kategorie, umiejętności i powiązania zadań też wyznaczyła AI — mogą być niedokładne. Więcej w regulaminie

Treść zadania

Treść zadania przepisana z PDF-u przez AI — w razie wątpliwości sprawdź oryginalny PDF. Więcej w regulaminie

Pola prostokątnej planszy 1×1001 \times 100 są ponumerowane kolejno liczbami całkowitymi od 11 do 100100. Pionek początkowo stał na polu o numerze nn. W pierwszym ruchu przesunięto go o jedno pole, w drugim — o dwa pola, w trzecim — o trzy pola itd. Okazało się, że po wykonaniu 9999 ruchów pionek odwiedził każde pole dokładnie raz. Wyznacz wszystkie możliwe wartości nn.

*Uwaga.* Przesunięcie pionka *o kk pól* oznacza bezpośrednie przemieszczenie go między polami, których numery różnią się o kk.
Zadania PDFRozwiązania PDF
Zgłoś błąd

Umiejętności (5)

Wymagane umiejętności:

Parzystość i nieparzystość
Niezmienniki
Analiza przypadków

Zdobywane umiejętności:

Niezmienniki
Parzystość i nieparzystość

Wskazówki (0/4)

Wskazówki wygenerowane przez AI — mogą zawierać błędy. Więcej w regulaminie

Wskazówka 1
Spróbuj prześledzić sytuację dla mniejszej planszy, np. 1×41 \times 4 lub 1×61 \times 6. Czy potrafisz znaleźć startowe pola, z których pionek odwiedzi każde pole dokładnie raz? To pomoże zauważyć prawidłowość.
Wskazówka 2
Skoro pionek odwiedza wszystkie pola od 11 do 100100 dokładnie raz, znasz sumę wszystkich odwiedzonych pól. Spróbuj zapisać to jako równanie wiążące nn z wyborami kierunków (w prawo lub w lewo) w kolejnych ruchach.
Wskazówka 3
Niech pip_i to pole po ii-tym ruchu, εi=±1\varepsilon_i = \pm 1 to kierunek. Wtedy pi=n+ε1⋅1+⋯+εi⋅ip_i = n + \varepsilon_1 \cdot 1 + \dots + \varepsilon_i \cdot i. Zsumuj p0,…,p99p_0, \dots, p_{99} i porównaj z 1+2+⋯+1001+2+\dots+100. Pamiętaj, że pi∈{1,…,100}p_i \in \{1, \dots, 100\}.
Wskazówka 4
Wyznacz nn z równania na sumę pól — pojawi się wyrażenie z ∑εj⋅j(100−j)\sum \varepsilon_j \cdot j(100-j). Zbadaj jego parzystość. Następnie pomyśl: z których pól da się wykonać ruch o 9999? To mocno ogranicza pozycje na początku i końcu wędrówki.

Prześlij rozwiązanie

Zaloguj się, aby przesłać swoje rozwiązanie

Zaloguj się