MathDB

4

Part of 2014 Middle European Mathematical Olympiad

Problems(2)

bibinomial coefficient, double factorial

Source: Middle European Mathematical Olympiad I-4

9/20/2014
For integers n≥k≥0n \ge k \ge 0 we define the bibinomial coefficient ((nk))\left( \binom{n}{k} \right) by ((nk))=n!!k!!(n−k)!!. \left( \binom{n}{k} \right) = \frac{n!!}{k!!(n-k)!!} . Determine all pairs (n,k)(n,k) of integers with n≥k≥0n \ge k \ge 0 such that the corresponding bibinomial coefficient is an integer.
Remark: The double factorial n!!n!! is defined to be the product of all even positive integers up to nn if nn is even and the product of all odd positive integers up to nn if nn is odd. So e.g. 0!!=10!! = 1, 4!!=2⋅4=84!! = 2 \cdot 4 = 8, and 7!!=1⋅3⋅5⋅7=1057!! = 1 \cdot 3 \cdot 5 \cdot 7 = 105.
factorialalgorithmnumber theoryrelatively primenumber theory proposed
Happy City

Source: Middle European Mathematical Olympiad T-4

9/21/2014
In Happy City there are 20142014 citizens called A1,A2,…,A2014A_1, A_2, \dots , A_{2014}. Each of them is either happy or unhappy at any moment in time. The mood of any citizen AA changes (from being unhappy to being happy or vice versa) if and only if some other happy citizen smiles at AA. On Monday morning there were NN happy citizens in the city.
The following happened on Monday during the day: the citizen A1A_1 smiled at citizen A2A_2, then A2A_2 smiled at A3A_3, etc., and, finally, A2013A_{2013} smiled at A2014A_{2014}. Nobody smiled at anyone else apart from this. Exactly the same repeated on Tuesday, Wednesday and Thursday. There were exactly 20002000 happy citizens on Thursday evening.
Determine the largest possible value of NN.
invariantinductionmodular arithmeticbinomial coefficientscombinatorics proposedcombinatorics