[Kombinatoryka] Konik na szesnastopolowej szachownicy
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
mol_ksiazkowy
- Użytkownik
- Posty: 11419
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
[Kombinatoryka] Konik na szesnastopolowej szachownicy
czy szachownice szesnastopolowa mozna obejsć (tj. wszystkie jej pola) ruchem konika szachowego i na kazdym polu stanąc tylko raz....?!
Ostatnio zmieniony 16 wrz 2006, o 08:42 przez mol_ksiazkowy, łącznie zmieniany 1 raz.
-
Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
[Kombinatoryka] Konik na szesnastopolowej szachownicy
Nie da się.
Dowód nie wprost - przypuśćmy, że da się tak zrobić:
a) Konik zaczyna swoją drogę na polach różnych od pól narożnych
Ponieważ musi odwiedzić każde pole, zatem musi w szczególności odwiedzić pola narożne. Rozpatrzmy przypadek gdy pierwszym polem narożnym jakie odwiedzi będzie pole A1 (pozostałe analogicznie). Na pole A1 da się dojść tylko z pól B3 i C2 - przyjmijmy, że konik przeskakuje na A1 z pola B3. Wówczas z warunków zadania konik musi się poruszyć na C2. Jeśli teraz konik nie poruszy się na D4 - wówczas nie odwiedzi tego pola z nałożonymi warunkami zadania. Jeśli konik poruszy się na D4 - wówczas z tego pola musi się poruszyć na jedno z pól B3, C2 (gdyż z wybrania A1 jako pierwszy narożnik mamy jeszcze nie odwiedzone pola A4,D1) - sprzeczność z warunkami zadania. Zatem w przypadku a) otrzymaliśmy sprzeczność.
b) Konik zaczyna swoją drogę na jednym z pól narożnych.
Dla ustalenia uwagi niech będzie to A1. Z tego pola może się on poruszyć na B3 lub C2 - przyjmijmy ze względu na środkowosymetryczność szachownicy, że następnym punktem trasy jest B3. Przypuśćmy, że następnym punktem wizyty nie jest D4. Wówczas prawdziwa jest jedna z ewentualności:
(*) konik jako pierwsze z pól B2,C2,C3 odwiedza pole C2 - wówczas rozumując jak w a) następnym polem drogi będzie pole D4 - ale prosto zauważyć, że konik stąd już się ruszyć nie może, a nie odwiedził on jeszcze pól B2,C3 - sprzeczność
(**) konik jako pierwsze z pól B2,C2,C3 odwiedził pole B2 lub C3 - wówczas prosto spostrzec (jak w punkcie a)), że w swoich najbliższych czterech ruchach złoży wizytę na polach A4,B2,C3,D1 kończąc na jednym z pól A4 lub D1 - teraz konik nie ma możliwości ruchu, a nie odwiedził C2 - sprzeczność
Zatem wizyta konika przebiega: A1 -> B3 -> D4 -> C2. Zauważmy [***], że jeśli któreś z pól A2,A3,B1,B4,C1,C4,D2,D3 zostanie nieodwiedzone, a konik znajdzie się na B2 lub C3 - to dostaniemy sprzeczność, gdyż podobnie jak w (**) "zaklinuje" się w jednym z rogów nie odwiedzając któregoś z pól. Z C2 konik może przebyć następujące drogi (uwzględniając rozumowanie [***]):
A3 -> C4 -> D2 -> B1
A3 -> B1 -> D2 -> C4
C4 -> A3 -> B1 -> D2
C4 -> D2 -> B1 -> A3
Zauważmy, że po każdej z tych tras, jedynym następnym ruchem konika będzie ruch na jedno z pól B2 lub C3 - przy czym pola A2,B4,C1,D3 są nieodwiedzone - sprzeczność.
Przeprowadzony dowód nie wprost potwierdza niemożliwość pokonania trasy w sposób podany w zadaniu.
Dowód nie wprost - przypuśćmy, że da się tak zrobić:
a) Konik zaczyna swoją drogę na polach różnych od pól narożnych
Ponieważ musi odwiedzić każde pole, zatem musi w szczególności odwiedzić pola narożne. Rozpatrzmy przypadek gdy pierwszym polem narożnym jakie odwiedzi będzie pole A1 (pozostałe analogicznie). Na pole A1 da się dojść tylko z pól B3 i C2 - przyjmijmy, że konik przeskakuje na A1 z pola B3. Wówczas z warunków zadania konik musi się poruszyć na C2. Jeśli teraz konik nie poruszy się na D4 - wówczas nie odwiedzi tego pola z nałożonymi warunkami zadania. Jeśli konik poruszy się na D4 - wówczas z tego pola musi się poruszyć na jedno z pól B3, C2 (gdyż z wybrania A1 jako pierwszy narożnik mamy jeszcze nie odwiedzone pola A4,D1) - sprzeczność z warunkami zadania. Zatem w przypadku a) otrzymaliśmy sprzeczność.
b) Konik zaczyna swoją drogę na jednym z pól narożnych.
Dla ustalenia uwagi niech będzie to A1. Z tego pola może się on poruszyć na B3 lub C2 - przyjmijmy ze względu na środkowosymetryczność szachownicy, że następnym punktem trasy jest B3. Przypuśćmy, że następnym punktem wizyty nie jest D4. Wówczas prawdziwa jest jedna z ewentualności:
(*) konik jako pierwsze z pól B2,C2,C3 odwiedza pole C2 - wówczas rozumując jak w a) następnym polem drogi będzie pole D4 - ale prosto zauważyć, że konik stąd już się ruszyć nie może, a nie odwiedził on jeszcze pól B2,C3 - sprzeczność
(**) konik jako pierwsze z pól B2,C2,C3 odwiedził pole B2 lub C3 - wówczas prosto spostrzec (jak w punkcie a)), że w swoich najbliższych czterech ruchach złoży wizytę na polach A4,B2,C3,D1 kończąc na jednym z pól A4 lub D1 - teraz konik nie ma możliwości ruchu, a nie odwiedził C2 - sprzeczność
Zatem wizyta konika przebiega: A1 -> B3 -> D4 -> C2. Zauważmy [***], że jeśli któreś z pól A2,A3,B1,B4,C1,C4,D2,D3 zostanie nieodwiedzone, a konik znajdzie się na B2 lub C3 - to dostaniemy sprzeczność, gdyż podobnie jak w (**) "zaklinuje" się w jednym z rogów nie odwiedzając któregoś z pól. Z C2 konik może przebyć następujące drogi (uwzględniając rozumowanie [***]):
A3 -> C4 -> D2 -> B1
A3 -> B1 -> D2 -> C4
C4 -> A3 -> B1 -> D2
C4 -> D2 -> B1 -> A3
Zauważmy, że po każdej z tych tras, jedynym następnym ruchem konika będzie ruch na jedno z pól B2 lub C3 - przy czym pola A2,B4,C1,D3 są nieodwiedzone - sprzeczność.
Przeprowadzony dowód nie wprost potwierdza niemożliwość pokonania trasy w sposób podany w zadaniu.