GoldenLine
Zaloguj się
Mariusz Niemczyk

Mariusz Niemczyk usmiech nr 4 ;)

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Witajcie ;)

Czy skoczek szachowy może odwiedzić wszystkie pola połówki szachownicy (każde pole jeden raz), i wrócić na pole, z którego wyrusza? Podać przykładową trasę lub wykazać, iż jest to niemożliwe.

Miłego łamania głowy,
m.
Link do wypowiedziLink

konto usunięte

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Nie może, gdyż w zadaniu jest mowa, że KAŻDE pole musi być odwiedzone tylko jeden raz, a jednocześnie z zadania wynika, że POLE STARTOWE musi być odwiedzone dwa razy [start/meta]. Stąd zadaniu brak wewnętrznej spójności ;-)))

R.

ps. odwiedzane pole = pole na którym kończy się ruch, czy też wszystkie pola "pośrednie" w trakcie wykonywania ruchu wraz z polem kończącym ruch ?
Link do wypowiedziLink
Mariusz Niemczyk

Mariusz Niemczyk usmiech nr 4 ;)

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Hej ;)

Gdy na jakimś etapie (poleX1 -> poleX2) skoczek wykonuje np. ruch z A1 na B3, to znaczy że odwiedza pola A1 i B3, a pola typu A2, A3, B2, B1 - w tym momencie nie grają roli (wszak skoczek przemyka 'ponad nimi', nie wiadomo dokładnie jak :D)

Dla jasności: gdyby istniała trasa, o którą pytam, skoczek mógłby skakać po połówce szachownicy zaliczając wszystkie 32 pola:

pole1 -> pole2 -> pole3 -> (....) -> pole30 -> pole31 -> pole32 -> pole1 -> pole2 -> pole3 ....

Powodzenia! ;)
Link do wypowiedziLink

konto usunięte

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Nie może ---> dowód: kilkudniowe zmagania z brykajacym skoczkiem ;-))Rafal Komarnicki edytował(a) ten post dnia 17.09.07 o godzinie 11:10
Link do wypowiedziLink
Mariusz Niemczyk

Mariusz Niemczyk usmiech nr 4 ;)

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Odpowiedź: prawdiłowa, chociaż dowód - mało jasny ;)

Sprawdziłeś Rafale (programowo?) wszystkie możliwości? :) A co na planszy 4x12? Nie pokusiłbyś się na jakieś uogólnienie? :)

I dodatkowo: czy gdyby nie było warunku, iż skoczek musi mieć możliwość powrotu na pole startowe, mógłby on odwiedzić 'jednorazowo' wszystkie 32 pola (skąd startując?)? :D
Link do wypowiedziLink

konto usunięte

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Zacznę od końca: gdyby nie było warunku, że musi wrócić ... to byłoby to wykonalne, gdyby wystartował z jednego z rogów ... tak swoja drogą już w pytaniu wskazałeś odpowiedź - pytając z jakiego pola co sugeruje, że jest to możliwe, a należy jedynie znaleźć to pole ;-)

Programowo sprawdziłem --> zaprogramowałem swój umysł, aby po kolejnej nieudanej próbie znaleźć motywację do kolejnej ;-))

Natomiast jeże chodzi o możliwość zaliczenia wszystkich pól na szachownicy 4x12...to takze jest to niemożliwe, bo:
- intuicyjnie, czyli "czucie i wiara" --> szachownica 4x12 to takie "wąskie gardło" ograniczające ruch skoczka...łatwo poruszać się wzdłuż dłuższego boku, gorze wzdłuż krótszego, nie wspominając o zawracaniu ;-))
- a teraz "mędrca szkiełko i oko" ---> da się to zrobić na powierzchni 3x12, 5x12, 6x12 itd, a jednocześnie nie da sie dla powierzchni 3x11, 3x9, 3x7 stąd wnioskuje, że przy powierzchni opisanej jako YxZ dla YiZ nieparzystych nie da sie tego zrobić.

R.Rafal Komarnicki edytował(a) ten post dnia 17.09.07 o godzinie 16:53
Link do wypowiedziLink
Mariusz Niemczyk

Mariusz Niemczyk usmiech nr 4 ;)

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Niedawno znalazłem w Wiki coś, co może okaże się przydatne... przed dalszym brykaniem ;)

http://en.wikipedia.org/wiki/Knight's_tour

ps. mam problem ze zrobieniem linka do strony z apostrofem...Mariusz Niemczyk edytował(a) ten post dnia 17.09.07 o godzinie 22:07
Link do wypowiedziLink

konto usunięte

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Mariusz N.:przed dalszym brykaniem ;)

http://en.wikipedia.org/wiki/Knight's_tour[/edited]

Cytuję:
"For any m × n board with m less than or equal to n, a closed knight's tour is always possible unless one or more of these three conditions are true:

m and n are both odd
m = 1, 2, or 4; m and n are not both 1
m = 3 and n = 4, 6, or 8 "

Czyli ja wpadłem jedynie na 1 warunek --> m,n nieparzyste ;-))Rafal Komarnicki edytował(a) ten post dnia 18.09.07 o godzinie 08:56
Link do wypowiedziLink
Tomasz S.

Tomasz S. Digital Marketing/
Recruitment/
Management,
www.staskiewi...

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

Może tak w kwestii formalnej.
Dowodem NIE jest:
a) próbowałem i nie udaje mi się
b) cytat z wikipedii
Link do wypowiedziLink
Mariusz Niemczyk

Mariusz Niemczyk usmiech nr 4 ;)

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

;)

Moje rozwiazanie wyjsciowego problemu bylo nastepujace:

Pokolorujmy 4x8 tak jak ponizej:

xoxoxoxo
xoxoxoxo
oxoxoxox
oxoxoxox

Dlaczego tak? Otoz jesli skoczek bedzie poruszac sie wmysl zasady:
wiersze: skrajny->srodkowy->skrajny->srodkowy->... to bedzie poruszac sie po polach jednego koloru... Poniewaz nie jest mozliwy ruch: skrajny->skrajny, nie bedzie mozliwe pokonanie calej trasy i powrot na pole startowe (dlaczego?). Mowiac o uogolnieniu - mialem na mysli 4xn;)

Teorii skoczka z podanej www nie przegladalem (pewnie kiedys zajrze:) A zadanie podrzucil na pl.sci.matematyka kilka lat temu Wlodzimierz Holsztynski.
Link do wypowiedziLink
Tomasz S.

Tomasz S. Digital Marketing/
Recruitment/
Management,
www.staskiewi...

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

To nie wyczerpuje dowodu - skoczek może poruszać się przecież również środkowy-środkowy.
Link do wypowiedziLink
Mariusz Niemczyk

Mariusz Niemczyk usmiech nr 4 ;)

Temat: skoczek brykający po połówce szachownicy (czyli: 8x4)

To nie wyczerpuje dowodu - skoczek może poruszać się przecież również środkowy-środkowy.

Stąd moje pytanie: "dlaczego" ;)

Gdyby mial sie pojawic ruch: srodkowy->srodkowy, to, zeby odwiedzic wszyskie 32 pola, polem 1ym i 32im na jego trasie musialyby byc jakies pola na wierszach skrajnych (dlaczego? :D)...Mariusz Niemczyk edytował(a) ten post dnia 20.09.07 o godzinie 01:42
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj