marcin: Z kartki papieru w kratkę o wymiarach 29x29 kratek wycięto 99 kwadratów 2x2. Wykaż, że można wyciąć jeszcze jeden taki kwadrat. Wszystkie cięcia przeprowadzane są wzdłuż linii wyznaczających kratki. Mam chyba rozwiązanie, ale nie wiem czy jest w pełni przekonujące i prawdziwe. Wydaje mi się, że najbardziej niekorzystnym sposobem wycięcia tych kwadratów jest wtedy, gdy wycinamy je co 1-kratkową przerwę (kwadrat 2x2 a na około niego takie obramowanie o grubości 1, bo 2 nie może być, bo wtedy możemy wyciąć już kolejny kwadrat). Zbadajmy więc ile wtedy 2 mieści się w szerokości i długości kartki (są takie same): Wychodzi coś takiego (1 - ta przerwa jedno-kratkowa, 2 - bok kwadraciku, który wytniemy): (1 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 Wychodzi 10 dwójek, bo po 9 takich "obramowanych" dwójkach pozostają nam 2 kratki (29 - 9*(2+1) = 2), czyli miejsce na kolejny bok wycinanego kwadraciku. Tak samo jest w szerokości i długości, bo kartka jest 29x29, więc przy najgorszym wycięciu zmieści się 100 kwadratów 2x2. Cnd. Dobrze?

Aneta: mi się wydaje że trzeba by założyć że te "szpary" między kwadratami są największe możliwe - tzn 1 kratka - tak jak masz - jak szpara większa to się tam kwadrat zmieści no to wygląda że dobrze

b.: Zamiast mówić o ,,najgorszym przypadku'', co zwykle jest nie do końca przekonujące, lepiej chyba argumentować tak: 1. narysuj sobie 100 kwadracików w sposób, który podałeś, tzn. z odstępami o 1. Pokolorujmy te ustalone 100 kwadracików na zielono (żeby ułatwić wysłowienie rozwiązania ) 2. i teraz zauważ, że jeśli jakkolwiek wytniesz z kartki 99 kwadracików, to każdy wycięty kwadracik ,,popsuje'' tylko jeden zielony kwadrat! To dzięki temu, że pomiędzy zielonymi są odstępy. no i wniosek: jeden zielony kwadrat pozostanie nienaruszony -- i można go wyciąć z kartki

marcin: "2. i teraz zauważ, że jeśli jakkolwiek wytniesz z kartki 99 kwadracików, to każdy wycięty kwadracik ,,popsuje'' tylko jeden zielony kwadrat! To dzięki temu, że pomiędzy zielonymi są odstępy. no i wniosek: jeden zielony kwadrat pozostanie nienaruszony -- i można go wyciąć z kartki" Z kartki 29x29 można wyciąć aż 196 kwadratów 2x2, więc trzeba rozpatrzeć przypadek kiedy da się ich wyciąć najmniej i zobaczyć czy będzie to więcej niż 99. Poza tym jeżeli to sobie namaluje to co z tego? w polu, w którym jest zielony kwadrat mogę zaznaczyć aż 4 kwadraty 2x2, "popsuć" można tylko poprzez wycięcie zielonego kwadratu inaczej możemy obok wyciąć jeszcze trzy...więc sprowadza się to do tego o czym ja mówiłem, czyli do najgorszego przypadku.

b.: nie nie nie, nie zrozumieliśmy się ,,popsuty'' -- chodziło mi o taki, który został choć częściowo wycięty jeszcze raz: 1. malujemy na zielono 100 kwadratów 2x2 w taki sposób, aby żadne 2 się nie stykały (czyli było 1 pole odstępu pomiędzy sąsiednimi) 2. wycinamy jakkolwiek 99 kwadratów -- tak jak w zadaniu napisane, znaczy jakkolwiek 3. pytanie: ile zielonych kwadratów zostało naruszonych (popsutych)? odp: co najwyżej 99 bo wycinając jakkolwiek kwadrat 2x2 możemy wyciąć pola z TYLKO JEDNEGO ZIELONEGO KWADRATU -- nie mozna tak wyciąc kwadratu 2x2, żeby zachodził on o 2 zielone -- bo między zielonymi jest 1 odstępu stąd wniosek, że co najmniej 1 zielony kwadrat pozostał nienaruszony (być może więcej, bo jak sam piszesz ,,w polu, w którym jest zielony kwadrat mogę zaznaczyć aż 4 kwadraty 2x2'' -- zgadza się, ale to oznacza, że nienaruszonych zielonych kwadratów zostanie nawet więcej) a to oznacza, że jakkolwiek się nie wytnie 99 kwadratów, będzie można wyciąć jeszcze 1 (właśnie ten zielony, nienaruszony)

marcin: To zdecydowanie łatwiej jest sprawdzić najgorszy przypadek, w którym to można wyciąć w sumie 100 kwadratów, czyli 99 kwadratów + 1. Dlaczego? Bo to jest najgorzej i można wyciąć już tylko lepiej - zawsze ten co najmniej 1 kwadrat zostanie w rezerwie do wycięcia. Najgorszy przypadek jest wtedy gdy pomiędzy wycinanymi kwadratami 2x2 jest największy możliwy odstęp, czyli w tym przypadku odstęp równy jednej kratce. Wtedy w szerokości i długości zmieści się 10 kwadratów 2x2 - widzimy to z prostego wyliczenia na dole, lub jeżeli ktoś woli możemy narysować jeden "wers". 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 Z kolejnego łatwego obliczenia 10 * 10 uzyskujemy 100, czyli liczbę kwadratów 2x2 jakie możemy wyciąć w najgorszym przypadku.

b.: tylko rzecz polega na tym, że to nie jest do końca przekonujące z tym najgorszym przypadkiem -- bo skąd wiadomo, że on taki najgorszy? nie daj się zwieść, tu to pewnie prawda, ale można się łatwo pomylić w bardziej podchwytliwym zadaniu w tym rozwiązaniu, które napisałem nie ma takiego problemu właściwie to są b. podobne rozwiązania, tylko że zamiast mówić, że tak rozmieszczone 100 kwadratów to ,,najgorszy przypadek'', jest inny argument, łatwiejszy do zweryfikowania

marcin: Najgorsze układy (które są sobie równoważne): 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 lub (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 (1) 2 2 Pokazują, że to jest najgorszy przypadek. Jak niby "bardziej" można zmniejszyć ilość dwójek w tym rozkładzie, kiedy nie może być liczb większych od 2 i nie może być paru jedynek po kolei? Jedyna opcja to wsadzić po między dwójki te jedynki i koniec.

b.: Ok, to w takim razie wyjaśnij mi jeszcze raz o co pytałeś na forum?

marcin: Chciałem dowiedzieć się, czy jest dobrze i ewentualnie zobaczyć inne sposoby rozwiązania zadania.

b.: Moim zdaniem, nie jest do końca dobrze. Właściwie pokazujesz, że to jest możliwe w 1 konkretnym przypadku, i próbujesz przekonać, że ten przypadek jest najgorszy możliwy. A miałeś pokazać, że da się wyciąć jeszcze jeden kwadracik w *każdym* przypadku. Zwróć uwagę, że te kwadraciki mogą być wycinane różnie, niekoniecznie tak samo w każdym wierszu. Np tak: (# oznacza wycięte, = oznacza niewycięte) =##====##=##=.... =##=##=##=##= ====##======= =##====##=##= =##=##=##=##= ====##======= ##=##==##=##= ##=######=##= =====##====== ... (narysowałem tylko fragment, jak to może wyglądać) i jak widać, są różne schematy możliwe: np. (1) 2 (4) 2 (1) 2 (1) w pierwszym wierszu no i skąd wiadomo, czy nie da się tak pomieszać tych kwadracików w sposób mniej regularny (znaczy nie tak równo w rzędach i kolumnach), żeby się już nie dało wyciąć setnego kwadracika? z rozwiązania które przedstawiłem to widać, a z Twojego - obawiam się - nie