Zobrazení zdroje stránky 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í čokolády|Ř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?<ref>http://mks.mff.cuni.cz/common/show.php?title=Poh%26aacute%3Bdky&file=archive/26/1&lang=0</ref> [[/Řešení mravenců|Ř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í přímek|Ř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 <math>2^n\times 2^n</math> dlaždicemi tvaru L o třech polích, když z šachovnice vysekneme právě jeden, libovolný vrchol? [[/Řešení šachovnice|Ř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í známostí|Řešení]]

== Prameny ==
<references />