Biorąc pod uwagę szachownicę 8×8, Twoim celem jest „pokrycie” każdego miejsca na szachownicy jak najmniejszą liczbą elementów. Pole jest „zakryte”, jeśli jest na nim kawałek lub jeśli kawałek na planszy można przenieść na to pole jednym ruchem.
Banalnie prostym rozwiązaniem byłoby zakrycie planszy z 64 sztukami. Jeśli umieścisz figurę na każdym kwadracie, każde pole jest oczywiście zakryte.
Mniej trywialnym rozwiązaniem jest 8 – wypełnij cały rząd lub kolumnę wieżami. Oczywiście każda wieża może pokryć wszystkie przestrzenie w swoim rzędzie lub kolumnie, więc plansza jest zakryta.
Czy można to zrobić przy użyciu mniej niż 8 pionów? Jeśli tak, jaka jest wymagana minimalna liczba elementów?
Komentarze
- Zobacz powiązaną dyskusję pod adresem meta meta.puzzling.stackexchange.com/questions/63/ …
Odpowiedź
Tak. Minimalna wymagana liczba elementów to 5 .
5 hetmanów można umieścić tak, aby obejmowały co miejsce na planszy, jak w poniższym przykładzie:
okładki pełną szachownicę 8×8.
Istnieje 12 takich aranżacji, wraz z obrotem i odzwierciedleniem każda z nich.
Edycja: Powyższe dowodzi, że 5 dam wystarczy, ale nie dowodzi, że 4 damy to za mało. Zgodnie z pytaniem MathOverflow i odpowiedziami na nie, nie ma łatwego dowodu logicznego lub matematycznego, ale zostało to udowodnione poprzez pełną ocenę wszystkich możliwych ułożeń królowych na tablicy . Sekwencja OEIS A075458 podaje minimalną liczbę matek wymaganych dla dowolnej planszy kwadratowej od $ 1 \ times1 $ do 18 $ \ times18 $ .
Komentarze
- Ile z tych ustaleń zagraża również kwadraty, na których stoją królowe? (jeśli spojrzymy na powyższy obrazek, królowe nie ' nie grożą sobie nawzajem ' kwadratami. jeśli w jakiś sposób jedna z nich zostały przechwycone po przejściu na tę pozycję, ' nie masz już prawidłowej odpowiedzi)
- Rozumiem, że ' postępuję zgodnie z regułami pytania, a ja ' nie kwestionuję tego. Mój powyższy komentarz był tylko burzą mózgów.
- To ' to inne, choć wciąż interesujące pytanie.
- 5 królowych, fajnie. Czy jest to w ogóle możliwe, gdy ogranicza się do standardowych elementów gry?
- @Glitch_Doctor To ' byłby interesującym problemem do rozwiązania. Może zadasz pytanie na ten temat?
Odpowiedź
Ten typ szachowej układanki jest znany jako problem z dominacją , a jak wskazuje @Xynariz, do szachownicy 8×8 potrzeba tylko pięciu dam. Warto również zauważyć, że pięć hetmanów wystarcza również na plansze 9×9, 10×10 i 11×11, jak pokazano na poniższym schemacie zaczerpniętym z rosyjskiej książki o układankach szachowych znalezionej tutaj .
Odpowiedź
Zgadzam się, że 5 hetmanów jest odpowiedzią. Ale oto prostsze rozwiązanie problemu
Rozważ X jako pozycje hetmanów zaznaczone na szachownicy
Komentarze
- Tak, to jedno z 12 rozwiązań wymienionych w mojej odpowiedzi powyżej. Nie ' nie wiem, czy ' nie nazywam tego " łatwiejszym rozwiązaniem ", ale jest zdecydowanie łatwiejszy do zapamiętania. 🙂
Odpowiedź
Rozwiązanie: umieść hetman na każdym z pięć czerwonych kropek pokazanych poniżej. Wszystkie kwadraty na planszy są następnie przykrywane przez co najmniej jedną z tych królowych.
Komentarze
- stary… po prostu narysuj poziome, pionowe i ukośne linie wzdłuż wszystkich czerwonych kropek (królowych). … wszystkie kwadraty są zakryte ….
- Ja ' zastanawiam się, dlaczego ktoś dodał nową odpowiedź na pytanie sprzed prawie trzech lat, podając niczego, co nie zostało uwzględnione w innych odpowiedziach, a także nie zadając sobie trudu, aby wyjaśnić swoją odpowiedź (chociaż edycja pomogła znacznie).