Cvičení z diskrétní matematiky/Úvodní příklady
Mějme čokoládu velkou m×n dílků. Zlomením rozumíme její rozdělení po přímce mezi dílky buď po délce, nebo po šířce. Budeme ji lámat, dokud nám nezbyde mn kusů 1×1. Jaká pro rozdílné způsoby lámání je dolní a horní mez na počet lámání? Řešení
Po drátě dlouhém 1 metr se prochází dané množství mravenců, každý rychlostí 0,1 m/s. Když se dva mravenci srazí, každý z nich se otočí a pokračuje opačným směrem, než v jakém mířil předtím. Když mravenec dorazí na konec drátu, spadne. Známe-li počáteční polohy všech mravenců, jak zjistíme, za jak dlouho všichni popadají z drátu?[1] Řešení
Máme nekonečnou euklidovskou rovinu a na ní n přímek v obecné poloze. Obecná poloha znamená, že žádné dvě přímky nejsou rovnoběžné a žádné tři se nestýkají v jednom bodě. Na kolik oblastí rozdělily přímky rovinu? Je možné obarvit tyto oblasti dvěma barvami tak, aby měly oblasti, které sousedí úsečkou, nebo polopřímkou, různé barvy? Řešení
Kdy lze vydláždit šachovnici m×n dominy 2×1 (které lze otáčet)? Kdy je to možné, odsekneme-li za šachovnice před dlážděním dva protilehlé rohy? Je možné vydláždit šachovnici dlaždicemi tvaru L o třech polích, když z šachovnice vysekneme právě jeden, libovolný vrchol? Řešení
Máme šest lidí, z nichž se některé dvojice znají a některé neznají. Ptáme se po důkazu následujícího tvrzení: vždy je buď možné najít trojici lidí, kteří se po dvou znají, nebo trojici lidí, kteří se po dvou neznají. Může se stát, že se každý ze sedmi lidí zná s právě třemi dalšími? Řešení