marcin: Tabliczkę czekolady, której jednakowe prostokątne cząstki ułożone są w k rzędów po m w rzędzie, przecięto wzdłuż przekątnej. Ile cząstek zostało przeciętych? Nie mam nawet żadnego pomysłu, a raczej żaden się nie sprawdza.

pp: uuu. ciezko

b.: Hmm wydaje mi się, że jeśli m i k są względnie pierwsze, to przeciętych zostanie m+k-1 kostek. Nie widzę w tej chwili, jak to uzasadnić, jestem jednak prawie pewien, że to prawda -- zastanów się więc sam No a jeśli nie są względnie pierwsze, to niech d=NWD(m,k), dzielimy naszą czekoladę na d² kawałków o wymiarach m/d x k/d i stosujemy początkową obserwację do każdego z kawałków (m/d i k/d są już względnie pierwsze).

pp: a jeżeli jedna jest pierwsza, a druga nie i np. NWD jest 1, czyli nic nam nie da?

b.: jeśli NWD(m,k)=1, to liczby m i k są *względnie* pierwsze (taka dokładnie jest definicja liczb względnie pierwszych )

marcin: O widzę, że coś się zrodziło, czyli np. mamy czekoladę 121 x 11 NWD=11 to co? rozważamy czekoladę 11x1, w której wychodzi 11 przeciętych kawałków i co? jak to się ma do 121x11, ile będzie przeciętych "czekoladek", 121?

marcin: dobra, mam wstępny dowód, zobaczcie czy prawidłowy: Teza: to co pisał b. (btw. thx) Dowód: Aby dana czekoladka (czyli kawałek czekolady) był przecięty przez przekątną musi ona przechodzić przez 2 punkty tej czekoladki, tzn. musi wejść poziomo i wyjść pionowo (chodzi o boki tych kawałków pionowe i poziome, tu zależy jak się umówimy, ale to nie ma znaczenia). 1. Rozważmy przypadek gdzie w czekoladzie "k" x "m", w której k i m nie mają żadnego wspólnego dzielnika prócz 1 (gdyż w przeciwnym wypadku przekątna przechodzi przez punkt na krańcach czekoladek, tym samym ich nie przecinając), mamy "2k" wejść i "2m" wyjść, ale pamiętajmy, że krańce liczyliśmy podwójnie, a jak wcześniej założyliśmy wchodzi poziomo wychodzi pionowo (czyli w pierwszej cząstce wchodzi a w ostatniej wychodzi, punkty tam się nie nakładają). Uzyskujemy wzór 2k+2m-2, który podaje nam liczbę wszystkich przecięć. Każda przecięta kostka czekolady ma 2 przecięcia, więc liczba kostek wyraża się wzorem: k+m-1 przy założeniu, że NWD(k,m) = 1 2. Jeżeli k i m ma NWD(k,m)>1 to ... i jak to ująć tam jest pewna powtarzalna się ilość takich tabliczek czekolady o wymiarach "w" na "s" gdzie NWD(w,s) = 1 i sprowadza się to do pierwszego przypadku.

b.: Jest w zasadzie ok, choć nie musi ,,wejść poziomo, wyjść pionowo''. Popatrz np., jak przekątna przecina np. czekoladę 2x3 -- niekoniecznie tylko ,,poziomo-pionowo''. Po prostu, patrzymy na przecięcia przekątnej z kwadracikami -- tych ,,poziomych'' jest 2k (jeśli liczymy narożniki), pionowych 2m. Każda kostka czekolady jest albo w ogóle nieprzecięta, albo przecięta w 2 miejscach (innej możliwości nie ma, bo m,k - względnie pierwsze). Kolejność przecięć (poziomo/pionowo) nie gra roli. Czyli przeciętych kostek jest (2k+2m-2) / 2 odejmujemy 2, bo jak zauważyłeś, 2 narożniki są liczone podwójnie. 2. Hmm, jak NWD(k,m)=d>1, to patrzymy na kawalek k/d, m/d -- on zawiera k/d+m/d-1 przeciętych kostek (z 1. części dowodu). Trzeba rozpatrzyć d takich kawałków, czyli wynik to d*(k/d+m/d-1) = k+m-NWD(k,m)

marcin: ok, thx