112 łebków
Palaczem, podpalaczem ani nadpalaczem nie jestem, a w kuchence gazowej mam zapalnik elektryczny, więc z zapałek korzystam raz w roku – 1 listopada, zapalając znicze na cmentarzu. Gdyby nie to, sądziłbym że to towar reglamentowany albo historyczny jak hubka i krzesiwo lub lampa naftowa. Natomiast nieco częściej i chętnie trafiam tu i ówdzie na tzw. zapałczanki, czyli łamigłówki, w których patyczki z łebkami przydają się jako rekwizyty, nawet jeśli praktyczne korzystanie z nich nie jest konieczne. Przykładem poniższa układanko-zabieranka.
Ze 112 zapałek utworzono kwadrat podzielony na 49 małych jednostkowych kwadratów. Wszystkich zapałczanych kwadratów (różnej wielkości) jest tu jednak znacznie więcej. Ile?
A teraz zabieranka. Z tego układu należy usunąć jak najmniej zapałek w taki sposób, aby nie pozostał w nim żaden kwadrat. Ile zapałek wystarczy zabrać?
Komentarze
Liczba kwadratów układa się kwadratowo. Mamy:
1 kwadrat 7×7
4 kwadraty 6×6
9 kwadratów 5×5
16 kwadratów 4×4
25 kwadratów 3×3
36 kwadratów 2×2
49 kwadratów 1×1
Czyli w sumie 140.
Zabrałam 27 zapałek. Ale pewnie można by ten wynik poprawić.
Tak, można.
mp
Wygląda na to, że nie wiem, jak do tego doszedłem, ale rozwiązałem 😉
Wynik to 28.
Rozwiązanie jest na tyle interesujące, że pokuszę się o wzór ogólny na ilość rozwiązań dla układu o boku N:
N*N/2+N/2
Dla N nieparzystych odjąć 1.
Jak wiemy każda zapałka ma dwa końce i powyższy kwadratowy układ aż prosi się o następujące pytanie:
Jaka jest największa możliwa do osiągnięcia ilość miejsc w których spotyka się jednocześnie trzech łebków?
Kwadratów jest 140 (= suma kwadratów liczb 1 do 7)
Udało mi się znaleźć rozwiązanie z brakiem 27 zapałek: https://app.box.com/s/hfmm98m8o4xse9l29trey4bzgw47w3e0
ale nie jestem pewnien czy nie da się mniej…
Proste:
jeśli nie 28 to 27.
Dzieło sztuki nowoczesnej tutaj:
http://pokazywarka.pl/y9l91c/
Spiralnie do środka usuwana co druga zapałka, a potem jeszcze trzy (żółte).
Liczba wszystkich kwadratów ukrytych w kratce n x n to:
K(n) = 1*1+2*2+…+(n-1)*(n-1)+n*n
np. K(7) = 140
Liczba zapałek wystarczających do „totalnej dekwadratyzacji” siatki n x n to:
z(n) = n*(n+1)/2
np. z(7) = 28
I nawet wiadomo dlaczego.
Ale ujawnienie postu apartado sugeruje, że nie jest ona najmniejsza. Trzeba jeszcze pomyśleć nad minimum…
Witam!
Teza 1:
Należy usunąć nie mniej niż 25 zapałek
Dowód:
Usunięcie jednej zapałki likwiduje co najwyżej dwa jednostkowe kwadraty.
Usunięcie 24-ech zapałek likwiduje co najwyżej 48 jesnostkowych kwadratów.
Do zlikwidowanie 49-ego kwadratu potrzebujemy usunąć 25-tą zapałkę.
Teza 2:
Neleży usunąć minimum 26 zapałek
Dowód
Nie wiem czy uda się zrozumiale, ale spróbuję.
Nasz układ pokolorowałem niczym szachownicę na czarne i białe kwadraty.
Liczba czarnych: 25
Liczba białych: 24
Załóżmy, że wystarczy usunąć 25 zapałek.
Każda kolejna usuwana zapałka musi likwidować dwa sąsiednie (czyli o różnych kolorach) kwadraty.
Po usunięciu 24-ech zapałek na planszy pozostał jeden jednostkowy kwadrat (czarny)
Na pewno nie usunęliśmy żadnej zapałki z zewnętrznego obwodu naszego układu. To oznacza, że ostatni pozostawiony (czarny) kwadrat musi znajdować się na brzegu naszego układu. I ta 25-ta usuwana zapałka jeest właśnie tą z zewnętrznego obwodu.
Bez straty ogólności mamy dwie możliwości:
1. Ostatni kwdrat jest w samym rogu układu (pierwszy kwadrat pierwszego rzędu w wyjściowym układzie złożonym ze 112 zapałek)
2. Ostatni kwadrat to trzeci kwadrat pierwszego rzędu w wyjściowym układzie złożonym ze 112 zapałek.
Wróćmy teraz do początkowgo układu (112 zapałek)
Po usunięciu zapałki z zewnętrznego obwodu (w zgodzie albo z punktem 1 albo punktem 2 powyżej) musimy odpowiednio usunąc jeszcze 24 zapałki.
I tu pozostawię miejsce do poszukania rozwiązania dla wszystkich czytelników (opisywanie stałoby się zbyt trudne). Ale ja doszedłem do wniosku, że niezależnie od sposobu usuwania kolejnych zapałek (z zachowaniem zasady, że każde usunięcie zapałki likwiduje dwa sąsiednie kwadraty jednostkowe) zawsze natkniemy się na moment, że na planszy pozostanie nam kwadrat o polu równym 2×2 kwadratów jednostkowych. I zlikwidowanie go będzie wymagalo usuniecia 26-tej zapałki.
Mamy więc SPRZECZNOŚĆ
Teza 3
Wystarczy usunąć 26 zapałek
Dowód:
Wystarczy spojrzeć na zdjęcie:
https://zapodaj.net/8bd8331e1123a.jpg.html
Pozdrawiam
Bardzo ładnie. Piątka.
mp
@apartado
Układ zapałczany aż się prosi o wiele różnych rozstrzygnięć typu np.:
Jaka jest największa możliwa ilość miejsc, w których spotykają się jednocześnie
– co najmniej 2 łebki?
– dokładnie 2, 3 lub 4 łebki?
Widzę że te układy zapałczane są jak jakaś sieć neuronowa – kopalnia tematów!
PS. „Sztuka nowoczesna” zawiera kwadrat 7×7 – trzeba usunąć jeszcze 1 zapałkę.
Jeśli się nie kropnąłem w liczeniu usuniętych zapałek ani nie przeoczyłem ukrytego kwadratu to faktycznie wystarczy usunąć 27 zapałek.
https://pokazywarka.pl/xhketa/
Ale kto wie… może wystarczy 26?
Uwolniłbym zawczasu, gdyby nie to domniemanie 26.
mp