MathDB

4

Part of 2006 Moldova Team Selection Test

Problems(3)

Counting numbers on circle

Source: Moldavian TST_1

3/6/2006
Let mm circles intersect in points AA and BB. We write numbers using the following algorithm: we write 11 in points AA and BB, in every midpoint of the open arc ABAB we write 22, then between every two numbers written in the midpoint we write their sum and so on repeating nn times. Let r(n,m)r(n,m) be the number of appearances of the number nn writing all of them on our mm circles. a) Determine r(n,m)r(n,m); b) For n=2006n=2006, find the smallest mm for which r(n,m)r(n,m) is a perfect square. Example for half arc: 1−11-1; 1−2−11-2-1; 1−3−2−3−11-3-2-3-1; 1−4−3−5−2−5−3−4−11-4-3-5-2-5-3-4-1; 1−5−4−7−3−8−5−7−2−7−5−8−3−7−4−5−11-5-4-7-3-8-5-7-2-7-5-8-3-7-4-5-1...
algorithminductioncombinatorics proposedcombinatorics
Number of distinct solutions of x,y,z=a

Source: Moldova TST 2006 Test II problem 4

3/25/2006
Let A={1,2,…,n}A=\{1,2,\ldots,n\}. Find the number of unordered triples (X,Y,Z)(X,Y,Z) that satisfy X⋃Y⋃Z=AX\bigcup Y \bigcup Z=A
combinatorics proposedcombinatorics
Modlova 3rd tst, problem 4

Source: Moldova TST III

3/26/2006
Let f(n)f(n) denote the number of permutations (a1,a2,…,an)(a_{1}, a_{2}, \ldots ,a_{n}) of the set {1,2,…,n}\{1,2,\ldots,n\}, which satisfy the conditions: a1=1a_{1}=1 and ∣ai−ai+1∣≤2|a_{i}-a_{i+1}|\leq2, for any i=1,2,…,n−1i=1,2,\ldots,n-1. Prove that f(2006)f(2006) is divisible by 3.
combinatorics proposedcombinatorics