Found problems: 622
The numbers $1,2,3,\dots,1000$ are written on the board. Patya and Vassya are playing a game. They take turn alternatively erasing a number from the board. Patya begins. If after a turn all numbers (maybe one) on the board be divisible by a natural number greater than $1$ the player who last played loses. If after some number of steps the only remaining number on the board be $1$ then they call it a draw. Determine the result of the game if they both play their best.
In a country, the time for presidential elections has approached. There are exactly 20 million voters in the country, of which only one percent supports the current president, Miraflores. Naturally, he wants to be elected again, but on the other hand, he wants the elections to seem democratic.
Miraflores established the following voting process: all the voters are divided into several equal groups, then each of these groups is again divided into a number of equal groups, and so on. In the smallest groups, a representative is chosen. Then, the chosen electors choose representatives in the second-smallest groups, to vote in an even larger group, and so on. Finally, the representatives of the largest groups choose the president.
Miraflores divides voters into groups as he wants and instructs his supporters how to vote. Will he be able to organize the elections in such a way that he will be elected president? (If the votes are equal, the opposition wins.)
[i]From the 32nd Moscow Mathematical Olympiad[/i]
Two pirates divide the loot, consisting of two bags of coins and a diamond, according to the following rules. First the first pirate takes take a few coins from any bag and transfer them from this bag in the other the same number of coins. Then the second pirate does the same (choosing the bag from which he takes the coins at his discretion) and etc. until you can take coins according to these rules. The pirate who takes the coins last gets the diamond. Who will get the diamond if is each of the pirates trying to get it? Give your answer depending on the initial number of coins in the bags.
Ana and Beto are playing a game. Ana writes a whole number on the board. Beto then has the right to erase the number and add $2$ to it, or erase the number and subtract $3$, as many times as he wants. Beto wins if he can get $2021$ after a finite number of stages; otherwise, Ana wins. Which player has a winning strategy?
In the centre of a square swimming pool is a boy, while his teacher (who cannot swim) is standing at one corner of the pool. The teacher can run three times as fast as the boy can swim, but the boy can run faster than the teacher . Can the boy escape from the teacher?
On a lottery ticket a player has to mark $6$ numbers from $36$. Then $6$ numbers from these $36$ are drawn randomly and the ticket wins if none of the numbers that came out is marked on the ticket. Prove that
a) it is possible to mark the numbers on $9$ tickets so that one of these tickets always wins,
b) it is not possible to mark the numbers on $8$ tickets so that one of tickets always wins.
Players $A$ and $B$ play a game on a blackboard that initially contains 2020 copies of the number 1 . In every round, player $A$ erases two numbers $x$ and $y$ from the blackboard, and then player $B$ writes one of the numbers $x+y$ and $|x-y|$ on the blackboard. The game terminates as soon as, at the end of some round, one of the following holds:
[list]
[*] $(1)$ one of the numbers on the blackboard is larger than the sum of all other numbers;
[*] $(2)$ there are only zeros on the blackboard.
[/list]
Player $B$ must then give as many cookies to player $A$ as there are numbers on the blackboard. Player $A$ wants to get as many cookies as possible, whereas player $B$ wants to give as few as possible. Determine the number of cookies that $A$ receives if both players play optimally.
Alice and Bob play on an infinite board formed by equilateral triangles. In each turn, Alice first places a white token on an unoccupied cell, and then Bob places a black token on an unoccupied cell. Alice's goal is to eventually have $k$ white tokens on a line. Determine the maximum value of $k$ for which Alice can achieve this no matter how Bob plays.
[i]Proposed by Oriol Solé[/i]
On a board $4\times 4$ the numbers from $1$ to $16$ are written, one in each box. Andres and Pablo choose four numbers each. Andrés chooses the biggest of each row and Pablo, the biggest of each column. The same number can be chosen by both. Then they are removed from the board all chosen numbers. What is the greatest value that the sum of the numbers can have what are left on the board?
Two players play alternatively on an infinite square grid. The first player puts an $X$ in an empty cell and the second player puts an $O$ in an empty cell. The first player wins if he gets $11$ adjacent $X$'s in a line - horizontally, vertically or diagonally. Show that the second player can always prevent the first player from winning.
Olya and Tolya are playing a game on $[0,1]$ segment. In the beginning it is white. In the first round Tolya chooses a number $0 \leq l \leq 1$, and then Olya chooses a subsegment of $[0,1]$ of length $l$ and recolors every its point to the opposite color(white to black, black to white). In the next round players change roles, etc. The game lasts $2024$ rounds. Let $L$ be the sum of length of white segments after the end of the game. If $L > \frac{1}{2}$ Olya wins, otherwise Tolya wins. Which player has a strategy to guarantee his win?
[i]A. Naradzetski[/i]
If there are four numbers $(a,b,c,d)$ in four registers of the calculating machine, they turn into $(a-b,b-c,c-d,d-a)$ numbers whenever you press the button. Prove that if not all the initial numbers are equal, machine will obtain at least one number more than $1985$ after some number of the operations.
Initially, the numbers $1, 2, \dots, 2024$ are written on a blackboard. Trixi and Nana play a game, taking alternate turns. Trixi plays first.
The player whose turn it is chooses two numbers $a$ and $b$, erases both, and writes their (possibly negative) difference $a-b$ on the blackboard. This is repeated until only one number remains on the blackboard after $2023$ moves. Trixi wins if this number is divisible by $3$, otherwise Nana wins.
Which of the two has a winning strategy?
[i](Birgit Vera Schmidt)[/i]
Let $a$, $b$, $n$ be positive integers such that $a + b \leq n^2$. Alice and Bob play a game on an (initially uncoloured) $n\times n$ grid as follows:
- First, Alice paints $a$ cells green.
- Then, Bob paints $b$ other (i.e.uncoloured) cells blue.
Alice wins if she can find a path of non-blue cells starting with the bottom left cell and ending with the top right cell (where a path is a sequence of cells such that any two consecutive ones have a common side), otherwise Bob wins. Determine, in terms of $a$, $b$ and $n$, who has a winning strategy.
Let $n>1$ be a given positive integer. Petro and Vasyl play the following game. They take turns making moves and Petro goes first. In one turn, a player chooses one of the numbers from $1$ to $n$ that wasn't selected before and writes it on the board. The first player after whose turn the product of the numbers on the board will be divisible by $n$ loses. Who wins if every player wants to win? Find answer for each $n>1$.
[i]Proposed by Mykhailo Shtandenko, Anton Trygub[/i]
Let $n\geq 3$ be a positive integer. Alice and Bob are playing a game in which they take turns colouring the vertices of a regular $n$-gon. Alice plays the first move. Initially, no vertex is coloured. Both players start the game with $0$ points.
In their turn, a player colours a vertex $V$ which has not been coloured and gains $k$ points where $k$ is the number of already coloured neighbouring vertices of $V$. (Thus, $k$ is either $0$, $1$ or $2$.)
The game ends when all vertices have been coloured and the player with more points wins; if they have the same number of points, no one wins. Determine all $n\geq 3$ for which Alice has a winning strategy and all $n\geq 3$ for which Bob has a winning strategy.
Mr. Ganzgenau would like to take his tea mug out of the microwave right at the front. But Mr. Ganzgenau's microwave doesn't really want to be very precise play along. To be precise, the two of them play the following game:
Let $n$ be a positive integer. The turntable of the microwave makes one in $n$ seconds full turn. Each time the microwave is switched on, an integer number of seconds turned either clockwise or counterclockwise so that there are n possible positions in which the tea mug can remain. One of these positions is right up front.
At the beginning, the microwave turns the tea mug to one of the $n$ possible positions. After that Mr. Ganzgenau enters an integer number of seconds in each move, and the microwave decides either clockwise or counterclockwise this number of spin for seconds.
For which $n$ can Mr. Ganzgenau force the tea cup after a finite number of puffs to be able to take it out of the microwave right up front?
(Birgit Vera Schmidt)
[hide=original wording, in case it doesn't make much sense]Herr Ganzgenau möchte sein Teehäferl ganz genau vorne aus der Mikrowelle herausnehmen. Die Mikrowelle von Herrn Ganzgenau möchte da aber so ganz genau gar nicht mitspielen.
Ganz genau gesagt spielen die beiden das folgende Spiel:
Sei n eine positive ganze Zahl. In n Sekunden macht der Drehteller der Mikrowelle eine vollständige Umdrehung. Bei jedem Einschalten der Mikrowelle wird eine ganzzahlige Anzahl von Sekunden entweder im oder gegen den Uhrzeigersinn gedreht, sodass es n mögliche Positionen gibt, auf denen das Teehäferl stehen bleiben kann. Eine dieser Positionen ist ganz genau vorne.
Zu Beginn dreht die Mikrowelle das Teehäferl auf eine der n möglichen Positionen. Danach gibt Herr Ganzgenau in jedem Zug eine ganzzahlige Anzahl von Sekunden ein, und die Mikrowelle entscheidet, entweder im oder gegen den Uhrzeigersinn diese Anzahl von Sekunden lang zu drehen.
Für welche n kann Herr Ganzgenau erzwingen, das Teehäferl nach endlich vielen Zügen ganz genau vorne aus der Mikrowelle nehmen zu können?
(Birgit Vera Schmidt) [/hide]
Two pupils $A$ and $B$ play the following game. They begin with a pile of $1998$ matches and $A$ plays first. A player who is on turn must take a nonzero square number of matches from the pile. The winner is the one who makes the last move. Decide who has the winning strategy and give one such strategy.
Chris and Michael play a game on a board which is a rhombus of side length $n$ (a positive integer) consisting of two equilateral triangles, each of which has been divided into equilateral triangles of side length $ 1$. Each has a single token, initially on the leftmost and rightmost squares of the board, called the “home” squares (the illustration shows the case $n = 4$).
[img]https://cdn.artofproblemsolving.com/attachments/e/b/8135203c22ce77c03c144850099ad1c575edb8.png[/img]
A move consists of moving your token to an adjacent triangle (two triangles are adjacent only if they share a side). To win the game, you must either capture your opponent’s token (by moving to the triangle it occupies), or move on to your opponent’s home square.
Supposing that Chris moves first, which, if any, player has a winning strategy?
Ahmad and Salem play the following game. Ahmad writes two integers (not necessarily different) on a board. Salem writes their sum and product. Ahmad does the same thing: he writes the sum and product of the two numbers which Salem has just written.
They continue in this manner, not stopping unless the two players write the same two numbers one after the other (for then they are stuck!). The order of the two numbers which each player writes is not important.
Thus if Ahmad starts by writing $3$ and $-2$, the first five moves (or steps) are as shown:
(a) Step 1 (Ahmad) $3$ and $-2$
(b) Step 2 (Salem) $1$ and $-6$
(c) Step 3 (Ahmad) $-5$ and $-6$
(d) Step 4 (Salem) $-11$ and $30$
(e) Step 5 (Ahmad) $19$ and $-330$
(i) Describe all pairs of numbers that Ahmad could write, and ensure that Salem must write the same numbers, and so the game stops at step 2.
(ii) What pair of integers should Ahmad write so that the game finishes at step 4?
(iii) Describe all pairs of integers which Ahmad could write at step 1, so that the game will finish after finitely many steps.
(iv) Ahmad and Salem decide to change the game. The first player writes three numbers on the board, $u, v$ and $w$. The second player then writes the three numbers $u + v + w,uv + vw + wu$ and $uvw$, and they proceed as before, taking turns, and using this new rule describing how to work out the next three numbers. If Ahmad goes first, determine all collections of three numbers which he can write down, ensuring that Salem has to write the same three numbers at the next step.
A point in the cartesian plane with integer coordinates is called a lattice point. Consider the following one player game. A finite set of selected lattice points and finite set of selected segments is called a position in this game if the following hold:
(i) The endpoints of each selected segment are lattice points;
(ii) Each selected segment is parallel to a coordinate axis or to one of the lines $y = \pm x$,
(iii) Each selected segment contains exactly five lattice points, all of which are selected,
(iv) Every two selected segments have at most one common point.
A move in this game consists of selecting a lattice point and a segment such that the new set of selected lattice points and segments is a position. Prove or disprove that there exists an initial position such that the game can have infinitely many moves.
Ana and Natalia alternately play on a $ n \times n$ board (Ana rolls first and $n> 1$). At the beginning, Ana's token is placed in the upper left corner and Natalia's in the lower right corner. A turn consists of moving the corresponding piece in any of the four directions (it is not allowed to move diagonally), without leaving the board. The winner is whoever manages to place their token on the opponent's token. Determine if either of them can secure victory after a finite number of turns.
Let there be $2004$ be bicolor tiles, white on one side and black on the other, placed in a circle. A move consists of choosing a black piece and turning over three pieces: the chosen one, the one on its left and the one on its right. If at the beginning there is only one black piece, will it be possible, repeating the movement described, to make all the pieces have the white face up?
Two squares of area $38$ are given. Each of the squares is divided into $38$ connected pieces of unit area by simple curves. Then the two squares are patched together. Show that one can sting the patched squares with $38$ needles so that every piece of each square is stung exactly once.
(a) On each square of a squared sheet of paper of size $20 \times 20$ there is a soldier. Vanya chooses a number $d$ and Petya moves the soldiers to new squares in such a way that each soldier is moved through a distance of at least $d$ (the distance being measured between the centres of the initial and the new squares) and each square is occupied by exactly one soldier. For which $d$ is this possible?
(Give the maximum possible $d$, prove that it is possible to move the soldiers through distances not less than $d$ and prove that there is no greater $d$ for which this procedure may be carried out.)
(b) Answer the same question as (a), but with a sheet of size $21 \times 21$.
(SS Krotov, Moscow)