MB104, příklady k domácímu rozjímání jarní semestr 2015, desátý týden
Příklad 1. Kolika způsoby se může bílý střelec dostat z některého bílého políčka v horní řadě šachovnice 8 x 8 na některé bílé políčko dolní řady, má-li povoleny pouze tahy o jedno pole směrem „ dolů "?
Řešení. Rekurzí přes počet způsobů, na která se lze dostat na nějaké konkrétní políčko šachovnice. Jedeme od shora dolů (v horní řadě máme samé jedničky, počty způsobů pro políčka v následující řadě jsou součtem způsobů pro políčka přímo „nad" uvažovaným. Celkem 296. □
Příklad 2. Myš žere kostku sýra 3x3x3 složenou z kostiček 1 x 1 x 1 a to tak, že si vybere nějakou kostičku 1 x 1 x 1 na povrchu, tu sežere a posune se na kostičku sousedící s právě sežranou přes stěnu. Tuto sežere a jde dál. Může jako poslední sežrat středovou kostičku (gravitaci neuvažujeme, kostičky zůstávají na místě i v prožrané kostce)
Řešení. Obarvíme kostku „šachovnicově" na bílá a černá pole. Nechť rohové kostičky jsou bílé. Pak bílých kostiček je 14, černých 13. Středová kostička je černá. Myš při své cestě žere střídavě bílé a černé kostičky. Máli tedy sežrat všechny, musí začít i končit bílou. □
1