Zanim połamię ołówek
Postanowiłem pozostać w podzbiorowym klimacie dwóch poprzednich wpisów. Zacznę od uogólnienia zadania sprzed trzech dni:
Proszę podać takie cztery liczby naturalne (bez zera), z których żadna nie będzie podzielna ani przez 3, ani przez 7, zaś suma każdych dwóch z nich będzie podzielna przez 3 lub przez 7.
Rozwiązań jest nieskończenie wiele, ale, jak to często bywa, także w matematyce, nie tylko o to chodzi, by złowić króliczka, ale także by go elegancko gonić. W tym przypadku elegancka pogoń „na piechotę”, czyli bez komputerowego wsparcia, polega na skorzystaniu z grafu, który wygląda tak:
Rysunki są niby dwa różne, ale graf jeden. Pisząc półżartem, mamy do czynienia z bliźniakami, a pisząc „przemądrzale” – z obiektami identycznymi izomorficznie. Polecam prawy jako milszy dla oka, bo bez przecinających się krawędzi. Graf zwany jest pełnym, ponieważ każdą parę wierzchołków łączy dokładnie jedna krawędź.
Jeśli wierzchołki oznaczymy właściwymi liczbami niepodzielnymi przez 3 i 7 – takimi, że każda krawędź będzie odpowiadać podzielnej przez 3 lub 7 sumie liczb przy wierzchołkach, które łączy – to taka konstrukcja będzie rozwiązaniem zadania. Wpisanie dwóch liczb jest trywialne, trzeciej i czwartej odrobinę trudniejsze, ale w sumie to pestka.
Pora na małą modyfikację:
Proszę podać pięć takich liczb naturalnych (bez zera), z których żadna nie będzie podzielna ani przez 3, ani przez 7, zaś suma każdych dwóch będzie podzielna przez 3 lub przez 7.
Graf pełny wzbogaci się o jeden wierzchołek:
Nie da się go niestety narysować tak ładnie, czyli „bezkolizyjnie”, jak tego powyżej z prawej strony, bo nie jest planarny, czyli na płaszczyźnie przynajmniej dwie jego krawędzie zawsze się przetną. Obserwowałem kiedyś bardzo młodego matematyka, który próbował jakoś zlikwidować przecięcia, czyli obalić twierdzenie Kuratowskiego. Wyobrażał sobie, że krawędzie są ze sznurka i przez kilka minut „wyciągał” je na zewnątrz. W końcu cisnął ołówkiem o biurko i poszedł grać w piłkę.
Załóżmy, że od dłuższego czasu staram się bezskutecznie rozwiązać zadanie z pięcioma liczbami. Niestety, bez powodzenia, więc jestem bardzo bliski połamania ołówka i pójścia na rower. Proszę o wsparcie, czyli albo o znalezienie rozwiązania, albo o w miarę zwięzłe uzasadnienie, że takowe nie istnieje.
Komentarze
Wszystkie liczby naturalne niepodzielne przez 3 możemy podzielić na dwa podzbiory. Podzbiór zawierający liczby, które przy dzieleniu przez 3 dają resztę 1 oraz podzbiór dla liczb z resztą równą 2.
Dla sumy dwóch liczb mamy 2 przypadki:
Przypadek pierwszy, gdy obie dodawane liczby należą do różnych podzbiorów. Wówczas suma jest zawsze podzielna przez 3.
Przypadek drugi, gdy obie dodawane liczby należą do tego samego podzbioru. Wówczas suma nigdy nie będzie podzielna przez 3. Wtedy musimy ratować się podzielnością przez 7.
Wśród pięciu liczb zawsze znajdą się co najmniej 3 należące do tego samego podzbioru.
Skupmy się na takiej trójce liczb.
Każda z nich przy dzieleniu przez 7 daje resztę równą od 1 do 6. Reszta równa 0 jest niedopuszczalna. Aby suma dwóch takich liczb była podzielna przez 7, to liczby te muszą dawać reszty: 1 i 6, albo 2 i 5, albo 3 i 4.
A z tego prosty wniosek, że dla dowolnej trójki liczb niepodzielnych przez 7 zawsze istnieje taka para których suma również nie dzieli się przez 7.
Pazdrawiam
Pierwszą rzeczą, którą trzeba zauważyć jest fakt, iż w powyższym grafie nie istnieje trójkąt, w którym na każdym z boków suma liczb jest podzielna przez 3 oraz nie istnieje trójkąt, w którym na każdym z boków suma liczb jest podzielna przez 7.
Można to najszybciej udowodnić patrząc na reszty z dzielenia przez 3 (analogicznie przez 7). Jeśli w wierzchołku A jest liczba, która daje resztę 1 przy dzieleniu przez 3, to w wierzchołkach B i C muszą być liczby, które dają resztę 2 przy dzieleniu przez 3. To daje sprzeczność, bo suma liczb przy boku BC nie jest podzielna przez 3.
Rozważmy teraz zadanie równoważne, ale łatwiejsze (chyba) do zrozumienia. Nazwijmy wierzchołki grafu kolejno: DEBAC. Musimy pomalować krawędzie naszego grafu dwoma kolorami: zielonym i niebieskim tak, aby nie powstały jednokolorowe trójkąty. W trójkącie ABC dwa boki muszą być jednego koloru (np. zielonego), a trzeci koloru innego.
Nie więc AB i AC będą zielone, a BC niebieski.
Dalej, gdyby bok AD był zielony, to BD jest niebieski (trójkąt ABD) i CD jest niebieski (trójkąt ACD). Ale wtedy trójkąt BCD jest cały niebieski, więc bok AD nie może być zielony.
Dlatego AD jest niebieski. Analogicznie można uzasadnić, że bok AE też jest niebieski. Zatem (z trójkąta ADE) bok DE jest zielony.
Zostały nam cztery boki do pomalowania.
Rozważmy dwa przypadki:
1. Jeśli CD jest zielony, to CE jest niebieski (trójkąt CDE), dalej BE jest zielony (trójkąt BCE) i dalej BD jest niebieski (trójkąt BDE)
2. Jeśli CD jest niebieski, to BD jest zielony (trójkąt BCD), dalej BE jest niebieski (trójkąt BDE) i CE jest zielony (trójkąt BCE)
W pierwszym przypadku boki narysowanego na grafie pięciokąta są zielone, a przekątne niebieskie. W drugim przypadku, jeśli zamienimy miejscami wierzchołki D i E (w grafie możemy to zrobić) to otrzymamy przypadek pierwszy.
Przenieśmy zatem przypadek pierwszy do naszego zadania.
Zielone krawędzie oznaczają krawędzie, na których suma cyfr jest podzielna przez 3, a niebieskie – krawędzie, na których suma cyfr jest podzielna przez 7. (możemy przyjąć też, że zielone oznaczają sumę podzielną przez 7, a niebieskie – podzielną przez 3, ale dalsze rozwiązanie będzie wtedy analogiczne).
Na jednym z wierzchołków (np. A) liczba przy dzieleniu przez 3 daje resztę 1. Wtedy na wierzchołku B reszta z dzielenia przez 3 wynosi 2, na wierzchołku E – 1, na wierzchołku D – 2, a na wierzchołku C -1. Ale suma liczb na boku AC nie jest podzielna przez 3 – sprzeczność.
Zatem w powyższy graf nie da się wpisać pięciu liczb tak, aby warunki zadania były spełnione.
Przy 4 liczbach mamy dwa dwuelementowe podzbiory:
A: liczby postaci 3n+1 (w przykładzie 4 i 10)
B: liczby postaci 3n+2 (w przykładzie 2 i 5)
Suma liczby z podzbioru A i lczby z podzbioru B jest podzielna przez 3.
Suma dwóch liczb z podzbioru A podzielna przez 3 nie jest, ale mozna te liczby dobrać tak, by ich suma była podziela przez 7 (konkretnie suma reszt z dzielenia tych liczb przez 7 musi być równa 7). Podobnie trzeba zrobić dla zbioru B.
Jeżeli mamy 5 liczb, to jeden ze zbiorów, powiedzmy A, musi mieć 3 elementy. I ponieważ 7 jest liczba nieparzystą, nie da się wybrać takiej trójki liczb, żeby każda para miała sumę reszt równą 7.