MathDB

4

Part of 2021 Tuymaada Olympiad

Problems(2)

Knights and Liars again

Source: Tuymaada 2021/J4

7/30/2021
Some manors of Lipshire county are connected by roads. The inhabitants of manors connected by a road are called neighbours. Is it always possible to settle in each manor a knight (who always tells truth) or a liar (who always lies) so that every inhabitant can say ”The number of liars among my neighbours is at least twice the number of knights”?
combinatorics
Counting monotonous paths in $n\times n$ square

Source: Tuymaada 2021 Senior P4

7/28/2021
An n×nn\times n square (nn is a positive integer) consists of n2n^2 unit squares.A \emph{monotonous path} in this square is a path of length 2n2n beginning in the left lower corner of the square,ending in its right upper corner and going along the sides of unit squares. For each kk, 0≤k≤2n−10\leq k\leq 2n-1, let SkS_k be the set of all the monotonous paths such that the number of unit squares lying below the path leaves remainder kk upon division by 2n−12n-1.Prove that all SkS_k contain equal number of elements.
counting problemcombinatorics