The total number of languages used in KAUST is $n$. For each positive integer $k \le n$, let $A_k$ be the set of all those people in KAUST who can speak at least $k$ languages; and let $B_k$ be the set of all people $P$ in KAUST with the property that, for any $k$ pairwise different languages (used in KAUST), $P$ can speak at least one of these $k$ languages. Prove that (a) If $2k \ge n + 1$ then $A_k \subseteq B_k$ (b) If $2k \le n + 1$ then $A_k \supseteq B_k.$ Nguyễn Duy Thái Sơn

The natural numbers are colored green or blue so that: $\bullet$ The sum of a green and a blue is blue; $\bullet$ The product of a green and a blue is green. How many ways are there to color the natural numbers with these rules, so that $462$ are blue and $2016$ are green?

2000 people are sitting around a round table. Each one of them is either a truth-sayer (who always tells the truth) or a liar (who always lies). Each person said: "At least two of the three people next to me to the right are liars". How many truth-sayers are there in the circle?

Let $n,m$ be positive integers. Let $A_1,A_2,A_3, ... ,A_m$ be sets such that $A_i \subseteq \{1, 2, 3, . . . , n\}$ and $|A_i| = 3$ for all $i$ (i.e. $A_i$ consists of three different positive integers each at most $n$). Suppose for all $i < j$ we have $|A_i \cap A_j | \le 1$ (i.e. $A_i$ and $A_j$ have at most one element in common). (a) Prove that $m \le \frac{n(n-1)}{ 6}$ . (b) Show that for all $n \ge3$ it is possible to have $m \ge \frac{(n-1)(n-2)}{ 6}$ .

Let $n<k$ be two natural numbers and suppose that Sepehr has $n$ chemical elements , $2k$ grams from each , divided arbitrarily in $2k$ cups.Find the smallest number $b$ such that there is always possible for Sepehr to choose $b$ cups , containing at least $2$ grams from each element in total. [i]Proposed by Josef Tkadlec & Morteza Saghafian[/i]

$n$ parallel segments of lengths $a_1 \le a_2 \le a_3 \le ... \le a_n$ were painted to mark an airport atrium. However, the architect decided that the $n$ segments should have equal length. If the cost per meter of extending the lines is equal to the cost of reducing them, how long should the lines be in order to minimize costs?

Some cells of a $10 \times 10$ are colored blue. A set of six cells is called [i]gremista[/i] when the cells are the intersection of three rows and two columns, or two rows and three columns, and are painted blue. Determine the greatest value of $n$ for which it is possible to color $n$ chessboard cells blue such that there is not a [i]gremista[/i] set.

[u]Round 1[/u] [b]p1.[/b] A $\$100$ TV has its price increased by $10\%$. The new price is then decreased by $10\%$. What is the current price of the TV? [b]p2.[/b] If $9w + 8x + 7y = 42$ and $w + 2x + 3y = 8$, then what is the value of $100w + 101x + 102y$? [b]p3.[/b] Find the number of positive factors of $37^3 \cdot 41^3$. [u]Round 2[/u] [b]p4.[/b] Three hoses work together to fill up a pool, and each hose expels water at a constant rate. If it takes the first, second, and third hoses 4, 6, and 12 hours, respectively, to fill up the pool alone, then how long will it take to fill up the pool if all three hoses work together? [b]p5.[/b] A semicircle has radius $1$. A smaller semicircle is inscribed in the larger one such that the two bases are parallel and the arc of the smaller is tangent to the base of the larger. An even smaller semicircle is inscribed in the same manner inside the smaller of the two semicircles, and this procedure continues indefinitely. What is the sum of all of the areas of the semicircles? [b]p6.[/b] Given that $P(x)$ is a quadratic polynomial with $P(1) = 0$, $P(2) = 0$, and $P(0) = 2012$, find $P(-1)$. [u]Round 3[/u] [b]p7.[/b] Darwin has a paper circle. He labels one point on the circumference as $A$. He folds $A$ to every point on the circumference on the circle and undoes it. When he folds $A$ to any point $P$, he makes a blue mark on the point where $\overline{AP}$ and the made crease intersect. If the area of Darwin paper circle is 80, then what is the area of the region surrounded by blue? [b]p8.[/b] Α rectangular wheel of dimensions $6$ feet by $8$ feet rolls for $28$ feet without sliding. What is the total distance traveled by any corner on the rectangle during this roll? [b]p9[/b]. How many times in a $24$-hour period do the minute hand and hour hand of a $12$-hour clock form a right angle? [u]Round 4[/u] The answers in this section all depend on each other. Find smallest possible solution set. [b]p10.[/b] Let B be the answer to problem $11$. Right triangle $ACD$ has a right angle at $C$. Squares $ACEF$ and $ADGH$ are drawn such that points $D$ and $E$ do not coincide and points $E$ and $H$ do not coincide. The midpoints of the sides of $ADGH$ are connected to form a smaller square with area $B.$ If the area of $ACEF$ is also $B$, then find the length $CD$ rounded up to the nearest integer. [b]p11.[/b] Let $C$ be the answer to problem $12$. Find the sum of the digits of $C$. [b]p12.[/b] Let $A$ be the answer to problem $10$. Given that $a_0 = 1$, $a_1 = 2$, and that $a_n = 3a_{n-1 }-a_{n-2}$ for $n \ge 2$, find $a_A$. PS. You should use hide for answers.Rounds 5-8 are [url=https://artofproblemsolving.com/community/c3h3134466p28406321]here [/url] and 9-12 [url=https://artofproblemsolving.com/community/c3h3134489p28406583]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Each of the spots in a $8\times 8$ chessboard is occupied by either a black or white “horse”. At most how many black horses can be on the chessboard so that none of the horses attack more than one black horse? [b]Remark:[/b] A black horse could attack another black horse.

For any two nonnegative integers $n$ and $k$ satisfying $n\geq k$, we define the number $c(n,k)$ as follows: - $c\left(n,0\right)=c\left(n,n\right)=1$ for all $n\geq 0$; - $c\left(n+1,k\right)=2^{k}c\left(n,k\right)+c\left(n,k-1\right)$ for $n\geq k\geq 1$. Prove that $c\left(n,k\right)=c\left(n,n-k\right)$ for all $n\geq k\geq 0$.

We are given 5040 balls in k different colors, where the number of balls of each color is the same. The balls are put into 2520 bags so that each bag contains two balls of different colors. Find the smallest k such that, however the balls are distributed into the bags, we can arrange the bags around a circle so that no two balls of the same color are in two neighboring bags.

In a basketball tournament any two of the $n$ teams $S_1,S_2,...,S_n$ play one match (no draws). Denote by $v_i$ and $p_i$ the number of victories and defeats of team $S_i$ ($i = 1,2,...,n$), respectively. Prove that $v^2_1 +v^2_2 +...+v^2_n = p^2_1 +p^2_2 +...+p^2_n$

Given an infinite sheet of square ruled paper. Some of the squares contain a piece. A move consists of a piece jumping over a piece on a neighbouring square (which shares a side) onto an empty square and removing the piece jumped over. Initially, there are no pieces except in an $m x n$ rectangle ($m, n > 1$) which has a piece on each square. What is the smallest number of pieces that can be left after a series of moves?

Let $n > 3$ be a positive integer. Suppose that $n$ children are arranged in a circle, and $n$ coins are distributed between them (some children may have no coins). At every step, a child with at least 2 coins may give 1 coin to each of their immediate neighbors on the right and left. Determine all initial distributions of the coins from which it is possible that, after a finite number of steps, each child has exactly one coin.

There are eight rooms on the first floor of a hotel, with four rooms on each side of the corridor, symmetrically situated (that is each room is exactly opposite to one other room). Four guests have to be accommodated in four of the eight rooms (that is, one in each) such that no two guests are in adjacent rooms or in opposite rooms. In how many ways can the guests be accommodated?

In a party of $1000$ people, the number of people who have shaken hands with at most $962$ people is less than or equal to $37$. Show that one can find $27$ people in the party who have all shaken hands with each other.

2500 chess kings have to be placed on a $100 \times 100$ chessboard so that [b](i)[/b] no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex); [b](ii)[/b] each row and each column contains exactly 25 kings. Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.) [i]Proposed by Sergei Berlov, Russia[/i]

The Queen of Hearts rules a kingdom with $n$ (distinguishable) cities. Each pair of cities is either connected with a bridge or not connected with a bridge. Each day, the Queen of Hearts visits $2021$ cities. For every pair of cities, if she sees a bridge she gets angry and destroys it; otherwise she feels nice and constructs a bridge between them. We call two configurations of bridges [i]equivalent[/i] if one can be reached from the other after a finite number of days. Show that there is some integer $M$ such that if $n>M$, two configurations are equivalent if both of the following conditions hold: [list] [*] The parity of the total number of bridges is the same in both configurations [*] For every city, the parity of the number of bridges going out of that city is the same in both configurations. [/list]

Let $N$ be the number of ways of distributing $8$ chocolates of different brands among $3$ children such that each child gets at least one chocolate, and no two children get the same number of chocolates. Find the sum of the digits of $N$.

A lottery ticket has $50$ cells into which one must put a permutation of $1, 2, 3, ... , 50$. Any ticket with at least one cell matching the winning permutation wins a prize. How many tickets are needed to be sure of winning a prize?

Consider a $10 \times 10$ grid. On every move, we colour $4$ unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the $4$ squares is previously uncoloured. What is the largest possible number of moves that can be taken to colour the whole grid?

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

$f(n)$ is the least number that there exist a $f(n)-$mino that contains every $n-$mino. Prove that $10000\leq f(1384)\leq960000$. Find some bound for $f(n)$

Let $S$ be the set of all 3-tuples $(a, b, c)$ of positive integers such that $a + b + c = 2013$. Find $$\sum_{(a,b,c)\in S} abc.$$

An arrangement of chips in the squares of $ n\times n$ table is called [i]sparse[/i] if every $ 2\times 2$ square contains at most 3 chips. Serge put chips in some squares of the table (one in a square) and obtained a sparse arrangement. He noted however that if any chip is moved to any free square then the arrangement is no more sparce. For what $ n$ is this possible? [i]Proposed by S. Berlov[/i]