Found problems: 622
Two people play a game on a $9 \times 9$ board. They move alternately. On each move, the first player draws a cross in an empty cell, and the second player draws a nought in an empty cell. When all $81$ cells are filled, the number $K$ of rows and columns in which there are more crosses and the number $H$ of rows and columns in which there are more noughts are counted. The score for the first player is the difference $B = K- H$. Find a value of $B$ such that the first player can guarantee a score of at least $B$, while the second player can hold the first player's score to at most B, regardless how the opponent plays.
(A Kanel)
Alice and Bob play the following game. To start, Alice arranges the numbers $1,2,\ldots,n$ in some order in a row and then Bob chooses one of the numbers and places a pebble on it. A player's [i]turn[/i] consists of picking up and placing the pebble on an adjacent number under the restriction that the pebble can be placed on the number $k$ at most $k$ times. The two players alternate taking turns beginning with Alice. The first player who cannot make a move loses. For each positive integer $n$, determine who has a winning strategy.
(Game) At the beginning of the game, the organisers place paper disks on the table, grouped into piles which may contain various numbers of disks. The two players take turns. On a player’s turn, their opponent selects two piles (one if there is only one pile left), and the player must remove some number of disks from one of the piles selected. This means that at least one disk has to be removed, and removing all disks in the pile is also permitted. The player removing the last disk from the table wins.
[i]Defeat the organisers in this game twice in a row! A starting position will be given and then you can decide whether you want to go first or second.[/i]
Two players $A$ and $B$ play the following game:
$A$ chooses a point, with integer coordinates, on the plane and colors it green, then $B$ chooses $10$ points of integer coordinates, not yet colored, and colors them yellow. The game always continues with the same rules; $A$ and $B$ choose one and ten uncolored points and color them green and yellow, respectively.
a. The objective of $A$ is to achieve $111^2$ green points that are the intersections of $111$ horizontal lines and $111$ vertical lines (parallel to the coordinate axes). $B$'s goal is to stop him. Determine which of the two players has a strategy that ensures you achieve your goal.
b. The objective of $A$ is to achieve $4$ green points that are the vertices of a square with sides parallel to the coordinate axes. $B$'s goal is to stop him. Determine which of the two players has a strategy that will ensure that they achieve their goal.
All the cells of a $10\times10$ board are colored white initially. Two players are playing a game with alternating moves. A move consists of coloring any un-colored cell black. A player is considered to loose, if after his move no white domino is left. Which of the players has a winning strategy?
[I]Proposed by A. Khrabrov[/i]
Kostya and Sergey play a game on a white strip of length 2016 cells. Kostya (he plays first) in one move should paint black over two neighboring white cells. Sergey should paint either one white cell either three neighboring white cells. It is forbidden to make a move, after which a white cell is formed the doesn't having any white neighbors. Loses the one that can make no other move. However, if all cells are painted, then Kostya wins. Who will win if he plays the right game (has a winning strategy)?
$8$ CPLP football teams competed in a championship in which each team played one and only time with each of the other teams. In football, each win is worth $3$ points, each draw is worth $1$ point and the defeated team does not score. In that championship four teams were in first place with $15$ points and the others four came in second with $N$ points each. Knowing that there were $12$ draws throughout the championship, determine $N$.
(a) Two people perform a card trick. The first performer takes $5$ cards from a $52$-card deck (previously shuffled by a member of the audience) , looks at them, and arranges them in a row from left to right: one face down (not necessarily the first one) , the others face up . The second performer guesses correctly the card which is face down. Prove that the performers can agree on a system which always makes this possible.
(b) For their second trick, the first performer arranges four cards in a row, face up, the fifth card is kept hidden. Can they still agree on a system which enables the second performer to correctly guess the hidden card?
(G Galperin)
Two players are writting in turn natural numbers not exceeding $p$. The rules forbid to write the divisors of the numbers already having been written. Those who cannot make his move looses.
a) Who, and how, can win if $p=10$?
b) Who wins if $p=1000$?
There are $11$ empty boxes and a pile of stones. Two players play the following game by alternating moves: In one move a player takes $10$ stones from the pile and places them into boxes, taking care to place no more than one stone in any box. The winner is the player after whose move there appear $21$ stones in one of the boxes for the first time. If a player wants to guarantee that they win the game, should they go first or second? Explain your reasoning.
Let $n$ be a positive integer. Humanity will begin to colonize Mars. The SpaceY and SpaceZ agencies will be responsible for traveling between the planets. To prevent the rockets from colliding, they will travel alternately, with SpaceY making the first trip. On each trip, the responsible agency will do one of two types of mission:
(i) choose a positive integer $k$ and take $k$ people to Mars, creating a new colony on the planet and settling them in that colony;
(ii) choose some existing colony on Mars and a positive integer $k$ strictly smaller than the population of that colony, and bring $k$ people from that colony back to Earth.
To maintain the organization on Mars, a mission cannot result in two colonies with the same population and the number of colonies must be at most $n$. The first agency that cannot carry out a mission will go bankrupt. Determine, in terms of $n$, which agency can guarantee that it will not go bankrupt first.
There are $n$ coins in the pile. Two players play a game by alternately performing a move. A move consists of taking $5,7$ or $11$ coins away from the pile. The player unable to perform a move loses the game. Which player - the one playing first or second - has the winning strategy if:
(a) $n=2001$;
(b) $n=5000$?
Given integer $n \geq 3$. There are $n$ dots marked $1$ to $n$ clockwise on a big circle. And between every two neighboring dots, there is a light. At first, every light were dark.
A and B are playing a game, A pick up $n$ pairs from $\{ (i,j)|1 \leq i < j \leq n \}$ and for every pairs $(i,j)$. B starts from the point marked $i$ and choose to walk clockwise or counterclockwise to the point marked $j$. And B invert the status of all passing lights (bright $\leftrightarrow$ dark)
A hopes the number of dark light can be as much as possible while B hopes the number of bright light can be as much as possible. Suppose A, B are both smart, how many lights are bright in the end?
[i]Proposed by BlessingOfHeaven[/i]
[img]https://pbs.twimg.com/profile_images/1014932415201120256/u9KAaMZ4_400x400.jpg[/img]
Three persons $A,B,C$, are playing the following game:
A $k$-element subset of the set $\{1, . . . , 1986\}$ is randomly chosen, with an equal probability of each choice, where $k$ is a fixed positive integer less than or equal to $1986$. The winner is $A,B$ or $C$, respectively, if the sum of the chosen numbers leaves a remainder of $0, 1$, or $2$ when divided by $3$.
For what values of $k$ is this game a fair one? (A game is fair if the three outcomes are equally probable.)
A frog jumps on the coordinate lattice, starting from the point $(1,1)$, according to the following rules:
(i) From point $(a,b)$ the frog can jump to either $(2a,b)$ or $(a,2b)$;
(ii) If $a>b$, the frog can also jump from $(a,b)$ to $(a-b,b)$, while for $a<b$ it can jump from $(a,b)$ to $(a,b-a)$.
Can the frog get to the point: (a) $(24,40)$; (b) $(40,60)$; (c) $(24,60)$; (d) $(200,4)$?
A pile of $n$ pebbles is placed in a vertical column. This configuration is modified according to the following rules. A pebble can be moved if it is at the top of a column which contains at least two more pebbles than the column immediately to its right. (If there are no pebbles to the right, think of this as a column with 0 pebbles.) At each stage, choose a pebble from among those that can be moved (if there are any) and place it at the top of the column to its right. If no pebbles can be moved, the configuration is called a [i]final configuration[/i]. For each $n$, show that, no matter what choices are made at each stage, the final configuration obtained is unique. Describe that configuration in terms of $n$.
[url=http://www.mathlinks.ro/Forum/viewtopic.php?p=119189]IMO ShortList 2001, combinatorics problem 7, alternative[/url]
Jesse and Tjeerd are playing a game. Jesse has access to $n\ge 2$ stones. There are two boxes: in the black box there is room for half of the stones (rounded down) and in the white box there is room for half of the stones (rounded up). Jesse and Tjeerd take turns, with Jesse starting. Jesse grabs in his turn, always one new stone, writes a positive real number on the stone and places put him in one of the boxes that isn't full yet. Tjeerd sees all these numbers on the stones in the boxes and on his turn may move any stone from one box to the other box if it is not yet full, but he may also choose to do nothing. The game stops when both boxes are full. If then the total value of the stones in the black box is greater than the total value of the stones in the white box, Jesse wins; otherwise win Tjeerd. For every $n \ge 2$, determine who can definitely win (and give a corresponding winning strategy).
Alice has 8 coins. She knows for sure only that 7 of these coins are genuine and weigh the same, while the remaining one is counterfeit and is either heavier or lighter than any of the other 7. Bob has a balance scale. The scale shows which plate is heavier but does not show by how much. For each measurement, Alice pays Bob beforehand a fee of one coin. If a genuine coin has been paid, Bob tells Alice the correct weighing outcome, but if a counterfeit coin has been paid, he gives a random answer. Alice wants to identify 5 genuine coins and not to give any of these coins to Bob. Can Alice achieve this result for sure?
Albert and Brita play a game with a bar of $19$ adjacent squares. Initially, there is a button on the middle square of the bar. At every turn Albert mentions one positive integer less than $5$, and Brita moves button a number of squares in the direction of her choice - while doing so however, Brita must not move the button more than twice in one direction order. Prove that Albert can choose the numbers so that by the $19$th turn, Brita to be forced to move the button out of the bar.
Let $(a,b)$ be a pair of natural numbers. Henning and Paul play the following game. At the beginning there are two piles of $a$ and $b$ coins respectively. We say that $(a,b)$ is the [i]starting position [/i]of the game. Henning and Paul play with the following rules:
$\bullet$ They take turns alternatively where Henning begins.
$\bullet$ In every step each player either takes a positive integer number of coins from one of the two piles or takes same natural number of coins from both piles.
$\bullet$ The player how take the last coin wins.
Let $A$ be the set of all positive integers like $a$ for which there exists a positive integer $b<a$ such that Paul has a wining strategy for the starting position $(a,b)$. Order the elements of $A$ to construct a sequence $a_1<a_2<a_3<\dots$
$(a)$ Prove that $A$ has infinity many elements.
$(b)$ Prove that the sequence defined by $m_k:=a_{k+1}-a_{k}$ will never become periodic. (This means the sequence $m_{k_0+k}$ will not be periodic for any choice of $k_0$)
Kiko and Ñoño play with a rod of length $2n$ where $n \le 3$ is an integer. Kiko cuts the rod in $ k \le 2n$ pieces of integer lengths. Then Ñoño has to arrange these pieces so that they form a hexagon of equal opposite sides and equal angles. The pieces can not be split and they all have to be used. If Ñoño achieves his goal, he wins, in any other case, Kiko wins. Determine which victory can be secured based on $k$.
Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
\[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]
turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )
The [i]liar's guessing game[/i] is a game played between two players $A$ and $B$. The rules of the game depend on two positive integers $k$ and $n$ which are known to both players.
At the start of the game $A$ chooses integers $x$ and $N$ with $1 \le x \le N.$ Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. Player $B$ now tries to obtain information about $x$ by asking player $A$ questions as follows: each question consists of $B$ specifying an arbitrary set $S$ of positive integers (possibly one specified in some previous question), and asking $A$ whether $x$ belongs to $S$. Player $B$ may ask as many questions as he wishes. After each question, player $A$ must immediately answer it with [i]yes[/i] or [i]no[/i], but is allowed to lie as many times as she wants; the only restriction is that, among any $k+1$ consecutive answers, at least one answer must be truthful.
After $B$ has asked as many questions as he wants, he must specify a set $X$ of at most $n$ positive integers. If $x$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that:
1. If $n \ge 2^k,$ then $B$ can guarantee a win.
2. For all sufficiently large $k$, there exists an integer $n \ge (1.99)^k$ such that $B$ cannot guarantee a win.
[i]Proposed by David Arthur, Canada[/i]
On a table, there is an empty bag and a chessboard containing exactly one token on each square. Next to the table is a large pile that contains an unlimited supply of tokens. Using only the following types of moves what is the maximum possible number of tokens that can be in the bag?
$\bullet$ Type 1: Choose a non-empty square on the chessboard that is not in the rightmost column. Take a token from this square and place it, along with one token from the pile, on the square immediately to its right.
$\bullet$ Type 2: Choose a non-empty square on the chessboard that is not in the bottommost row. Take a token from this square and place it, along with one token from the pile, on the square immediately below it.
$\bullet$ Type 3: Choose two adjacent non-empty squares. Remove a token from each and put them both into the bag.
(a) The vertices of a regular $10$-gon are painted in turn black and white. Two people play the following game . Each in turn draws a diagonal connecting two vertices of the same colour . These diagonals must not intersect . The winner is the player who is able to make the last move. Who will win if both players adopt the best strategy?
(b) Answer the same question for the regular $12$-gon .
(V.G. Ivanov)