Found problems: 85335
Consider a $ n\times n $ square grid which is divided into $ n^2 $ unit squares(think of a chess-board). The set of all unit squares intersecting the main diagonal of the square or lying under it is called an $n$-staircase. Find the number of ways in which an $n$-stair case can be partitioned into several rectangles, with sides along the grid lines, having mutually distinct areas.
Karakade has three flash drives of each of the six capacities $1, 2, 4, 8, 16, 32$ gigabytes. She gives each of her $6$ servants three flash drives of different capacities. Prove that either there are two capacities where each servant has at most one of the two capacities, or all servants have flash drives with different sums of capacities.
In a certain magical country, there are banknotes in denominations of $2^0, 2^1, 2^2, \ldots$ UAH. Businessman Victor has to make cash payments to $44$ different companies totaling $44000$ UAH, but he does not remember how much he has to pay to each company. What is the smallest number of banknotes Victor should withdraw from an ATM (totaling exactly $44000$ UAH) to guarantee that he would be able to pay all the companies without leaving any change?
[i]Proposed by Oleksii Masalitin[/i]
Find all functions $f: \mathbb R \to \mathbb R$ such that for all reals $x$ and $y$,
\[f(x+y)+f(x)f(y)=f(xy)+f(x)+f(y).\]
We have a blue triangle. In every move, we divide the blue triangle by angle bisector to $2$ triangles and color one triangle in red. Prove, that after some moves we color more than half of the original triangle in red.
Given coprime positive integers $p,q>1$, call all positive integers that cannot be written as $px+qy$(where $x,y$ are non-negative integers) [i]bad[/i], and define $S(p,q)$ to be the sum of all bad numbers raised to the power of $2019$. Prove that there exists a positive integer $n$, such that for any $p,q$ as described, $(p-1)(q-1)$ divides $nS(p,q)$.
There are $k$ cities in Belarus and $k$ cities in Armenia, between some cities there are non-directed flights. From any Belarusian city there are exactly $n$ flights to Armenian cities, and for every pair of Armenian cities exactly two Belarusian cities have flights to both of the Armenian cities.
a) Prove that from every Armenian city there are exactly $n$ flights to Belarusian cities.
b) Prove that there exists a flight route in which every city is visited at most once and that consists of at least $\lfloor \frac{(n+1)^2}{4} \rfloor$ cities in each of the countries.
[i]D. Gorovoy[/i]
We denote by $S(k)$ the sum of digits of a positive integer number $k$. We say that the positive integer $a$ is $n$-good, if there is a sequence of positive integers $a_0$, $a_1, \dots , a_n$, so that $a_n = a$ and $a_{i + 1} = a_i -S (a_i)$ for all $i = 0, 1,. . . , n-1$.
Is it true that for any positive integer $n$ there exists a positive integer $b$, which is $n$-good, but not $(n + 1)$-good?
A. Antropov
Let $S=\{1,2,3,\cdots,100\}$. Find the maximum value of integer $k$, such that there exist $k$ different nonempty subsets of $S$ satisfying the condition: for any two of the $k$ subsets, if their intersection is nonemply, then the minimal element of their intersection is not equal to the maximal element of either of the two subsets.
Let $a,b,c\ge0$ and $a+b+c\ge3.$ Prove that $a^4+b^3+c^2\ge a^3+b^2+c.$
Julian and Johan are playing a game with an even number of cards, say $2n$ cards, ($n \in Z_{>0}$). Every card is marked with a positive integer. The cards are shuffled and are arranged in a row, in such a way that the numbers are visible. The two players take turns picking cards. During a turn, a player can pick either the rightmost or the leftmost card. Johan is the first player to pick a card (meaning Julian will have to take the last card). Now, a player’s score is the sum of the numbers on the cards that player acquired during the game.
Prove that Johan can always get a score that is at least as high as Julian’s.
Let $S$ be a finite set, and let $F$ be a family of subsets of $S$ such that
a) If $A\subseteq S$, then $A\in F$ if and only if $S\setminus A\notin F$;
b) If $A\subseteq B\subseteq S$ and $B\in F$, then $A\in F$.
Determine if there must exist a function $f:S\to\mathbb{R}$ such that for every $A\subseteq S$, $A\in F$ if and only if
\[\sum_{s\in A}f(s)<\sum_{s\in S\setminus A}f(s).\]
[i]Evan O'Dorney.[/i]
Let $ABCD$ be a cyclie quadrilateral, $\omega$ be it's circumcircle and $M$ be the midpoint of the arc $AB$ of $\omega$ which does not contain the vertices $C$ and $D$. The line that passes through $M$ and the intersection point of segments $AC$ and $BD$, intersects again $\omega$ in $N$. Let $P$ and $Q$ be points in the $CD$ segment such that $\angle AQD = \angle DAP$ and $\angle BPC = \angle CBQ$. Prove that the circumcircle of $NPQ$ and $\omega$ are tangent to each other.
Let $\triangle ABC$ be a triangle with circumcenter $O$ and orthocenter $H$. Let $D$ be a point on the circumcircle of $ABC$ such that $AD \perp BC$. Suppose that $AB = 6, DB = 2$, and the ratio $\tfrac{\text{area}(\triangle ABC)}{\text{area}(\triangle HBC)}=5.$ Then, if $OA$ is the length of the circumradius, then $OA^2$ can be written in the form $\tfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Compute $m + n$.
Let $P(x) \in \mathbb{Z}[x]$ be a polynomial. Determine all polynomials $Q(x) \in \mathbb{Z}[x]$, such that for every positive integer $n$, there exists a polynomial $R_n(x) \in \mathbb{Z}[x]$ satisfies
$$Q(x)^{2n} - 1 = R_n(x)\left(P(x)^{2n} - 1\right).$$
The points $K$ and $N$ lie on the hypotenuse $AB$ of a right triangle $ABC$. Prove that orthocenters the triangles $BCK$ and $ACN$ coincide if and only if $\frac{BN}{AK}=\tan^2 A.$
The two brothers, without waiting for the bus, decided to walk to the next stop. After passing $1/3$ of the way, they looked back and saw a bus approaching the stop. One of the brothers ran backwards, and the other ran forward at the same speed. It turned out that everyone ran to their stop exactly at the moment when the bus approached it. Find the speed of the brothers, if the bus speed is $30$ km / h, neglect the bus stop time.
Let $\alpha$ and $\beta$ be positive rational numbers so that $\alpha+\beta\sqrt{5}$ is a root of some polynomial $x^2+ax+b$ where $a$ and $b$ are integers. What is the smallest possible value of $\alpha\beta$?
A sphere is inscribed in an $n$-angled pyramid. Prove that if we align all side faces of the pyramid with the base plane, flipping them around the corresponding edges of the base, then
(1) all tangent points of these faces to the sphere would coincide with one point, $H$, and
(2) the vertices of the faces would lie on a circle centered at $H$.
Rosa and Sara play with a triangle $ABC$, right at $B$. Rosa begins by marking two interior points of the hypotenuse $AC$, then Sara marks an interior point of the hypotenuse $AC$ different from those of Rosa. Then, from these three points the perpendiculars to the sides $AB$ and $BC$ are drawn, forming the following figure.
[img]https://cdn.artofproblemsolving.com/attachments/9/9/c964bbacc4a5960bee170865cc43902410e504.png[/img]
Sara wins if the area of the shaded surface is equal to the area of the unshaded surface, in other case wins Rosa. Determine who of the two has a winning strategy.
Six gamers play a round-robin tournament where each gamer plays one game against each of the other five gamers. In each game there is one winner and one loser where each player is equally likely to win that game, and the result of each game is independent of the results of the other games. The probability that the tournament will end with exactly one gamer scoring more wins than any other player is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$.
When two distinct digits are randomly chosen in $N=123456789$ and their places are swapped, one gets a new number $N'$ (for example, if 2 and 4 are swapped, then $N'=143256789$). The expected value of $N'$ is equal to $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Compute the remainder when $m+n$ is divided by $10^6$.
[i]Proposed by Yannick Yao[/i]
Two circles are given in the plane, $\Omega$ and inside it $\omega$. The center of $\omega$ is $I$. $P$ is a point moving on $\Omega$. The second intersection of the tangents from $P$ to $\omega$ and circle $\Omega$ are $Q$ and $R.$ The second intersection of circle $IQR$ and lines $PI$, $PQ$ and $PR$ are $J$, $S$ and $T,$ respectively. The reflection of point $J$ across line $ST$ is $K.$
Prove that lines $PK$ are concurrent.
A drawer has $5$ pairs of socks. Three socks are chosen at random. If the probability that there is a pair among the three is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, what is $m+n$?
[i]Author: Ray Li[/i]
Given are two positive integers $k$ and $n$ with $k \le n \le 2k - 1$. Julian has a large stack of rectangular $k \times 1$ tiles. Merlin calls a positive integer $m$ and receives $m$ tiles from Julian to place on an $n \times n$ board. Julian first writes on every tile whether it should be a horizontal or a vertical tile. Tiles may be used the board should not overlap or protrude. What is the largest number $m$ that Merlin can call if he wants to make sure that he has all tiles according to the rule of Julian can put on the plate?