MathDB

3

Part of 2012 BAMO

Problems(2)

2012 BAMO C/2 Two infinite rows of evenly-spaced dots, at most 2012 dots in

Source:

8/26/2019
Two infinite rows of evenly-spaced dots are aligned as in the figure below. Arrows point from every dot in the top row to some dot in the lower row in such a way that: [*]No two arrows point at the same dot. [*]Now arrow can extend right or left by more than 1006 positions. https://cdn.artofproblemsolving.com/attachments/7/6/47abf37771176fce21bce057edf0429d0181fb.png Show that at most 2012 dots in the lower row could have no arrow pointing to them.
combinatorics
2012 BAMO12 3 permutations of a sequence, scramble, two-two

Source:

8/26/2019
Let x1,x2,...,xkx_1,x_2,...,x_k be a sequence of integers. A rearrangement of this sequence (the numbers in the sequence listed in some other order) is called a scramble if no number in the new sequence is equal to the number originally in its location. For example, if the original sequence is 1,3,3,51,3,3,5 then 3,5,1,33,5,1,3 is a scramble, but 3,3,1,53,3,1,5 is not.
A rearrangement is called a two-two if exactly two of the numbers in the new sequence are each exactly two more than the numbers that originally occupied those locations. For example, 3,5,1,33,5,1,3 is a two-two of the sequence 1,3,3,51,3,3,5 (the first two values 33 and 55 of the new sequence are exactly two more than their original values 11 and 33).
Let n≥2n\geq 2. Prove that the number of scrambles of 1,1,2,3,...,n−1,n1,1,2,3,...,n-1,n is equal to the number of two-twos of 1,2,3,...,n,n+11,2,3,...,n,n+1.
(Notice that both sequences have n+1n+1 numbers, but the first one contains two 1s.)
combinatoricsInteger sequencepermutation