Dowód na naturalną wartość wszystkich wyników przekształceń

MariuszJ · Post autor: **MariuszJ** » 4 maja 2018, o 18:59

Znany problem. Mamy dwa naczynia, każde ma pojemność wyrażoną liczbą naturalną. Możemy przelewać z jednego do drugiego całość zawartości pierwszego lub tyle ile się zmieści w drugim. Możemy opróżniać naczynie do pustego wylewając wodę na ziemię i możemy dolewać wodę z kranu do naczynia pustego lub częściowo napełnionego.

Udowodnić że w każdym momencie tych czynności zawartość obu naczyń będzie wyrażona liczbą naturalną lub zero. To chyba dowód przez indukcję?

Janusz Tracz · Post autor: **Janusz Tracz** » 4 maja 2018, o 19:46

indukcja nie jest konieczna. Obejrzyj bardzo przyjemny film o

Kod: Zaznacz cały

https://www.youtube.com/watch?v=0Oef3MHYEC0

. Dla zbiorników o objętości \(\displaystyle{ n,k\in\NN}\) poruszasz się w takim grafie o rozmiarach \(\displaystyle{ n \times k}\) trafiając jedynie w naturalne wierzchołki które odpowiadają wartością napełnienia zbiorników.

MariuszJ · Post autor: **MariuszJ** » 4 maja 2018, o 19:59

Wydaje mi się że rysowanie olbrzymiego grafu nie jest potrzebne i powinno dać się wykazać matematycznie że jeśli naczynia mają objętość naturalną i na początku większe jest całkowicie napełnione, to rozpatrując kilka możliwości przelewów, zgodnie z warunkami zadania, zawsze po przelewie zachowamy wartość naturalną, bo jeśli wcześniej ona była naturalna i zawsze możemy dolać tylko wartość naturalną to nowa wartość dalej jest naturalna. To jest jakiś bardzo prosty dowód. Potrzebny mi jest opis słowny dowodu do mojego blogu informatycznego.

Janusz Tracz · Post autor: **Janusz Tracz** » 4 maja 2018, o 20:03

To co podałem jest dowodem własnie słownym a do tego zgrabnym. Żadnego olbrzymiego grafu nikt nie rysuje przecież.

a4karo · Post autor: **a4karo** » 4 maja 2018, o 20:08

Janusz Tracz pisze:To co podałem jest dowodem własnie słownym a do tego zgrabnym. Żadnego olbrzymiego grafu nikt nie rysuje przecież.

To jest argument: słowny, zgrabny, zrozumiały, ale nie dowód.

Dowód (banalny) chyba najłatwiej jest zrobić indukcja po ilości przelewań.

Janusz Tracz · Post autor: **Janusz Tracz** » 4 maja 2018, o 20:18

No bobra racja... ale argument ten na pewno jest warty uwagi.

MariuszJ · Post autor: **MariuszJ** » 4 maja 2018, o 20:56

Czy ktoś mi może podać ten dowód przez indukcję? Słaby jestem z matematyki. Program będzie wykorzystywał algorytm na przeszukiwanie grafu, ale muszę na początku wykazać że mogę użyć tablicy indeksowanej liczbami naturalnymi dla wierzchołków grafu.

To jest chyba za prosty problem że nikomu się nie chce nim zająć.

Matematyka.pl