Return to search

Klasické kombinatorické úlohy / Classic problems in combinatorics

This work is concerned with five problems in combinatorics. In Josephus problem, people are standing in a circle or in a row and every q-th is executed until only one person remains. We show how to find the survivor, and discuss the generalization when each person has more lives. In Tower of Hanoi, we study the numbers and properties of moves necessary to transport the tower from one rod to another, where the total number of rods is either three or four. We mention related problems with restrictions on the legal moves. In ménage problem, we calculate the number of seatings of couples around a table such that men and women alternate and nobody sits next to his or her partner. We also discuss permutations with restricted positions and rook polynomials. In ballot problem, we consider two candidates competing against each other and calculate the probability that, throughout the count, the first candidate always had more votes than k times the number of votes of the second one; we also mention the relation to Catalan numbers. In Kirkman's schoolgirl problem, the task is to find a weekly schedule for fifteen girls walking daily out in triads so that no two go together more than once. We also discuss the social golfer problem and Schurig's tables.

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:304068
Date January 2012
CreatorsStodolová, Kristýna
ContributorsSlavík, Antonín, Calda, Emil
Source SetsCzech ETDs
LanguageCzech
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0019 seconds