Krótkie klepki
W sierpniowym „Świecie Nauki” znalazło się zadanie mniej więcej takiej treści:
Diagram 10×10 należy szczelnie pokryć klepkami 1×n. Cyfra w polu diagramu oznacza długość klepki (n), która powinna zakryć to pole. Klepki takiej samej długości nie mogą się ze sobą stykać. Żadne dwie klepki nie mogą się stykać tylko rogami. W rozwiązaniu wystarczy podać liczbę klepek 1×2.
Niestety, autor zapomniał o jednym warunku, więc rozwiązania się „rozmnożyły”. Ów warunek powinien brzmieć: n = 1, 2, 3 lub 4. Zatem długość najkrótszych klepek jest równa ich szerokości (są kwadratami 1×1), a najdłuższych wynosi 4.
Teraz poniższe zadanie (inne niż w „ŚN”) ma jedno rozwiązanie, zatem liczba klepek 1×2 będzie konkretna. Jaka?
Komentarze
12. Bardzo fajne zadanie 🙂
Pozdrawiam.
Dwanaście
12
1×2=12 🙂
Fajne
a
12 klepek 1×2
Jest 12 klepek 1×2 (3 poziome i 9 pionowych) 🙂
Zwróćmy uwagę na to, że nie wszystkie cyfry są konieczne, żeby uzyskać tylko jedno rozwiązanie.
Dojdziemy do takiego samego rozwiązania (chociaż zajmie nam to trochę więcej czasu), jeżeli usuniemy czwórkę z lewej części diagramu.
W rzeczywistości potrzebujemy tylko połowy z dwunastu podanych cyfr.
A których sześciu konkretnie? Chyba nie dowolnych… Pomijam, że zadanie stanie się gehenną, ale trudno mi uwierzyć, że będzie jednoznaczne.
mp
Nie, nie dowolnych.
Potrzebujemy jedynki, trójki z dwóch pierwszych kolumn oraz dwójke z ostatniego wiersza.
Zadanie będzie jednoznaczne.
Z tymi cyframi zadanie idzie jak po sznurku, bez rozwidleń w ślepe uliczki. Po wyrzuceniu kilku cyfr może da się zachować jednoznaczność ale na pewno pojawią się rozwidlenia.
Pozwoliłem sobie napisać program komputerowy, który znajdzie wszystkie podzbiory danych wejściowych, dla których rozwiązanie jest jednoznaczne (mówiąc o jednoznacznym rozwiązaniu mam na myśli konkretny układ klepek w diagramie, a nie odpowiedź na pytanie „Ile jest klepek 1×2?”). Dane oznaczyłem kolejnymi liczbami naturalnymi (startując od zera!), od góry do dołu, od lewej do prawej, co jest widoczne na obrazku: http://www.gg.pl/dysk/vj6naGYsdR1Qvz6naGYsZTQ/klepki.jpg
W efekcie otrzymałem osiem konfiguracji danych wejściowych, dla których rozwiązanie jest jednoznaczne:
{0,1,3,5,6,8,9,11}
{0,2,3,6,7,9}
{0,3,4,5,6,9}
{0,3,4,6,7,9}
{0,3,5,6,7,9}
{0,3,5,6,9,10}
{0,3,6,7,8,9}
{0,3,6,7,10}
Powyższe potwierdza słuszność wpisów poprzedników, którzy twierdzili, że wystarczy 6 odpowiednich liczb. Ostatnia pozycja pokazuje, że wystarczy nawet 5 liczb, a zadanie wygląda wtedy tak: http://www.gg.pl/dysk/y0J_FVgwHBJQykJ_FVgwDDs/klepki-hard.jpg
Umieszczam również odnośnik do kodu programów, których użyłem do obliczenia powyższych: http://www.gg.pl/dysk/FUzIN-h0TVtQFEzIN-h0XXI/klepki.zip
@Spytko z Melsztyna
Myślę, że przy 12 cyfrach też bywają rozwidlenia, tylko że ślepe uliczki są krótkie.