For teachers / Printable sets /Stage 7 · Combinatorics

Stage 7 · Combinatorics

10 problems · National olympiad second round; IMO P1/P4 · mathsolympiadprep.com

Print or save as PDF The answer key prints on its own page at the end.

1. Given a positive integer $k$, a pigeon and a seagull play a game on an $n\times n$ board. The pigeon goes first, and they take turns doing the operations. The pigeon will choose $m$ grids and lay an egg in each grid he chooses. The seagull will choose a $k\times k$ grids and eat all the eggs inside them. If at any point every grid in the $n\times n$ board has an egg in it, then the pigeon wins. Else, the seagull wins. For every integer $n\geq k$, find all $m$ such that the pigeon wins.

   Proposed by amano_hina

   Combinatorics Solution and answer checking →

2. Let $m > 1$ be an integer, $n$ is an odd number satisfying $3\le n < 2m,$ number $a_{i,j} (i,j\in N, 1\le i\le m, 1\le j\le n)$ satisfies $(1)$ for any $1\le j\le n, a_{1,j},a_{2,j},\cdots,a_{m,j}$ is a permutation of $1,2,3,\cdots,m; (2)$ for any $\text{1 < i m, 1 j n 1, |a i,j a i, j 1 | 1}$ holds. Find the minimal value of $M$, where $\text{M max 1 < i < m j 1 n a i,j .}$

   Combinatorics Solution and answer checking →

3. Once in a restaurant Dr. Strange found out that there were 12 types of food items from 1 to 12 on the menu. He decided to visit the restaurant 12 days in a row and try a different food everyday. 1st day, he tries one of the items from the first two. On the 2nd day, he eats either item 3 or the item he didn’t tried on the 1st day. Similarly, on the 3rd day, he eats either item 4 or the item he didn’t tried on the 2nd day. If someday he's not able to choose items that way, he eats the item that remained uneaten from the menu. In how many ways can he eat the items for 12 days?

   Combinatorics Solution and answer checking →

4. Let $N$ denote the number of ordered 2011-tuples of positive integers $(a_1,a_2,\ldots,a_{2011})$ with $1\le a_1,a_2,\ldots,a_{2011} \le 2011^2$ such that there exists a polynomial $f$ of degree $4019$ satisfying the following three properties:
   
   - $f(n)$ is an integer for every integer $n$;
   - $2011^2 \mid f(i) - a_i$ for $i=1,2,\ldots,2011$;
   - $2011^2 \mid f(n+2011) - f(n)$ for every integer $n$.
   Find the remainder when $N$ is divided by $1000$.

   Victor Wang

   Combinatorics Solution and answer checking →

5. Given the natural $n$. We shall call word sequence from $n$ letters of the alphabet, and distance $\rho(A, B)$ between words $A=a_1a_2\dots a_n$ and $B=b_1b_2\dots b_n$ , the number of digits in which they differ (that is, the number of such $i$, for which $a_i\ne b_i$). We will say that the word $C$ lies between words $A$ and $B$ , if $\rho (A,B)=\rho(A,C)+\rho(C,B)$. What is the largest number of words you can choose so that among any three, there is a word lying between the other two?

   Combinatorics Solution and answer checking →

6. Two players, $A$ and $B,$ alternatively take stones from a pile of $n \geq 2$ stones. $A$ plays first and in his first move he must take at least one stone and at most $n-1$ stones. Then each player must take at least one stone and at most as many stones as his opponent took in the previous move. The player who takes the last stone wins. Which player has a winning strategy?

   Combinatorics Solution and answer checking →

7. Terence Tao is playing rock-paper-scissors. Because his mental energy is focused on solving the twin primes conjecture, he uses the following very simple strategy:
   
      ·He plays rock first.
      ·On each subsequent turn, he plays a different move than the previous one, each with probability ½.
   
   What is the probability that his 5th move will be rock?

   Combinatorics Solution and answer checking →

8. Find all functions $f,g: \mathbb{R} \to \mathbb{R}$ such that satisfies
   $$f(x^2-g(y))=g(x)^2-y$$
   for all $x,y \in \mathbb{R}$

   Combinatorics Solution and answer checking →

9. Compute the number of ordered quadruples $(a,b,c,d)$ of distinct positive integers such that $\displaystyle \binom{\binom{a}{b}}{\binom{c}{d}}=21$.

   Proposed by Luke Robitaille

   Combinatorics Solution and answer checking →

10. Given $X=\{0,a,b,c\}$, let $M(X)=\{f|f: X\to X\}$ denote the set of all functions from $X$ into itself. An addition table on $X$ is given us follows:
    $+$ $0$ $a$ $b$ $c$
    $0$ $0$ $a$ $b$ $c$
    $a$ $a$ $0$ $c$ $b$
    $b$ $b$ $c$ $0$ $a$
    $c$ $c$ $b$ $a$ $0$
    a)If $S=\{f\in M(X)|f(x+y+x)=f(x)+f(y)+f(x)\forall x,y\in X\}$, find $|S|$.
    b)If $I=\{f\in M(X)|f(x+x)=f(x)+f(x)\forall x\in X\}$, find $|I|$.

    Combinatorics Solution and answer checking →

Answer key — Stage 7 · Combinatorics

Worked solutions for every problem are on the site, one page per problem.

1. $k \leq n \leq 2k - 1$ open
2. $7$ open
3. $2048$ open
4. $281$ open
5. $n + 1$ open
6. $n$ open
7. $\frac{1}{2}$ open
8. $f(x) = g(x) = x \ \ \forall x \in \mathbb{R}$ open
9. $13$ open
10. $|S| = 1$ open

Problems belong to the competitions that set them and are reproduced from open datasets under their licences; every problem page names its source. Free to copy for classroom use.