We call a set of squares with sides parallel to the coordinate axes and vertices with integer coordinates friendly if any two of them have exactly two points in common. We consider friendly sets in which each of the squares has sides of length $n$. Determine the largest possible number of squares in such a friendly set.

An $ n \times n$ matrix whose entries come from the set $ S \equal{} \{1, 2, \ldots , 2n \minus{} 1\}$ is called a [i]silver matrix[/i] if, for each $ i \equal{} 1, 2, \ldots , n$, the $ i$-th row and the $ i$-th column together contain all elements of $ S$. Show that: (a) there is no silver matrix for $ n \equal{} 1997$; (b) silver matrices exist for infinitely many values of $ n$.

A set of $61$ coins that look alike is given. Two coins (whose weights are equal) are counterfeit. The other $59$ (genuine) coins also have the same weight, but a different weight from that of the counterfeit coins. However it is not known whether it is the genuine coins or the counterfeit coins which are heavier. How can this question be resolved by three weighings on the one balance? (It is not required to separate the counterfeit coins from the genuine ones.) (D. Fomin, Leningrad)

Suppose that in a certain society, each pair of persons can be classified as either [i]amicable [/i]or [i]hostile[/i]. We shall say that each member of an amicable pair is a [i]friend[/i] of the other, and each member of a hostile pair is a [i]foe[/i] of the other. Suppose that the society has $\, n \,$ persons and $\, q \,$ amicable pairs, and that for every set of three persons, at least one pair is hostile. Prove that there is at least one member of the society whose foes include $\, q(1 - 4q/n^2) \,$ or fewer amicable pairs.

Let $E$ to be an infinite set of congruent ellipses in the plane, and $r$ a fixed line. It is known that each line parallel to $r$ intersects at least one ellipse belonging to $E$. Prove that there exist infinitely many triples of ellipses belonging to $E$, such that there exists a line that intersect the triple of ellipses.

The king have revised the chess-board $8\times 8$ having visited all the fields once only and returned to the starting point. When his trajectory was drawn (the centres of the squares were connected with the straight lines), a closed broken line without self-intersections appeared. a) Give an example that the king could make $28$ steps parallel the sides of the board only. b) Prove that he could not make less than $28$ such a steps. c) What is the maximal and minimal length of the broken line if the side of a field is $1$?

Ten pirates find a chest filled with golden and silver coins. There are twice as many silver coins in the chest as there are golden. They divide the golden coins in such a way that the difference of the numbers of coins given to any two of the pirates is not divisible by $10.$ Prove that they cannot divide the silver coins in the same way.

Determine all positive integers $a$ and $b$ such that each square on the $a\times b$ board can be colored red, blue, or green such that each red square has exactly one blue neighbor and one green neighbor, each blue square has exactly one red and one green neighbor and each green square has exactly one red and one blue neighbor. Clarification: Two squares are neighbors if they have a common side.

$f,g$ are two permutations of set $X=\{1,\dots,n\}$. We say $f,g$ have common points iff there is a $k\in X$ that $f(k)=g(k)$. a) If $m>\frac{n}{2}$, prove that there are $m$ permutations $f_{1},f_{2},\dots,f_{m}$ from $X$ that for each permutation $f\in X$, there is an index $i$ that $f,f_{i}$ have common points. b) Prove that if $m\leq\frac{n}{2}$, we can not find permutations $f_{1},f_{2},\dots,f_{m}$ satisfying the above condition.

Students in a school are arranged in an order that when you count from left to right, there will be $n$ students in the first row, $n-1$ students in the second row, $n - 2$ students in the third row,... until there is one student in the $n$th row. All the students face to the first row. For example, here is an arrangement for $n = 5$, where each $*$ represents one student: $*$ $* *$ $* * *$ $* * * *$ $* * * * *$ (first row) Each student will pick one of two following statement (except the student standing at the beginning of the row): i) The guy before me is telling the truth, while the guy standing next to him on the left is lying. ii) The guy before me is lying, while the guy standing next to him on the left is telling the truth. For $n = 2015$, find the maximum number of students telling the truth. (A student is lying if what he said is not true. Otherwise, he is telling the truth.)

There are direct routes from every city of a certain country to every other city. The prices are known in advance. Two tourists (they do not necessary start from one city) have decided to visit all the cities, using only direct travel lines. The first always chooses the cheapest ticket to the city, he has never been before (if there are several -- he chooses arbitrary destination among the cheapests). The second -- the most expensive (they do not return to the first city). Prove that the first will spend not more money for the tickets, than the second.

a) The vertex $A_1$ of the regular $12$-gon (dodecagon) $A_1A_2...A_{12}$ is marked with "$-$" and all the rest $--$ with "$+$". You are allowed to change the sign simultaneously in the $6$ vertices in succession. Prove that is impossible to obtain dodecagon with $A_2$ marked with "$-$" and the rest of the vertices $--$ with "$+$". b) Prove the same statement if it is allowed to change the signs not in six, but in four vertices in succession. c) Prove the same statement if it is allowed to change the signs in three vertices in succession.

Let $k$ and $m$ be positive integers. For a positive integer $n$, let $f(n)$ be the number of integer sequences $x_1,\,\ldots,\,x_k,\,y_1,\,\ldots,\,y_m,\,z$ satisfying $1\leq x_1\leq\cdots\leq x_k\leq z\leq n$ and $1\leq y_1\leq\cdots\leq y_m\leq z\leq n$. Show that $f(n)$ can be expressed as a polynomial in $n$ with nonnegative coefficients.

[u]Round 5[/u] [b]5.1.[/b] Quadrilateral $ABCD$ is such that $\angle ABC = \angle ADC = 90^o$ , $\angle BAD = 150^o$ , $AD = 3$, and $AB = \sqrt3$. The area of $ABCD$ can be expressed as $p\sqrt{q}$ for positive integers $p, q$ where $q$ is not divisible by the square of any prime. Find $p + q$. [b]5.2.[/b] Neetin wants to gamble, so his friend Akshay describes a game to him. The game will consist of three dice: a $100$-sided one with the numbers $1$ to $100$, a tetrahedral one with the numbers $1$ to $4$, and a normal $6$-sided die. If Neetin rolls numbers with a product that is divisible by $21$, he wins. Otherwise, he pays Akshay $100$ dollars. The number of dollars that Akshay must pay Neetin for a win in order to make this game fair is $a/b$ for relatively prime positive integers $a, b$. Find $a + b$. (Fair means the expected net gain is $0$. ) [b]5.3.[/b] What is the sum of the fourth powers of the roots of the polynomial $P(x) = x^2 + 2x + 3$? [u]Round 6[/u] [b]6.1.[/b] Consider the set $S = \{1, 2, 3, 4,..., 25\}$. How many ordered $n$-tuples $S_1 = (a_1, a_2, a_3,..., a_n)$ of pairwise distinct ai exist such that $a_i \in S$ and $i^2 | a_i$ for all $1 \le i \le n$? [b]6.2.[/b] How many ways are there to place $2$ identical rooks and $ 1$ queen on a $ 4 \times 4$ chessboard such that no piece attacks another piece? (A queen can move diagonally, vertically or horizontally and a rook can move vertically or horizontally) [b]6.3.[/b] Let $L$ be an ordered list $\ell_1$, $\ell_2$, $...$, $\ell_{36}$ of consecutive positive integers who all have the sum of their digits not divisible by $11$. It is given that $\ell_1$ is the least element of $L$. Find the least possible value of $\ell_1$. [u]Round 7[/u] [b]7.1.[/b] Spencer, Candice, and Heather love to play cards, but they especially love the highest cards in the deck - the face cards (jacks, queens, and kings). They also each have a unique favorite suit: Spencer’s favorite suit is spades, Candice’s favorite suit is clubs, and Heather’s favorite suit is hearts. A dealer pulls out the $9$ face cards from every suit except the diamonds and wants to deal them out to the $3$ friends. How many ways can he do this so that none of the $3$ friends will see a single card that is part of their favorite suit? [b]7.2.[/b] Suppose a sequence of integers satisfies the recurrence $a_{n+3} = 7a_{n+2} - 14a_{n+1} + 8a_n$. If $a_0 = 4$, $a_1 = 9$, and $a_2 = 25$, find $a_{16}$. Your answer will be in the form $2^a + 2^b + c$, where $2^a < a_{16} < 2^{a+1}$ and $b$ is as large as possible. Find $a + b + c$. [b]7.3.[/b] Parallel lines $\ell_1$ and $\ell_2$ are $1$ unit apart. Unit square $WXYZ$ lies in the same plane with vertex $W$ on $\ell_1$. Line $\ell_2$ intersects segments $YX$ and $YZ$ at points $U$ and $O$, respectively. Given $UO =\frac{9}{10}$, the inradius of $\vartriangle YOU$ can be expressed as $\frac{m}{n}$ for relatively prime positive integers $m, n$. Find $m + n$. [u]Round 8[/u] [b]8.[/b] Let $A$ be the number of contestants who participated in at least one of the three rounds of the 2020 ABMC April contest. Let $B$ be the number of times the letter b appears in the Accuracy Round. Let $M$ be the number of people who submitted both the speed and accuracy rounds before 2:00 PM EST. Further, let $C$ be the number of times the letter c appears in the Speed Round. Estimate $$A \cdot B + M \cdot C.$$Your answer will be scored according to the following formula, where $X$ is the correct answer and $I$ is your input. $$max \left\{ 0, \left\lceil min \left\{13 - \frac{|I-X|}{0.05 |I|}, 13 - \frac{|I-X|}{0.05 |I-2X|} \right\} \right\rceil \right\}$$ PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h2766239p24226402]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Three people, Pranav, Sumith, and Jacklyn, are attending a fair. Every time a person enters or exits, the groundskeeper writes their name down in chronological order. If each person enters and exits the fairgrounds exactly once, in how many ways can the groundskeeper write down their names?

We are given two positive integers $p$ and $q$. Step by step, a rope of length $1$ is cut into smaller pieces as follows: In each step all the currently longest pieces are cut into two pieces with the ratio $p:q$ at the same time. After an unknown number of such operations, the currently longest pieces have the length $x$. Determine in terms of $x$ the number $a(x)$ of different lengths of pieces of rope existing at that time.

In a football tournament $2n$ teams play in a round. Every round consists of $n$ pairs of teams that haven’t played with each other yet. Every round’s schedule is determined before the round is held. Find the minimal positive integer $k$ such that the following situation is possible: after $k$ rounds it’s impossible to schedule the next round.

$6$ musicians gathered at a chamber music festival. At each scheduled concert, some of the musicians played while the others listened as members of the audience. What is the least number of such concerts which would need to be scheduled so that every $2$ musicians each must play for the other in some concert?

Three balloon vendors each offer two types of balloons - one offers red & blue, one offers blue & yellow, and one offers yellow & red. I like each vendor the same, so I must buy $7$ balloons from each. How many different possible triples $(x,y,z)$ are there such that I could buy $x$ blue, $y$ yellow, and $z$ red balloons?

Given $3n$ cards, each of them will be written with a number from the following sequence: $$2, 3, ..., n, n + 1, n + 3, n + 4, ..., 2n + 1, 2n + 2, 2n + 4, ..., 3n + 3$$ with each number used exactly once. Then every card is arranged from left to right in random order. Determine the probability such that for every $i$ with $1\le i \le 3n$, the number written on the $i$-th card, counted from the left, is greater than or equal to $i$.

Consider positive integers $a<b$ and the set $C\subset\{a,a+1,a+2,\dots ,b-2,b-1,b\}$. Suppose $C$ has more than $\frac{b-a+1}{2}$ elements. Prove that there are two elements $x,y\in C$ that satisfy $x+y=a+b$. [i] (From "Radu Păun" contest, Radu Miculescu)[/i]

Let $ABCD$ be a unit square. For any interior points $M,N$ such that the line $MN$ does not contain a vertex of the square, we denote by $s(M,N)$ the least area of the triangles having their vertices in the set of points $\{ A,B,C,D,M,N\}$. Find the least number $k$ such that $s(M,N)\le k$, for all points $M,N$. [i]Dinu Șerbănescu[/i]

In the country of Muilejistan, there exists a network of roads connecting all its cities. The network has the particular property that for any two cities, there is a unique path without backtracking (i.e., a path where the traveler never returns along the same road). The longest possible path between two cities is 600 kilometers. For instance, the path from the city of Mlar to the city of Nlar is 600 kilometers. Similarly, the path from the city of Klar to the city of Glar is also 600 kilometers. 1. If Jalim departs from Mlar towards Nlar at noon and Kalim departs from Klar towards Glar also at noon, both traveling at the same speed, prove that they meet at some point on their journey. 2. If the distance in kilometers between any two cities is an integer, prove that the distance from Glar to Mlar is even.

Let $G$ be the complete graph on $2015$ vertices. Each edge of $G$ is dyed red, blue or white. For a subset $V$ of vertices of $G$, and a pair of vertices $(u,v)$, define \[ L(u,v) = \{ u,v \} \cup \{ w | w \in V \ni \triangle{uvw} \text{ has exactly 2 red sides} \}\]Prove that, for any choice of $V$, there exist at least $120$ distinct values of $L(u,v)$.

The professor tells Peter the product of two positive integers and Sam their sum. At first, nobody of them knows the number of the other. One of them says: [i]You can't possibly guess my number[/i]. Then the other says: [i]You are wrong, the number is 136[/i]. Which number did the professor tell them respectively? Give reasons for your claim.