Let $ n \geq 2$ be an integer, let $ S$ be a set of $ n$ elements, and let $ A_i , \; 1\leq i \leq m$, be distinct subsets of $ S$ of size at least $ 2$ such that \[ A_i \cap A_j \not\equal{} \emptyset, A_i \cap A_k \not\equal{} \emptyset, A_j \cap A_k \not\equal{} \emptyset, \;\textrm{imply}\ \;A_i \cap A_j \cap A_k \not\equal{} \emptyset \ .\] Show that $ m \leq 2^{n\minus{}1}\minus{}1$. [i]P. Erdos[/i]

In town $ A,$ there are $ n$ girls and $ n$ boys, and each girl knows each boy. In town $ B,$ there are $ n$ girls $ g_1, g_2, \ldots, g_n$ and $ 2n \minus{} 1$ boys $ b_1, b_2, \ldots, b_{2n\minus{}1}.$ The girl $ g_i,$ $ i \equal{} 1, 2, \ldots, n,$ knows the boys $ b_1, b_2, \ldots, b_{2i\minus{}1},$ and no others. For all $ r \equal{} 1, 2, \ldots, n,$ denote by $ A(r),B(r)$ the number of different ways in which $ r$ girls from town $ A,$ respectively town $ B,$ can dance with $ r$ boys from their own town, forming $ r$ pairs, each girl with a boy she knows. Prove that $ A(r) \equal{} B(r)$ for each $ r \equal{} 1, 2, \ldots, n.$

Suppose we are given a $19\times19$ chessboard (a table with $19^2$ squares) and remove the central square. Is it possible to tile the remaining $19^2-1=360$ squares with $4\times1$ and $1\times4$ rectangles? (So that each of the $360$ squares is covered by exactly one rectangle.) Justify your answer.

The plan of a Martian underground is represented by a closed selfintersecting curve, with at most one self-intersection at each point. Prove that a tunnel for such a plan may be constructed in such a way that the train passes consecutively over and under the intersecting parts of the tunnel.

All $10$-digit numbers consisting of digits $1, 2$ and $3$ are written one under the other. Each number has one more digit added to the right. $1$, $2$ or $3$, and it turned out that to the number $111. . . 11$ added $1$ to the number $ 222. . . 22$ was assigned $2$, and the number $333. . . 33$ was assigned $3$. It is known that any two numbers that differ in all ten digits have different digits assigned to them. Prove that the assigned column of numbers matches with one of the ten columns written earlier.

How many distinct arrangements are possible for wearing five different rings in the five fingers of the right hand? (We can wear multiple rings in one finger) [list=1] [*] $\frac{10!}{5!}$ [*] $5^5$ [*] $\frac{9!}{4!}$ [*] None of these [/list]

Two vertices of a cube are $A,O$ such that $AO$ is the diagonal of one its faces. A $n-$run is a sequence of $n+1$ vertices of the cube such that each $2$ consecutive vertices in the sequence are $2$ ends of one side of the cube. Is the $1386-$runs from $O$ to itself less than $1386-$runs from $O$ to $A$ or more than it?

$2019$ point grasshoppers sit on a line. At each move one of the grasshoppers jumps over another one and lands at the point the same distance away from it. Jumping only to the right, the grasshoppers are able to position themselves so that some two of them are exactly $1$ mm apart. Prove that the grasshoppers can achieve the same, jumping only to the left and starting from the initial position. (Sergey Dorichenko)

Suppose we have a necklace of $n$ beads. Each bead is labeled with an integer and the sum of all these labels is $n - 1$. Prove that we can cut the necklace to form a string, whose consecutive labels $x_1,x_2,...,x_n$ satisfy $\sum_{i=1}^{k} x_i \le k - 1$ for any $k = 1,...,n$

Let $ S$ be the set of all odd positive integers less than $ 30m$ which are not multiples of $ 5$, where $ m$ is a given positive integer. Find the smallest positive integer $ k$ such that each $ k$-element subset of $ S$ contains two distinct numbers, one of which divides the other.

There are $n$ lamps $L_1, L_2, \dots, L_n$ arranged in a circle in that order. At any given time, each lamp is either [i]on[/i] or [i]off[/i]. Every second, each lamp undergoes a change according to the following rule: (a) For each lamp $L_i$, if $L_{i-1}, L_i, L_{i+1}$ have the same state in the previous second, then $L_i$ is [i]off[/i] right now. (Indices taken mod $n$.) (b) Otherwise, $L_i$ is [i]on[/i] right now. Initially, all the lamps are [i]off[/i], except for $L_1$ which is [i]on[/i]. Prove that for infinitely many integers $n$ all the lamps will be [i]off[/i] eventually, after a finite amount of time.

Suppose you are given $n$ blocks, each of which weighs an integral number of pounds, but less than $n$ pounds. Suppose also that the total weight of the $n$ blocks is less than $2n$ pounds. Prove that the blocks can be divided into two groups, one of which weighs exactly $n$ pounds.

Consolidated Megacorp is planning to send a salesperson to Elbonia who needs to visit every town there. It is possible to travel between any two towns of Elbonia directly either by barge or by mule cart (the same type of travel is available in either direction, and these are the only types of travel available). Show that it is possible to choose a starting town so that the salesperson can complete a round trip visiting each town exactly once and returning to her starting point, while changing the type of transportation used at most one time (this is desirable, since it’s hard to arrange for the merchandise to be transferred from barge to cart or vice versa).

A fixed number of people are dividing an inheritance among themselves. An heir will be called poor if he gets less than $\$99$ and rich if he gets more than $\$10 000$ (some heirs may be neither rich nor poor). The total inheritance and the number of heirs are such that the total income of the rich heirs will be no less than that of the poor ones no matter how the inheritance is divided. Prove that the total income of the rich heirs is no less than $100$ times that of the poor ones. (F Nazarov)

Weights of $1$ g, $2$ g,$ ...$ , $200$ g are placed on the two pans of a balance such that on each pan there are $100$ weights and the balance is in equilibrium. Prove that one can swap $50$ weights from one pan with $50$ weights from the other pan such that the balance remains in equilibrium. Kvant Magazine

Sofia has $5$ pieces of paper on a table. He takes some of the pieces, cuts each one into $5$ little pieces, and puts them back on the table. She repeats this procedure several times until she gets tired. Could Sofia end up with $2010$ pieces on the table?

In an $n\times n$ array all the fields are colored with a different color. In one move one can choose a row, move all the fields one place to the right, and move the last field (from the right) to the leftmost field of the row; or one can choose a column, move all the fields one place downwards, and move the field at the bottom of the column to the top field of the same column. For what values of $n$ is it possible to reach any arrangement of the $n^2$ fields using these kinds of steps? [i]Proposed by Ádám Schweitzer[/i]

Let $a_1$, $a_2$ ,..., $a_{99}$ be a sequence of digits from the set ${0,...,9}$ such that if for some $n$ ∈ $N$, $a_n = 1$, then $a_{n+1} \ne 2$, and if $a_n = 3$ then $a_{n+1} \ne 4$. Prove that there exist indices $k,l$ ∈ ${1,...,98}$ such that $a_k = a_l$ and $a_{k+1} = a_{l+1}$.

A $1\times 1\times 1$ cube is placed on an $8\times 8$ chessboard so that its bottom face coincides with a square of the chessboard. The cube rolls over a bottom edge so that the adjacent face now lands on the chessboard. In this way, the cube rolls around the chessboard, landing on each square at least once. Is it possible that a particular face of the cube never lands on the chessboard?

An ordered quadruple of numbers is called [i]ten-esque[/i] if it is composed of 4 nonnegative integers whose sum is equal to $10$. Ana chooses a ten-esque quadruple $(a_1, a_2, a_3, a_4)$ and Banana tries to guess it. At each stage Banana offers a ten-esque quadtruple $(x_1,x_2,x_3,x_4)$ and Ana tells her the value of \[|a_1-x_1|+|a_2-x_2|+|a_3-x_3|+|a_4-x_4|\] How many guesses are needed for Banana to figure out the quadruple Ana chose?

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]

p1. The pattern $ABCCCDDDDABBCCCDDDDABBCCCDDDD...$ repeats to infinity. Which letter ranks in place $2533$ ? p2. Prove that if $a > 2$ and $b > 3$ then $ab + 6 > 3a + 2b$. p3. Given a rectangle $ABCD$ with size $16$ cm $\times 25$ cm, $EBFG$ is kite, and the length of $AE = 5$ cm. Determine the length of $EF$. [img]https://cdn.artofproblemsolving.com/attachments/2/e/885af838bcf1392eb02e2764f31ae83cb84b78.png[/img] p4. Consider the following series of statements. It is known that $x = 1$. Since $x = 1$ then $x^2 = 1$. So $x^2 = x$. As a result, $x^2 - 1 = x- 1$ $(x -1) (x + 1) = (x - 1) \cdot 1$ Using the rule out, we get $x + 1 = 1$ $1 + 1 = 1$ $2 = 1$ The question. a. If $2 = 1$, then every natural number must be equal to $ 1$. Prove it. b. The result of $2 = 1$ is something that is impossible. Of course there's something wrong in the argument above? Where is the fault? Why is that you think wrong? p5. To calculate $\sqrt{(1998)(1996)(1994)(1992)+16}$ . someone does it in a simple way as follows: $2000^2-2 \times 5\times 2000 + 5^2 - 5$? Is the way that person can justified? Why? p6. To attract customers, a fast food restaurant give gift coupons to everyone who buys food at the restaurant with a value of more than $25,000$ Rp.. Behind every coupon is written one of the following numbers: $9$, $12$, $42$, $57$, $69$, $21$, 15, $75$, $24$ and $81$. Successful shoppers collect coupons with the sum of the numbers behind the coupon is equal to 100 will be rewarded in the form of TV $21''$. If the restaurant owner provides as much as $10$ $21''$ TV pieces, how many should be handed over to the the customer? p7. Given is the shape of the image below. [img]https://cdn.artofproblemsolving.com/attachments/4/6/5511d3fb67c039ca83f7987a0c90c652b94107.png[/img] The centers of circles $B$, $C$, $D$, and $E$ are placed on the diameter of circle $A$ and the diameter of circle $B$ is the same as the radius of circle $A$. Circles $C$, $D$, and $E$ are equal and the pairs are tangent externally such that the sum of the lengths of the diameters of the three circles is the same with the radius of the circle $A$. What is the ratio of the circumference of the circle $A$ with the sum of the circumferences of circles $B$, $C$, $D$, and $E$? p8. It is known that $a + b + c = 0$. Prove that $a^3 + b^3 + c^3 = 3abc$.

Find all integers $ n $ $(n\geq2)$ with the property: for every $ n $ distinct disks in a plane with at least a common point one of the disks contains the center of another disk.

Let C be the number of ways to arrange the letters of the word CATALYSIS, T be the number of ways to arrange the letters of the word TRANSPORT, S be the number of ways to arrange the letters of the word STRUCTURE, and M be the number of ways to arrange the letters of the word MOTION. What is $\frac{C - T + S}{M}$ ?

Suppose that integers are given $m <n $. Consider a spreadsheet of size $n \times n $, whose cells arbitrarily record all integers from $1 $ to ${{n} ^ {2}} $. Each row of the table is colored in yellow $m$ the largest elements. Similarly, the blue colors the $m$ of the largest elements in each column. Find the smallest number of cells that are colored yellow and blue at a time