Consider a sequence of words , consisting of the letters $A$ and $B$ . The first word in the sequence is "$A$" . The k-th word i s obtained from the $(k-1)$-th by means of the following transformation : each $A$ is substituted by $AAB$ , and each $B$ is substituted by $A$. It is easily seen that every word is an initial part of the next word. The initial parts of these words coincide to give a sequence of letters $AABAABAAA BAABAAB...$ (a) In which place of this sequence is the $1000$-th letter $A$? (b ) Prove that this sequence is not periodic. (V . Galperin , Moscows)

There are $ 6n \plus{} 4$ mathematicians participating in a conference which includes $ 2n \plus{} 1$ meetings. Each meeting has one round table that suits for $ 4$ people and $ n$ round tables that each table suits for $ 6$ people. We have known that two arbitrary people sit next to or have opposite places doesn't exceed one time. 1. Determine whether or not there is the case $ n \equal{} 1$. 2. Determine whether or not there is the case $ n > 1$.

Nina and Tadashi play the following game. Initially, a triple $(a, b, c)$ of nonnegative integers with $a+b+c=2021$ is written on a blackboard. Nina and Tadashi then take moves in turn, with Nina first. A player making a move chooses a positive integer $k$ and one of the three entries on the board; then the player increases the chosen entry by $k$ and decreases the other two entries by $k$. A player loses if, on their turn, some entry on the board becomes negative. Find the number of initial triples $(a, b, c)$ for which Tadashi has a winning strategy.

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The cycle of graph $G(V,E)$ is a set of distinct vertices ${v_1,v_2...,v_n}\subseteq V$, $v_iv_{i+1}\in E$ for all $1\leq i\leq n$ $(n\geq 3, v_{n+1}=v_1)$; a cycle containing a chord is the cycle ${v_1,v_2...,v_n}$, such that there exist $i,j, 1< i-j< n-1$, satisfying $v_iv_j\in E$.

Is it possible to cover a $13\times 13$ chessboard with forty-two pieces of dimensions $4\times 1$ such that only the central square of the chessboard remains uncovered?

[u]Round 1[/u] [b]p1.[/b] Alice and Bob compiled a list of movies that exactly one of them saw, then Cindy and Dale did the same. To their surprise, these two lists were identical. Prove that if Alice and Cindy list all movies that exactly one of them saw, this list will be identical to the one for Bob and Dale. [b]p2.[/b] Several whole rounds of cheese were stored in a pantry. One night some rats sneaked in and consumed $10$ of the rounds, each rat eating an equal portion. Some were satisfied, but $7$ greedy rats returned the next night to finish the remaining rounds. Their portions on the second night happened to be half as large as on the first night. How many rounds of cheese were initially in the pantry? [b]p3.[/b] You have $100$ pancakes, one with a single blueberry, one with two blueberries, one with three blueberries, and so on. The pancakes are stacked in a random order. Count the number of blueberries in the top pancake, and call that number N. Pick up the stack of the top N pancakes, and flip it upside down. Prove that if you repeat this counting-and-flipping process, the pancake with one blueberry will eventually end up at the top of the stack. [b]p4.[/b] There are two lemonade stands along the $4$-mile-long circular road that surrounds Sour Lake. $100$ children live in houses along the road. Every day, each child buys a glass of lemonade from the stand that is closest to her house, as long as she does not have to walk more than one mile along the road to get there. A stand's [u]advantage [/u] is the difference between the number of glasses it sells and the number of glasses its competitor sells. The stands are positioned such that neither stand can increase its advantage by moving to a new location, if the other stand stays still. What is the maximum number of kids who can't buy lemonade (because both stands are too far away)? [b]p5.[/b] Merlin uses several spells to move around his $64$-room castle. When Merlin casts a spell in a room, he ends up in a different room of the castle. Where he ends up only depends on the room where he cast the spell and which spell he cast. The castle has the following magic property: if a sequence of spells brings Merlin from some room $A$ back to room $A$, then from any other room $B$ in the castle, that same sequence brings Merlin back to room $B$. Prove that there are two different rooms $X$ and $Y$ and a sequence of spells that both takes Merlin from $X$ to $Y$ and from $Y$ to $X$. [u]Round 2[/u] [b]p6.[/b] Captains Hook, Line, and Sinker are deciding where to hide their treasure. It is currently buried at the $X$ in the map below, near the lairs of the three pirates. Each pirate would prefer that the treasure be located as close to his own lair as possible. You are allowed to propose a new location for the treasure to the pirates. If at least two out of the three pirates prefer the new location (because it moves closer to their own lairs), then the treasure will be moved there. Assuming the pirates’ lairs form an acute triangle, is it always possible to propose a sequence of new locations so that the treasure eventually ends up in your backyard (wherever that is)? [img]https://cdn.artofproblemsolving.com/attachments/c/c/a9e65624d97dec612ef06f8b30be5540cfc362.png[/img] [b]p7.[/b] Homer went on a Donut Diet for the month of May ($31$ days). He ate at least one donut every day of the month. However, over any stretch of $7$ consecutive days, he did not eat more than $13$ donuts. Prove that there was some stretch of consecutive days over which Homer ate exactly $30$ donuts. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

For each positive integer $n$, the Bank of Cape Town issues coins of denomination $\frac1n$. Given a finite collection of such coins (of not necessarily different denominations) with total value at most most $99+\frac12$, prove that it is possible to split this collection into $100$ or fewer groups, such that each group has total value at most $1$.

Let $M$ be the set of positive odd integers. For every positive integer $n$, denote $A(n)$ the number of the subsets of $M$ whose sum of elements equals $n$. For instance, $A(9) = 2$, because there are exactly two subsets of $M$ with the sum of their elements equal to $9$: $\{9\}$ and $\{1, 3, 5\}$. a) Prove that $A(n) \le A(n + 1)$ for every integer $n \ge 2$. b) Find all the integers $n \ge 2$ such that $A(n) = A(n + 1)$

Let $k$ be a positive integer. The organising commitee of a tennis tournament is to schedule the matches for $2k$ players so that every two players play once, each day exactly one match is played, and each player arrives to the tournament site the day of his first match, and departs the day of his last match. For every day a player is present on the tournament, the committee has to pay $1$ coin to the hotel. The organisers want to design the schedule so as to minimise the total cost of all players' stays. Determine this minimum cost.

Some students on the faculty speak several languages and some - Russian only. $50$ of them know English, $50$ -- French and $50$ -- Spanish. Prove that it is possible to divide them onto $5$ groups, not necessary equal, to get $10$ of them knowing English, $10$ -- French and $10$ -- Spanish in each group.

There are $ n$ football teams in a round-robin competition where every 2 teams meet once. The winner of each match receives 3 points while the loser receives 0 points. In the case of a draw, both teams receive 1 point each. Let $ k$ be as follows: $ 2 \leq k \leq n \minus{} 1$. At least how many points must a certain team get in the competition so as to ensure that there are at most $ k \minus{} 1$ teams whose scores are not less than that particular team's score?

Let $n$ be an odd positive integer, and consider an infinite square grid. Prove that it is impossible to fill in one of $1,2$ or $3$ in every cell, which simultaneously satisfies the following conditions: (1) Any two cells which share a common side does not have the same number filled in them. (2) For any $1\times 3$ or $3\times 1$ subgrid, the numbers filled does not contain $1,2,3$ in that order be it reading from top to bottom, bottom to top, or left to right, or right to left. (3) The sum of numbers of any $n\times n$ subgrid is the same.

$a$ and $b$ are natural numbers such that $b > a > 1$, and $a$ does not divide $b$. The sequence of natural numbers $\{b_n\}_{n=1}^\infty$ satisfies $b_{n + 1} \geq 2b_n \forall n \in \mathbb{N}$. Does there exist a sequence $\{a_n\}_{n=1}^\infty$ of natural numbers such that for all $n \in \mathbb{N}$, $a_{n + 1} - a_n \in \{a, b\}$, and for all $m, l \in \mathbb{N}$ ($m$ may be equal to $l$), $a_m + a_l \not\in \{b_n\}_{n=1}^\infty$?

There are $N$ pupils in a school class, and there are several communities among them. Sociability of a pupil will mean the number of pupils in the largest community to which the pupil belongs (if the pupil belongs to none then the sociability equals $1$). It occurred that all girls in the class have different sociabilities. What is the maximum possible number of girls in the class?

A unit square is cut by $n$ straight lines . Prove that in at least one of these parts one can completely fit a square with side $\frac{1}{n+1}$ [hide=original wording]Одиничний квадрат розрізано $n$ прямими на частини. Доведіть, що хоча б в одній з цих частин можна повністю розмістити квадрат зі стороною $\frac{1}{n+1}$[/hide] [hide=notes] The selection panel jury made a mistake because the solution known to it turned out to be incorrect. As it turned out, the assertion of the problem is still correct, although it cannot be proved by simple methods, see. article: Keith Ball. Тhe plank problem for symmetric bodies // Іпѵепііопез МаіЬешаІіеае. — 1991. — Ѵоі. 104, по. 1. — Р. 535-543. [url]https://arxiv.org/abs/math/9201218[/url][/hide]

Given an alfabet of $n$ letters. A sequence of letters such that between any 2 identical letters there are no 2 identical letters is called a [i]word[/i]. a) Find the maximal possible length of a [i]word[/i]. b) Find the number of the [i]words[/i] of maximal length.

The set $M$ was formed from the plane by removing three points $A, B, C$, which are vertices of the triangle. What is the smallest number of convex sets whose union is $M$? [hide=original wording] Množina M Vznikla z roviny vyjmutím tří bodů A, B, C, které jsou vrcholy trojúhelníka. Jaký je nejmenší počet konvexních množin, jejichž sjednocením je M?[/hide]

A graph is called a [i]self-intersecting [/i]graph if it is isomorphic to a graph whose every edge is a segment and every two edges intersect. Notice that no edge contains a vertex except its two endings. a) Find all $ n$'s for which the cycle of length $ n$ is self-intersecting. b) Prove that in a self-intersecting graph $ |E(G)|\leq|V(G)|$. c) Find all self-intersecting graphs. [img]http://i35.tinypic.com/x43s5u.png[/img]

Three wise men live in an old region. As they do not always agree on their advice to the king, he decided to stay with the wisest of the three, killing the others. To decide which of them was saved, performed the following test: He put each sage a hat, without him seeing its color, then locked them in a common room and told them: $\bullet$ Only the first to guess the color of his own hat will save his life. $\bullet$ In total there are five hats, three are white and two are black. $\bullet$ You cannot communicate with each other, but you can look at each other. After a long time, one of the wise men says: "I know the color of my hat." What color did they have? How did you figure it out? What color were the other hats used?

How many ways can you mark $8$ squares of an $8\times 8$ chessboard so that no two marked squares are in the same row or column, and none of the four corner squares is marked? (Rotations and reflections are considered different.)

Prove that it is impossible to fill the cells of an $8 \times 8$ table with the numbers from $ 1$ to $64$ (each number must be used once) so that for each $2\times 2$ square, the difference between products of the numbers on it’s diagonals will be equal to $ 1$.

For which values of $n$ it is possible to cover the side wall of staircase of n steps (for $n = 6$ in the figure) with plates of shown shape? The width and height of each step is $1$ dm, the dimensions of plate are $2 \times 2$ dm and from the corner there is cut out a piece with dimensions $1\times 1$ dm. [img]https://cdn.artofproblemsolving.com/attachments/e/e/ac7a52f3dd40480f82024794708c5a449e0c2b.png[/img]

For natural numbers $n$ and $b$, let $V(n, b)$ denote the number of decompositions of $n$ into the product of integers each of which is greater than $b$: for example $$36 = 6\times 6 = 4\times 9 = 3\times 3\times 4 = 3\times 12,$$ i.e. $V(36,2) = 5$. Prove that $V(n, b) < n/b$ for all $n$ and $b$. (N.B. Vasiliev, Moscow)

There are some checkers in $n\cdot n$ size chess board.Known that for all numbers $1\le i,j\le n$ if checkwork in the intersection of $i$ th row and $j$ th column is empty,so the number of checkers that are in this row and column is at least $n$.Prove that there are at least $\frac{n^2}{2}$ checkers in chess board.

A $2^{2014} + 1$ by $2^{2014} + 1$ grid has some black squares filled. The filled black squares form one or more snakes on the plane, each of whose heads splits at some points but never comes back together. In other words, for every positive integer $n$ greater than $2$, there do not exist pairwise distinct black squares $s_1$, $s_2$, \dots, $s_n$ such that $s_i$ and $s_{i+1}$ share an edge for $i=1,2, \dots, n$ (here $s_{n+1}=s_1$). What is the maximum possible number of filled black squares? [i]Proposed by David Yang[/i]