This website uses cookies to ensure you get the best experience on the website.
010101011101110010
100110001000
100100
101110000011100011
011100001011
011001
 ¤ קונטקט ¤ 
 ¤ אפשרויות ¤ 
 ¤ עדכון ¤ 
 ¤ Stop potratům ¤ 
Rychlá řešení dlouho bolí
Čekáte-li nečekané dítě
 ¤ HEX מונה ¤ 
2 e 5 e 3
 ¤ תעודה ¤ 
Valid HTML 4.01 Valid CSS Valid RSS 2.0

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

Ukradený náhrdelník - difficulty 3.8 (former difficulty 3)
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ů.
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á.
Difficulty:12345678910
 ¤ עשירייה ¤ 
 ¤ חיפוש ¤ 
 ¤ Biblenet ¤ 
פסוק:
חזרה למעלה
Copyright © 2004-2019 Tomáš Vala
אופטימלי עבור Firefox
מפת האתר | גירסה ניידת | A+ A A-