Found problems: 1385
Viktor and Natalia play a colouring game with a 3-dimensional cube taking turns alternatingly. Viktor goes first, and on each of his turns, he selects an unpainted edge, and paints it violet. On each of Natalia's turns, she selects an unpainted edge, or at most once during the game a face diagonal, and paints it neon green. If the player on turn cannot make a legal move, then the turn switches to the other player. The game ends when nobody can make any more legal moves.
Natalia wins if at the end of the game every vertex of the cube can be reached from every other vertex by traveling only along neon green segments (edges or diagonal), otherwise Viktor wins.
Who has a winning strategy? (Prove your answer.)
[i]Authored by Viktor Simjanoski[/i]
There are $14$ players participating at a chess tournament, each playing one game with every other player. After the end of the tournament, the players were ranked in descending order based on their points. The sum of the points of the first three players is equal with the sum of the points of the last nine players. What is the highest possible number of draws in the tournament.(For a victory the player gets $1$ point, for a loss $0$ points, in a draw both players get $0,5$ points.)
A magician has $300$ cards with numbers from $1$ to $300$ written on them, each number on exactly one card. The magician then lays these cards on a $3 \times 100$ rectangle in the following way - one card in each unit square so that the number cannot be seen and cards with consecutive numbers are in neighbouring squares. Afterwards, the magician turns over $k$ cards of his choice. What is the smallest value of $k$ for which it can happen that the opened cards definitely determine the exact positions of all other cards?
Régis, Ed and Rafael are at the IMO. They are going to play a game in Bath, and there are $2^n$ houses in the city. Régis and Ed will team up against Rafael. The game operates as follows: First, Régis and Ed think on a strategy and then let Rafael know it. After this, Régis and Ed no longer communicate, and the game begins. Rafael decides on an order to visit the houses and then starts taking Régis to them in that order. At each house, except for the last one, Régis choose a number between $1$ and $n$ and places it in the house. In the last house, Rafael chooses a number from $1$ to $n$ and places it there.
Afterwards, Ed sees all the houses and the numbers in them, and he must guess in which house Rafael placed the number. Ed is allowed $k$ guesses. What is the smallest $k$ for which there exists a strategy for Ed and Régis to ensure that Ed correctly guess the house where Rafael placed the number?
Nickolas and Peter divide $2n+1$ nuts amongst each other. Both of them want to get as many as possible. Three methods are suggested to them for doing so, each consisting of three stages. The first two stages are the same in all three methods:
[i]Stage 1:[/i] Peter divides the nuts into 2 heaps, each containing at least 2 nuts.
[i]Stage 2:[/i] Nickolas divides both heaps into 2 heaps, each containing at least 1 nut.
Finally, stage 3 varies among the three methods as follows:
[i]Method 1:[/i] Nickolas takes the smallest and largest of the heaps.
[i]Method 2:[/i] Nickolas takes the two middle size heaps.
[i]Method 3:[/i] Nickolas chooses between taking the biggest and the smallest heap or the two middle size heaps, but gives one nut to Peter for the right of choice.
Determine the most and the least profitable method for Nickolas.
Bob proposes the following game to Johanna. The board in the figure is an equilateral triangle subdivided in turn into $256$ small equilateral triangles, one of which is painted in black. Bob chooses any point inside the board and places a small token. Johanna can make three types of plays. Each of them consists of choosing any of the $3$ vertices of the board and move the token to the midpoint between the current position of the tile and the chosen vertex. In the second figure we see an example of a move in which Johana chose vertex $A$. Johanna wins if she manages to place her piece inside the triangle black. Prove that Johanna can always win in at most $4$ moves.
[asy]
unitsize(8 cm);
pair A, B, C;
int i;
A = dir(60);
C = (0,0);
B = (1,0);
fill((6/16*(1,0) + 1/16*dir(60))--(7/16*(1,0) + 1/16*dir(60))--(6/16*(1,0) + 2/16*dir(60))--cycle, gray(0.7));
draw(A--B--C--cycle);
for (i = 1; i <= 15; ++i) {
draw(interp(A,B,i/16)--interp(A,C,i/16));
draw(interp(B,C,i/16)--interp(B,A,i/16));
draw(interp(C,A,i/16)--interp(C,B,i/16));
}
label("$A$", A, N);
label("$B$", B, SE);
label("$C$", C, SW);
[/asy]
[asy]
unitsize(8 cm);
pair A, B, C, X, Y, Z;
int i;
A = dir(60);
C = (0,0);
B = (1,0);
X = 9.2/16*(1,0) + 3.3/16*dir(60);
Y = (A + X)/2;
Z = rotate(60,X)*(Y);
fill((6/16*(1,0) + 1/16*dir(60))--(7/16*(1,0) + 1/16*dir(60))--(6/16*(1,0) + 2/16*dir(60))--cycle, gray(0.7));
draw(A--B--C--cycle);
for (i = 1; i <= 15; ++i) {
draw(interp(A,B,i/16)--interp(A,C,i/16));
draw(interp(B,C,i/16)--interp(B,A,i/16));
draw(interp(C,A,i/16)--interp(C,B,i/16));
}
draw(A--X, dotted);
draw(arc(Z,abs(X - Y),-12,40), Arrow(6));
label("$A$", A, N);
label("$B$", B, SE);
label("$C$", C, SW);
dot(A);
dot(X);
dot(Y);
[/asy]
$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players $bad$ if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$-th player. Prove that \[\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0.\]
[i]Proposed by Sung Yun Kim, South Korea[/i]
The figure shows a game board with $16$ squares. At the start of the game, two cars are placed in different squares. Two players $A$ and $B$ alternately take turns, and A starts. In each turn, the player chooses one of the cars and moves it one or more squares to the right. The left-most car may never overtake or land on the same square as the right-most car. The first player which is unable to move loses.
[img]https://cdn.artofproblemsolving.com/attachments/1/b/8d6f40fac4983d6aa9bd076392c91a6d200f6a.png[/img]
(a) Prove that A can win regardless of how $B$ plays, if the two cars start as shown in the figure.
(b) Determine all starting positions in which $B$ can win regardless of how $A$ plays.
A set of $n$ points in space is given, no three of which are collinear and no four of which are co-planar (on a single plane), and each pair of points is connected by a line segment. Initially, all the line segments are colorless. A positive integer $b$ is given and Alice and Bob play the following game. In each turn Alice colors one segment red and then Bob colors up to $b$ segments blue. This is repeated until there are no more colorless segments left. If Alice colors a red triangle, Alice wins. If there are no more colorless segments and Alice hasn’t succeeded in coloring a red triangle, Bob wins. Neither player is allowed to color over an already colored line segment.
1. Prove that if $b < \sqrt{2n - 2} -\frac32$ , then Alice has a winning strategy.
2. Prove that if $b \ge 2\sqrt{n}$, then Bob has a winning strategy.
A round-robin tournament has six competititors. Each round between two players is equally likely to result in a win for a given player, a loss for that player, or a tie. The results of the tournament are \textit{nice} if for all triples of distinct players $(A, B, C)$,
1. If $A$ beat $B$ and $B$ beat $C$, then $A$ also beat $C$;
2. If $A$ and $B$ tied, then either $C$ beat both $A$ and $B$, or $C$ lost to both $A$ and $B$.
The probability that the results of the tournament are $\textit{nice}$ is $p = \tfrac{m}{n}$, for coprime positive integers $m$ and $n$. Find $m$.
[i]Proposed by Michael Tang[/i]
The vertices of 100-gon (i.e., polygon with 100 sides) are colored alternately white or black. One of the vertices contains a checker. Two players in turn do two things: move the checker into other vertice along the side of 100-gon and then erase some side. The game ends when it is impossible to move the checker. At the end of the game if the checker is in the white vertice then the first player wins. Otherwise the second player wins. Does any of the players have winning strategy? If yes, then who?
[i]Remark.[/i] The answer may depend on initial position of the checker.
A traffic light installed at a main junction of a road, in which you circulate in both directions, it remains red for $30$ s and green for another $30$ s, alternately. You want to install another traffic light on the same road, for a secondary crossing, located $400$ m away from the first, which works with the same period of $1$ min duration. It is wanted that the cars that circulate at $60$ km/h on the road in any of the two senses and that they do not have to stop if there was only the traffic light of the main intersection. They also don't have to stop after installing the secondary crossover. How many seconds can red be on at the secondary traffic light?
Note: It is suggested to reason on a Cartesian representation of the march of the cars, taking an axis of distances and another of times.
The vertices of 100-gon (i.e., polygon with 100 sides) are colored alternately white or black. One of the vertices contains a checker. Two players in turn do two things: move the checker into other vertice along the side of 100-gon and then erase some side. The game ends when it is impossible to move the checker. At the end of the game if the checker is in the white vertice then the first player wins. Otherwise the second player wins. Does any of the players have winning strategy? If yes, then who?
[i]Remark.[/i] The answer may depend on initial position of the checker.
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?
There are $9999$ rods with lengths $1, 2, ..., 9998, 9999$. The players Anja and Bernd alternately remove one of the sticks, with Anja starting. The game ends when there are only three bars left. If from those three bars, a not degenerate triangle can be constructed then Anja wins, otherwise Bernd.
Who has a winning strategy?
Peter wrote $100$ distinct integers on a board. Basil needs to fill the cells of a table $100\times{100}$ with integers so that the sum in each rectangle $1\times{3}$ (either vertical, or horizontal) is equal to one of the numbers written on the board. Find the greatest $n$ such that, regardless of numbers written by Peter, Basil can fill the table so that it would contain each of numbers $(1,2,...,n)$ at least once (and possibly some other integers).
Two children take turns breaking chocolate bar that is 5*10 squares. They can only break the bar using the divisions between squares and can only do 1 break at a time.. The first player that when breaking the chocolate bar breaks off only a single square wins. Is there a winning strategy for any player?
A solitaire game is played on an $m\times n$ rectangular board, using $mn$ markers which are white on one side and black on the other. Initially, each square of the board contains a marker with its white side up, except for one corner square, which contains a marker with its black side up. In each move, one may take away one marker with its black side up, but must then turn over all markers which are in squares having an edge in common with the square of the removed marker. Determine all pairs $(m,n)$ of positive integers such that all markers can be removed from the board.
Alice plays the following game of solitaire on a $20 \times 20$ chessboard.
She begins by placing $100$ pennies, $100$ nickels, $100$ dimes, and $100$ quarters on the board so that each of the $400$ squares contains exactly one coin. She then chooses $59$ of these coins and removes them from the board.
After that, she removes coins, one at a time, subject to the following rules:
- A penny may be removed only if there are four squares of the board adjacent to its square (up, down, left, and right) that are vacant (do not contain coins). Squares “off the board” do not count towards this four: for example, a non-corner square bordering the edge of the board has three adjacent squares, so a penny in such a square cannot be removed under this rule, even if all three adjacent squares are vacant.
- A nickel may be removed only if there are at least three vacant squares adjacent to its square. (And again, “off the board” squares do not count.)
- A dime may be removed only if there are at least two vacant squares adjacent to its square (“off the board” squares do not count).
- A quarter may be removed only if there is at least one vacant square adjacent to its square (“off the board” squares do not count).
Alice wins if she eventually succeeds in removing all the coins. Prove that it is impossiblefor her to win.
In a $k$-player tournament for $k > 1$, every player plays every other player exactly once. Find with proof the smallest value of $k$ such that it is possible that for any two players, there was a third player who beat both of them.
In a box there are $31$, $41$ and $59$ stones coloured, respectively, red, green and blue. Three players,
having t-shirts of these three colours, play the following game. They sequentially make one of two moves:
(I) either remove three stones of one colour from the box,
(II) or replace two stones of different colours by two stones of the third colour.
The game ends when all the stones in the box have the same colour and the winner is the player whose t-shirt
has this colour. Assuming that the players play optimally, is it possible to decide whether the game ends and
who will win, depending on who the starting player is?
Given a positive integer $n\ge 3$, Arándano and Banana play a game. Initially, numbers $1,2,3,\dots,n$ are written on the blackboard. Alternatingly and starting with Arándano, the players erase numbers from the board one at a time, until exactly three numbers remain on the board. Banana wins the game if the last three numbers on the board are the sides of a nondegenerate triangle, and Arándano wins otherwise.
Determine, in terms of $n$, who has a winning strategy.
The numbers $1$ to $500$ are written on a board. Two pupils $A$ and $B$ play the following game: A player in turn deletes one of the numbers from the board. The game is over when only two numbers remain. Player $B$ wins if the sum of the two remaining numbers is divisible by $3,$ otherwise $A$ wins. If $A$ plays first, show that $B$ has a winning strategy.
[b]p1.[/b] Let $f$ be a function such that $f(x + y) = f(x) + f(y)$ for all $x$ and $y$. Assume $f(5) = 9$. Compute $f(2015)$.
[b]p2.[/b] There are six cards, with the numbers $2, 2, 4, 4, 6, 6$ on them. If you pick three cards at random, what is the probability that you can make a triangles whose side lengths are the chosen numbers?
[b]p3. [/b]A train travels from Berkeley to San Francisco under a tunnel of length $10$ kilometers, and then returns to Berkeley using a bridge of length $7$ kilometers. If the train travels at $30$ km/hr underwater and 60 km/hr above water, what is the train’s average speed in km/hr on the round trip?
[b]p4.[/b] Given a string consisting of the characters A, C, G, U, its reverse complement is the string obtained by first reversing the string and then replacing A’s with U’s, C’s with G’s, G’s with C’s, and U’s with A’s. For example, the reverse complement of UAGCAC is GUGCUA. A string is a palindrome if it’s the same as its reverse. A string is called self-conjugate if it’s the same as its reverse complement. For example, UAGGAU is a palindrome and UAGCUA is self-conjugate. How many six letter strings with just the characters A, C, G (no U’s) are either palindromes or self-conjugate?
[b]p5.[/b] A scooter has $2$ wheels, a chair has $6$ wheels, and a spaceship has $11$ wheels. If there are $10$ of these objects, with a total of $50$ wheels, how many chairs are there?
[b]p6.[/b] How many proper subsets of $\{1, 2, 3, 4, 5, 6\}$ are there such that the sum of the elements in the subset equal twice a number in the subset?
[b]p7.[/b] A circle and square share the same center and area. The circle has radius $1$ and intersects the square on one side at points $A$ and $B$. What is the length of $\overline{AB}$ ?
[b]p8. [/b]Inside a circle, chords $AB$ and $CD$ intersect at $P$ in right angles. Given that $AP = 6$, $BP = 12$ and $CD = 15$, find the radius of the circle.
[b]p9.[/b] Steven makes nonstandard checkerboards that have $29$ squares on each side. The checkerboards have a black square in every corner and alternate red and black squares along every row and column. How many black squares are there on such a checkerboard?
[b]p10.[/b] John is organizing a race around a circular track and wants to put $3$ water stations at $9$ possible spots around the track. He doesn’t want any $2$ water stations to be next to each other because that would be inefficient. How many ways are possible?
[b]p11.[/b] In square $ABCD$, point $E$ is chosen such that $CDE$ is an equilateral triangle. Extend $CE$ and $DE$ to $F$ and $G$ on $AB$. Find the ratio of the area of $\vartriangle EFG$ to the area of $\vartriangle CDE$.
[b]p12.[/b] Let $S$ be the number of integers from $2$ to $8462$ (inclusive) which does not contain the digit $1,3,5,7,9$. What is $S$?
[b]p13.[/b] Let x, y be non zero solutions to $x^2 + xy + y^2 = 0$. Find $\frac{x^{2016} + (xy)^{1008} + y^{2016}}{(x + y)^{2016}}$ .
[b]p14.[/b] A chess contest is held among $10$ players in a single round (each of two players will have a match). The winner of each game earns $2$ points while loser earns none, and each of the two players will get $1$ point for a draw. After the contest, none of the $10$ players gets the same score, and the player of the second place gets a score that equals to $4/5$ of the sum of the last $5$ players. What is the score of the second-place player?
[b]p15.[/b] Consider the sequence of positive integers generated by the following formula
$a_1 = 3$, $a_{n+1} = a_n + a^2_n$ for $n = 2, 3, ...$
What is the tens digit of $a_{1007}$?
[b]p16.[/b] Let $(x, y, z)$ be integer solutions to the following system of equations
$x^2z + y^2z + 4xy = 48$
$x^2 + y^2 + xyz = 24$
Find $\sum x + y + z$ where the sum runs over all possible $(x, y, z)$.
[b]p17.[/b] Given that $x + y = a$ and $xy = b$ and $1 \le a, b \le 50$, what is the sum of all a such that $x^4 + y^4 - 2x^2y^2$ is a prime squared?
[b]p18.[/b] In $\vartriangle ABC$, $M$ is the midpoint of $\overline{AB}$, point $N$ is on side $\overline{BC}$. Line segments $\overline{AN}$ and $\overline{CM}$ intersect at $O$. If $AO = 12$, $CO = 6$, and $ON = 4$, what is the length of $OM$?
[b]p19.[/b] Consider the following linear system of equations.
$1 + a + b + c + d = 1$
$16 + 8a + 4b + 2c + d = 2$
$81 + 27a + 9b + 3c + d = 3$
$256 + 64a + 16b + 4c + d = 4$
Find $a - b + c - d$.
[b]p20.[/b] Consider flipping a fair coin $ 8$ times. How many sequences of coin flips are there such that the string HHH never occurs?
PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].
There is a queue of $n{}$ girls on one side of a tennis table, and a queue of $n{}$ boys on the other side. Both the girls and the boys are numbered from $1{}$ to $n{}$ in the order they stand. The first game is played by the girl and the boy with the number $1{}$ and then, after each game, the loser goes to the end of their queue, and the winner remains at the table. After a while, it turned out that each girl played exactly one game with each boy. Prove that if $n{}$ is odd, then a girl and a boy with odd numbers played in the last game.
[i]Proposed by A. Gribalko[/i]