Dowód z kolorowaniem płaszczyzny i dowód określonej sumy :-)

[Arturooo]

Czołem!
Mam problem z zadaniami o następującej treści:
Zad 1.

Udowodnij, że obszary wyznaczone przez dowolną ilość prostych mogą zostać pokolorowane na dwa kolory tak, że żadne dwa obszary o wspólnym boku nie będą miały tego samego koloru.

Mam tutaj problem już z wyznaczeniem założenia indukcyjnego.

Zad 2.

Firma kateringowa pakuje kanapki wyłącznie w pudełka po 3 lub
5 sztuk. Udowodnij, że każdą liczącą co najmniej 8 sztuk liczbę kanapek da się
zapakować w takie pudełka tak, aby wszystkie pudełka były pełne

Tutaj moim pomysłem na założenie indukcyjne jest że \(\displaystyle{ n = 3k + 5j}\) dla k i j będącymi liczbami naturalnymi, jednak nie mam pojęcia, czy jest to prawidłowy tok rozumowania.
Próbowałem udowodnić to na zasadzie
\(\displaystyle{ n = 3k + 5j}\)
\(\displaystyle{ n+1 = 3(k+2) + 5(j-1)}\)
Jednak przy takim podejściu do tematu j może dojść do zera i dalsze odejmowanie nie miałoby sensu. Oczywiście wiem, że następnym krokiem byłoby, że dla n+2 mamy
\(\displaystyle{ n+2 = 3(k-1) + 5(j+1)}\)
ale nie wiem jak zapisać to tak, by był to dobrze wykonany dowód przez indukcję.

[Marcinek665]

Takie spostrzeżenie:

\(\displaystyle{ 3n=3(n-5)+5 \cdot 3}\)

\(\displaystyle{ 3n+1=3(n-3) + 5 \cdot 2}\)

\(\displaystyle{ 3n+2=3(n-1)+5 \cdot 1}\)

Pozostanie parę małych przypadków do rozważenia, co łatwo zrobić na palcach.

W pierwszym rozważ jedną prostą. Podzieli ona płaszczyznę na dwa obszary. Jeden pomalujesz na biało, drugi na czarno. To jest twoje założenie. Dalej jakoś kombinować z możliwościami przecięcia.

[baklazan9494]

Mógłby ktoś podpowiedzieć jak zabrać się za to drugie? Wskazówka powyżej nic mi nie mówi.

[Jan Kraszewski]

Ta wskazówka powyżej to w zasadzie całe rozwiązanie. W dodatku wskazówka \(\displaystyle{ 3n=3(n-5)+5 \cdot 3}\) jest w zasadzie zbędna, bo nie ma wymagania, by używać obu rodzajów pudełek.

Każda liczba jest postaci \(\displaystyle{ 3n}\) lub \(\displaystyle{ 3n+1}\) lub \(\displaystyle{ 3n+2}\). Zatem powyższe spostrzeżenie pokazuje jak zapakować dowolną dającą resztę \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ 3}\) liczbę kanapek \(\displaystyle{ \ge 10}\) oraz dowolną dającą resztę \(\displaystyle{ 2}\) z dzielenia przez \(\displaystyle{ 3}\) liczbę kanapek \(\displaystyle{ \ge 8}\). Zapakowanie dowolnej podzielnej przez \(\displaystyle{ 3}\) liczby kanapek jest oczywiste, bo używasz tylko pudełek trzykanapkowych.

JK

[baklazan9494]

Rzeczywiście, wiem już o co chodzi. Ale gdzie tu jakaś indukcja?

[Jan Kraszewski]

Nie ma.

JK