Putnam Archive — Combinatorics

Alice and Bob play a game with a string of $n$ digits, each of which is restricted to be $0$, $1$, or $2$. Initially all the digits are $0$. A legal move is to add or subtract $1$ from one digit to create a new string that has not appeared before. A player with no legal move loses, and the other player wins. Alice goes first, and the players alternate moves. For each $n \geq 1$, determine which player has a strategy that guarantees winning.

Find the minimal value of $k$ such that there exist $k$-by-$k$ real matrices $A_1, \dots, A_{2025}$ with the property that $A_i A_j = A_j A_i$ if and only if $|i-j| \in \{0,1,2024\}$.

Let $n$ be an integer with $n \geq 2$. For a sequence $s = (s_1,\dots,s_{n-1})$ where each $s_i = \pm 1$, let $f(s)$ be the number of permutations $(a_1,\dots,a_n)$ of $\{1,2,\dots,n\}$ such that $s_i(a_{i+1}-a_i) > 0$ for all $i$. For each $n$, determine the sequences $s$ for which $f(s)$ is maximal.

Suppose that each point in the plane is colored either red or green, subject to the following condition: For every three noncollinear points $A,B,C$ of the same color, the center of the circle passing through $A,B$ and $C$ is also this color. Prove that all points of the plane are the same color.

For $n \geq 2$, let $A = [a_{i,j}]_{i,j=1}^n$ be an $n$-by-$n$ matrix of nonnegative integers such that

1. (a)
   $a_{i,j} = 0$ when $i+j\leq n$;
2. (b)
   $a_{i+1,j} \in \{a_{i,j}, a_{i,j}+1\}$ when $1 \leq i \leq n-1$ and $1 \leq j \leq n$; and
3. (c)
   $a_{i,j+1} \in \{a_{i,j}, a_{i,j}+1\}$ when $1 \leq i \leq n$ and $1 \leq j \leq n-1$.

Let $S$ be the sum of the entries of $A$, and let $N$ be the number of nonzero entries of $A$. Prove that $$S \leq \frac{(n+2)N}{3}.$$

Let $\mathbb{N} = \{1,2,3,\dots\}$. Find the largest real constant $r$ such that there exists a function $g\colon \mathbb{N} \to \mathbb{N}$ such that $$g(n+1)-g(n) \geq (g(g(n)))^r$$ for all $n \in \mathbb{N}$.

Let $S$ be the set of bijections $$T \colon \{1,2,3\} \times \{1,2,\dots,2024\} \to \{1,2,\dots,6072\}$$ such that $T(1,j) < T(2,j) < T(3,j)$ for all $j \in \{1,2,\dots,2024\}$ and $T(i,j) < T(i,j+1)$ for all $i \in \{1,2,3\}$ and $j \in \{1,2,\dots,2023\}$. Do there exist $a$ and $c$ in $\{1,2,3\}$ and $b$ and $d$ in $\{1,2,\dots,2024\}$ such that the fraction of elements $T$ in $S$ for which $T(a,b) < T(c,d)$ is at least $1/3$ and at most $2/3$?

Let $n$ and $k$ be positive integers. The square in the $i$th row and $j$th column of an $n$-by-$n$ grid contains the number $i+j-k$. For which $n$ and $k$ is it possible to select $n$ squares from the grid, no two in the same row or column, such that the numbers contained in the selected squares are exactly $1,2,\dots,n$?

Two convex quadrilaterals are called partners if they have three vertices in common and they can be labeled $ABCD$ and $ABCE$ so that $E$ is the reflection of $D$ across the perpendicular bisector of the diagonal $\overline{AC}$. Is there an infinite sequence of convex quadrilaterals such that each quadrilateral is a partner of its successor and no two elements of the sequence are congruent? [A diagram has been omitted.]

Let $k$ and $m$ be positive integers. For a positive integer $n$, let $f(n)$ be the number of integer sequences $x_1,\dots,x_k,y_1,\dots,y_m,z$ satisfying $1 \leq x_1 \leq \cdots \leq x_k \leq z \leq n$ and $1 \leq y_1 \leq \cdots \leq y_m \leq z \leq n$. Show that $f(n)$ can be expressed as a polynomial in $n$ with nonnegative coefficients.

Alice and Bob play a game in which they take turns choosing integers from $1$ to $n$. Before any integers are chosen, Bob selects a goal of “odd” or “even”. On the first turn, Alice chooses one of the $n$ integers. On the second turn, Bob chooses one of the remaining integers. They continue alternately choosing one of the integers that has not yet been chosen, until the $n$th turn, which is forced and ends the game. Bob wins if the parity of $\{k\colon \mbox{the number $k$ was chosen on the $k$th turn}\}$ matches his goal. For which values of $n$ does Bob have a winning strategy?

Consider an $m$-by-$n$ grid of unit squares, indexed by $(i,j)$ with $1 \leq i \leq m$ and $1 \leq j \leq n$. There are $(m-1)(n-1)$ coins, which are initially placed in the squares $(i,j)$ with $1 \leq i \leq m-1$ and $1 \leq j \leq n-1$. If a coin occupies the square $(i,j)$ with $i \leq m-1$ and $j \leq n-1$ and the squares $(i+1,j), (i,j+1)$, and $(i+1,j+1)$ are unoccupied, then a legal move is to slide the coin from $(i,j)$ to $(i+1,j+1)$. How many distinct configurations of coins can be reached starting from the initial configuration by a (possibly empty) sequence of legal moves?

A sequence $y_1,y_2,\dots,y_k$ of real numbers is called zigzag if $k=1$, or if $y_2-y_1, y_3-y_2, \dots, y_k-y_{k-1}$ are nonzero and alternate in sign. Let $X_1,X_2,\dots,X_n$ be chosen independently from the uniform distribution on $[0,1]$. Let $a(X_1,X_2,\dots,X_n)$ be the largest value of $k$ for which there exists an increasing sequence of integers $i_1,i_2,\dots,i_k$ such that $X_{i_1},X_{i_2},\dots,X_{i_k}$ is zigzag. Find the expected value of $a(X_1,X_2,\dots,X_n)$ for $n \geq 2$.

Let $n$ be an integer with $n \geq 2$. Over all real polynomials $p(x)$ of degree $n$, what is the largest possible number of negative coefficients of $p(x)^2$?

Alice and Bob play a game on a board consisting of one row of 2022 consecutive squares. They take turns placing tiles that cover two adjacent squares, with Alice going first. By rule, a tile must not cover a square that is already covered by another tile. The game ends when no tile can be placed according to this rule. Alice's goal is to maximize the number of uncovered squares when the game ends; Bob's goal is to minimize it. What is the greatest number of uncovered squares that Alice can ensure at the end of the game, no matter how Bob plays?

Let $n$ be a positive integer. Determine, in terms of $n$, the largest integer $m$ with the following property: There exist real numbers $x_1,\dots,x_{2n}$ with $-1 < x_1 < x_2 < \cdots < x_{2n} < 1$ such that the sum of the lengths of the $n$ intervals $$[x_1^{2k-1}, x_2^{2k-1}], [x_3^{2k-1},x_4^{2k-1}], \dots, [x_{2n-1}^{2k-1}, x_{2n}^{2k-1}]$$ is equal to 1 for all integers $k$ with $1 \leq k \leq m$.

Let $\times$ represent the cross product in $\mathbb{R}^3$. For what positive integers $n$ does there exist a set $S \subset \mathbb{R}^3$ with exactly $n$ elements such that $$S = \{v \times w: v, w \in S\}?$$

Assign to each positive real number a color, either red or blue. Let $D$ be the set of all distances $d > 0$ such that there are two points of the same color at distance $d$ apart. Recolor the positive reals so that the numbers in $D$ are red and the numbers not in $D$ are blue. If we iterate this recoloring process, will we always end up with all the numbers red after a finite number of steps?

Find all integers $n$ with $n \geq 4$ for which there exists a sequence of distinct real numbers $x_1,\dots,x_n$ such that each of the sets

forms a 3-term arithmetic progression when arranged in increasing order.

How many positive integers $N$ satisfy all of the following three conditions?

1. (i)
   $N$ is divisible by 2020.
2. (ii)
   $N$ has at most 2020 decimal digits.
3. (iii)
   The decimal digits of $N$ are a string of consecutive ones followed by a string of consecutive zeros.

Let $k$ be a nonnegative integer. Evaluate $$\sum_{j=0}^k 2^{k-j} \binom{k+j}{j}.$$

Let $a_n$ be the number of sets $S$ of positive integers for which $$\sum_{k \in S} F_k = n,$$ where the Fibonacci sequence $(F_k)_{k \geq 1}$ satisfies $F_{k+2} = F_{k+1} + F_k$ and begins $F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3$. Find the largest integer $n$ such that $a_n = 2020$.

Let $k$ and $n$ be integers with $1 \leq k < n$. Alice and Bob play a game with $k$ pegs in a line of $n$ holes. At the beginning of the game, the pegs occupy the $k$ leftmost holes. A legal move consists of moving a single peg to any vacant hole that is further to the right. The players alternate moves, with Alice playing first. The game ends when the pegs are in the $k$ rightmost holes, so whoever is next to play cannot move and therefore loses. For what values of $n$ and $k$ does Alice have a winning strategy?

Let $n$ be a positive integer, and let $V_n$ be the set of integer $(2n+1)$-tuples $\mathbf{v} = (s_0, s_1, \cdots, s_{2n-1}, s_{2n})$ for which $s_0 = s_{2n} = 0$ and $|s_j - s_{j-1}| = 1$ for $j=1,2,\cdots,2n$. Define $$q(\mathbf{v}) = 1 + \sum_{j=1}^{2n-1} 3^{s_j},$$ and let $M(n)$ be the average of $\frac{1}{q(\mathbf{v})}$ over all $\mathbf{v} \in V_n$. Evaluate $M(2020)$.

Denote by $\mathbb{Z}^2$ the set of all points $(x,y)$ in the plane with integer coordinates. For each integer $n \geq 0$, let $P_n$ be the subset of $\mathbb{Z}^2$ consisting of the point $(0,0)$ together with all points $(x,y)$ such that $x^2 + y^2 = 2^k$ for some integer $k \leq n$. Determine, as a function of $n$, the number of four-point subsets of $P_n$ whose elements are the vertices of a square.

Let $F_m$ be the $m$th Fibonacci number, defined by $F_1 = F_2 = 1$ and $F_m = F_{m-1} + F_{m-2}$ for all $m \geq 3$. Let $p(x)$ be the polynomial of degree $1008$ such that $p(2n+1) = F_{2n+1}$ for $n=0,1,2,\dots,1008$. Find integers $j$ and $k$ such that $p(2019) = F_j - F_k$.

Let $\mathbb{Z}^n$ be the integer lattice in $\mathbb{R}^n$. Two points in $\mathbb{Z}^n$ are called neighbors if they differ by exactly $1$ in one coordinate and are equal in all other coordinates. For which integers $n \geq 1$ does there exist a set of points $S \subset \mathbb{Z}^n$ satisfying the following two conditions?

1. (1)
   If $p$ is in $S$, then none of the neighbors of $p$ is in $S$.
2. (2)
   If $p \in \mathbb{Z}^n$ is not in $S$, then exactly one of the neighbors of $p$ is in $S$.

Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some order, and let $M$ be the $(2^n-1) \times (2^n-1)$ matrix whose $(i,j)$ entry is $$m_{ij} = \begin{cases} 0 & \mbox{if }S_i \cap S_j = \emptyset; \\ 1 & \mbox{otherwise.} \end{cases}$$ Calculate the determinant of $M$.

Let $\mathcal{P}$ be the set of vectors defined by $$\mathcal{P} = \left\{ \left. \begin{pmatrix} a \\ b \end{pmatrix} \right| 0 \leq a \leq 2, 0 \leq b \leq 100, \mbox{ and } a,b \in \mathbb{Z} \right\}.$$ Find all $\mathbf{v} \in \mathcal{P}$ such that the set $\mathcal{P} \setminus \{ \mathbf{v} \}$ obtained by omitting vector $\mathbf{v}$ from $\mathcal{P}$ can be partitioned into two sets of equal size and equal sum.

Let $S$ be the set of sequences of length $2018$ whose terms are in the set $\{1,2,3,4,5,6,10\}$ and sum to $3860$. Prove that the cardinality of $S$ is at most $$2^{3860} \cdot \left( \frac{2018}{2048} \right)^{2018}.$$

A class with $2N$ students took a quiz, on which the possible scores were $0,1,\dots,10$. Each of these scores occurred at least once, and the average score was exactly $7.4$. Show that the class can be divided into two groups of $N$ students in such a way that the average score for each group was exactly $7.4$.

Each of the integers from $1$ to $n$ is written on a separate card, and then the cards are combined into a deck and shuffled. Three players, $A$, $B$, and $C$, take turns in the order $A,B,C,A,\dots$ choosing one card at random from the deck. (Each card in the deck is equally likely to be chosen.) After a card is chosen, that card and all higher-numbered cards are removed from the deck, and the remaining cards are reshuffled before the next turn. Play continues until one of the three players wins the game by drawing the card numbered $1$.

Show that for each of the three players, there are arbitrarily large values of $n$ for which that player has the highest probability among the three players of winning the game.

The 30 edges of a regular icosahedron are distinguished by labeling them $1,2,\dots,30$. How many different ways are there to paint each edge red, white, or blue such that each of the 20 triangular faces of the icosahedron has two edges of the same color and a third edge of a different color? [Note: the top matter on each exam paper included the logo of the Mathematical Association of America, which is itself an icosahedron.]

Find the number of ordered $64$-tuples $(x_0,x_1,\dots,x_{63})$ such that $x_0,x_1,\dots,x_{63}$ are distinct elements of $\{1,2,\dots,2017\}$ and $$x_0 + x_1 + 2x_2 + 3x_3 + \cdots + 63 x_{63}$$ is divisible by 2017.

Given a positive integer $n$, let $M(n)$ be the largest integer $m$ such that $$\binom{m}{n-1} > \binom{m-1}{n}.$$ Evaluate $$\lim_{n \to \infty} \frac{M(n)}{n}.$$

Consider a $(2m-1) \times (2n-1)$ rectangular region, where $m$ and $n$ are integers such that $m, n \geq 4$. This region is to be tiled using tiles of the two types shown:

[ Figure omitted — see the original source for the diagram. ]

(The dotted lines divide the tiles into $1 \times 1$ squares.) The tiles may be rotated and reflected, as long as their sides are parallel to the sides of the rectangular region. They must all fit within the region, and they must cover it completely without overlapping.

What is the minimum number of tiles required to tile the region?

Suppose that $S$ is a finite set of points in the plane such that the area of triangle $\triangle ABC$ is at most 1 whenever $A$, $B$, and $C$ are in $S$. Show that there exists a triangle of area 4 that (together with its interior) covers the set $S$.

Given a list of the positive integers $1,2,3,4,\dots$, take the first three numbers $1,2,3$ and their sum $6$ and cross all four numbers off the list. Repeat with the three smallest remaining numbers $4,5,7$ and their sum $16$. Continue in this way, crossing off the three smallest remaining numbers and their sum, and consider the sequence of sums produced: $6, 16, 27, 36, \dots$. Prove or disprove that there is some number in the sequence whose base 10 representation ends with $2015$.

\,

Let $T$ be the set of all triples $(a,b,c)$ of positive integers for which there exist triangles with side lengths $a,b,c$. Express $$\sum_{(a,b,c) \in T} \frac{2^a}{3^b 5^c}$$ as a rational number in lowest terms.

Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\dots,n\}$ such that $$|i-j| = 1 \mbox{ implies } |\pi(i) -\pi(j)| \leq 2$$ for all $i,j$ in $\{1,2,\dots,n\}$. Show that for $n \geq 2$, the quantity $$P_{n+5} - P_{n+4} - P_{n+3} + P_n$$ does not depend on $n$, and find its value.

A base $10$ over-expansion of a positive integer $N$ is an expression of the form $$N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_0 10^0$$ with $d_k \neq 0$ and $d_i \in \{0,1,2,\dots,10\}$ for all $i$. For instance, the integer $N = 10$ has two base 10 over-expansions: $10 = 10 \cdot 10^0$ and the usual base 10 expansion $10 = 1 \cdot 10^1 + 0 \cdot 10^0$. Which positive integers have a unique base 10 over-expansion?

In the 75th annual Putnam Games, participants compete at mathematical games. Patniss and Keeta play a game in which they take turns choosing an element from the group of invertible $n \times n$ matrices with entries in the field $\mathbb{Z}/p \mathbb{Z}$ of integers modulo $p$, where $n$ is a fixed positive integer and $p$ is a fixed prime number. The rules of the game are:

1. (1)
   A player cannot choose an element that has been chosen by either player on any previous turn.
2. (2)
   A player can only choose an element that commutes with all previously chosen elements.
3. (3)
   A player who cannot choose an element on his/her turn loses the game.

Patniss takes the first turn. Which player has a winning strategy? (Your answer may depend on $n$ and $p$.)

Recall that a regular icosahedron is a convex polyhedron having 12 vertices and 20 faces; the faces are congruent equilateral triangles. On each face of a regular icosahedron is written a nonnegative integer such that the sum of all 20 integers is 39. Show that there are two faces that share a vertex and have the same integer written on them.

A finite collection of digits $0$ and $1$ is written around a circle. An arc of length $L \geq 0$ consists of $L$ consecutive digits around the circle. For each arc $w$, let $Z(w)$ and $N(w)$ denote the number of $0$'s in $w$ and the number of $1$'s in $w$, respectively. Assume that $\left| Z(w) - Z(w') \right| \leq 1$ for any two arcs $w, w'$ of the same length. Suppose that some arcs $w_1,\dots,w_k$ have the property that $$Z = \frac{1}{k} \sum_{j=1}^k Z(w_j) \mbox{ and } N = \frac{1}{k} \sum_{j=1}^k N(w_j)$$ are both integers. Prove that there exists an arc $w$ with $Z(w) = Z$ and $N(w) = N$.

Define a function $w: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ as follows. For $\left| a \right|, \left| b \right| \leq 2$, let $w(a,b)$ be as in the table shown; otherwise, let $w(a,b) = 0$.

For every finite subset $S$ of $\mathbb{Z} \times \mathbb{Z}$, define $$A(S) = \sum_{(\mathbf{s}, \mathbf{s}') \in S \times S} w(\mathbf{s} - \mathbf{s}').$$ Prove that if $S$ is any finite nonempty subset of $\mathbb{Z} \times \mathbb{Z}$, then $A(S) > 0$. (For example, if $S = \{(0,1), (0,2), (2,0), (3,1)\}$, then the terms in $A(S)$ are $12, 12, 12, 12, 4, 4, 0, 0, 0,0,-1,-1,-2,-2,-4,-4$.)

For positive integers $n$, let the numbers $c(n)$ be determined by the rules $c(1) = 1$, $c(2n) = c(n)$, and $c(2n+1) = (-1)^n c(n)$. Find the value of $$\sum_{n=1}^{2013} c(n) c(n+2).$$

Let $\mathcal{P}$ be a nonempty collection of subsets of $\{1,\dots, n\}$ such that:

1. (i)
   if $S, S' \in \mathcal{P}$, then $S \cup S' \in \mathcal{P}$ and $S \cap S' \in \mathcal{P}$, and
2. (ii)
   if $S \in \mathcal{P}$ and $S \neq \emptyset$, then there is a subset $T \subset S$ such that $T \in \mathcal{P}$ and $T$ contains exactly one fewer element than $S$.

Suppose that $f: \mathcal{P} \to \mathbb{R}$ is a function such that $f(\emptyset) = 0$ and $$f(S \cup S') = f(S) + f(S') - f(S \cap S') \mbox{ for all $S,S' \in \mathcal{P}$.}$$ Must there exist real numbers $f_1,\dots,f_n$ such that $$f(S) = \sum_{i \in S} f_i$$ for every $S \in \mathcal{P}$?

Let $X = \{1, 2, \dots, n\}$, and let $k \in X$. Show that there are exactly $k \cdot n^{n-1}$ functions $f: X \to X$ such that for every $x \in X$ there is a $j \geq 0$ such that $f^{(j)}(x) \leq k$. [Here $f^{(j)}$ denotes the $j$^th iterate of $f$, so that $f^{(0)}(x) = x$ and $f^{(j+1)}(x) = f(f^{(j)}(x))$.]

Let $n \geq 1$ be an odd integer. Alice and Bob play the following game, taking alternating turns, with Alice playing first. The playing area consists of $n$ spaces, arranged in a line. Initially all spaces are empty. At each turn, a player either

• places a stone in an empty space, or
• removes a stone from a nonempty space $s$, places a stone in the nearest empty space to the left of $s$ (if such a space exists), and places a stone in the nearest empty space to the right of $s$ (if such a space exists).

Furthermore, a move is permitted only if the resulting position has not occurred previously in the game. A player loses if he or she is unable to move. Assuming that both players play optimally throughout the game, what moves may Alice make on her first turn?

Let $d_1, d_2, \dots, d_{12}$ be real numbers in the open interval $(1, 12)$. Show that there exist distinct indices $i, j, k$ such that $d_i, d_j, d_k$ are the side lengths of an acute triangle.

Let $S$ be a class of functions from $[0, \infty)$ to $[0, \infty)$ that satisfies:

• (i)
  The functions $f_1(x) = e^x - 1$ and $f_2(x) = \ln(x+1)$ are in $S$;
• (ii)
  If $f(x)$ and $g(x)$ are in $S$, the functions $f(x) + g(x)$ and $f(g(x))$ are in $S$;
• (iii)
  If $f(x)$ and $g(x)$ are in $S$ and $f(x) \geq g(x)$ for all $x \geq 0$, then the function $f(x) - g(x)$ is in $S$.

Prove that if $f(x)$ and $g(x)$ are in $S$, then the function $f(x) g(x)$ is also in $S$.

A round-robin tournament of $2n$ teams lasted for $2n-1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once?

Define a growing spiral in the plane to be a sequence of points with integer coordinates $P_0 = (0,0), P_1, \dots, P_n$ such that $n \geq 2$ and:

• the directed line segments $P_0 P_1, P_1 P_2, \dots, P_{n-1} P_n$ are in the successive coordinate directions east (for $P_0 P_1$), north, west, south, east, etc.;
• the lengths of these line segments are positive and strictly increasing.

[Picture omitted.] How many of the points $(x,y)$ with integer coordinates $0\leq x\leq 2011, 0\leq y\leq 2011$ cannot be the last point, $P_n$ of any growing spiral?

In a tournament, 2011 players meet 2011 times to play a multiplayer game. Every game is played by all 2011 players together and ends with each of the players either winning or losing. The standings are kept in two $2011 \times 2011$ matrices, $T = (T_{hk})$ and $W = (W_{hk})$. Initially, $T=W=0$. After every game, for every $(h,k)$ (including for $h=k$), if players $h$ and $k$ tied (that is, both won or both lost), the entry $T_{hk}$ is increased by 1, while if player $h$ won and player $k$ lost, the entry $W_{hk}$ is increased by 1 and $W_{kh}$ is decreased by 1.

Prove that at the end of the tournament, $\det(T+iW)$ is a non-negative integer divisible by $2^{2010}$.

Given a positive integer $n$, what is the largest $k$ such that the numbers $1,2,\dots,n$ can be put into $k$ boxes so that the sum of the numbers in each box is the same? [When $n=8$, the example $\{1,2,3,6\}, \{4,8\}, \{5,7\}$ shows that the largest $k$ is at least 3.]

There are 2010 boxes labeled $B_1, B_2, \dots, B_{2010}$, and $2010n$ balls have been distributed among them, for some positive integer $n$. You may redistribute the balls by a sequence of moves, each of which consists of choosing an $i$ and moving exactly $i$ balls from box $B_i$ into any one other box. For which values of $n$ is it possible to reach the distribution with exactly $n$ balls in each box, regardless of the initial distribution of balls?

Call a subset $S$ of $\{1, 2, \dots, n\}$ mediocre if it has the following property: Whenever $a$ and $b$ are elements of $S$ whose average is an integer, that average is also an element of $S$. Let $A(n)$ be the number of mediocre subsets of $\{1,2,\dots,n\}$. [For instance, every subset of $\{1,2,3\}$ except $\{1,3\}$ is mediocre, so $A(3) =7$.] Find all positive integers $n$ such that $A(n+2) - 2A(n+1) + A(n) = 1$.

Prove that for every positive integer $n$, there is a sequence of integers $a_0, a_1, \dots, a_{2009}$ with $a_0 = 0$ and $a_{2009} = n$ such that each term after $a_0$ is either an earlier term plus $2^k$ for some nonnegative integer $k$, or of the form $b\,\mathrm{mod}\,c$ for some earlier positive terms $b$ and $c$. [Here $b\,\mathrm{mod}\,c$ denotes the remainder when $b$ is divided by $c$, so $0 \leq (b\,\mathrm{mod}\,c) < c$.]

Alan and Barbara play a game in which they take turns filling entries of an initially empty $2008 \times 2008$ array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

Start with a finite sequence $a_1, a_2, \dots, a_n$ of positive integers. If possible, choose two indices $j < k$ such that $a_j$ does not divide $a_k$, and replace $a_j$ and $a_k$ by $\mathrm{gcd}(a_j, a_k)$ and $\mathrm{lcm}(a_j, a_k)$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made. (Note: gcd means greatest common divisor and lcm means least common multiple.)

Prove that there exists a constant $c>0$ such that in every nontrivial finite group $G$ there exists a sequence of length at most $c \log |G|$ with the property that each element of $G$ equals the product of some subsequence. (The elements of $G$ in the sequence are not required to be distinct. A subsequence of a sequence is obtained by selecting some of the terms, not necessarily consecutive, without reordering them; for example, $4, 4, 2$ is a subsequence of $2, 4, 6, 4, 2$, but $2, 2, 4$ is not.)

Let $n$ and $k$ be positive integers. Say that a permutation $\sigma$ of $\{1,2,\dots,n\}$ is $k$-limited if $|\sigma(i) - i| \leq k$ for all $i$. Prove that the number of $k$-limited permutations of $\{1,2,\dots,n\}$ is odd if and only if $n \equiv 0$ or $1$ (mod $2k+1$).