חידות לוגיות

Dva lupiči společně ukradli vzácný náhrdelník složený z diamantů a rubínů. Oba druhy kamenů byly na náhrdelníku zastoupeny stejně a každého druhu byl sudý počet. Kameny byly na řetízku rozložený rovnoměrně za sebou, ale ne nutně střídavě (tedy klidně 2 diamanty, 1 rubín, 3 diamanty, ...).
Když zloději přisli domů, uvažovali, jak náhrdelník spravedlivě rozdělit na dvě části, aby každý z nich zároveň dostal stejný počet diamantů i rubínů.
Dokažte, že takové rozdělení vždy existuje pro libovolné rozložení kamenů.

Show/hide solution:

Náhrdelník budeme dělit na dva stejně dlouhé úseky (tzn. dvě místa řezu) o délce poloviny z celkového počtu kamenů. Zvolme libovolně počáteční rozdělní náhrdelníku. Spočítáme hodnotu D - R, kde D je počet diamantů a R počet rubínů ve zvoleném úseku. Jestliže je výsledná hodnota 0 máme vyhráno. Jinak je hodnota nenulová. Bez újmy na obecnosti předpokládejme, že je kladná. Potom D - R pro druhý díl (označme si jako koncové rozdělení) náhrdelníku je záporná hodnota. Zvolený úsek postupně posouváme o jeden kámen doprava (napravo nám jeden kámen přibude a nalevo zmizí) dokud nanalezneme úsek, kde D - R je 0. Takový úsek musí existovat, protože v každém kroce se hodntoa D - R zvýší nebo sníží o 1 nebo zůstane stejná. Mezi počátečním a koncovým rozdělením tedy musí existovat bod, kdy hodnota D - R je nulová, protože pro počáteční rozdělení je kladná a pro koncové záporná.

» גלריה » חידות לוגיות 100011101000010101