Olympiad problems

KoMaL A Problems 2022/2023, A. 842

Tags: combinatorics , komal

$n$ people live in a town, and they are members of some clubs (residents can be members of more than one club). No matter how we choose some (but at least one) clubs, there is a resident of the town who is the member of an odd number of the chosen clubs. Prove that the number of clubs is at most $n$. [i]Proposed by Dömötör Pálvölgyi, Budapest[/i]

KoMaL A Problems 2019/2020, A. 771

Tags: geometry , komal

Let $\omega$ denote the incircle of triangle $ABC,$ which is tangent to side $BC$ at point $D.$ Let $G$ denote the second intersection of line $AD$ and circle $\omega.$ The tangent to $\omega$ at point $G$ intersects sides $AB$ and $AC$ at points $E$ and $F$ respectively. The circumscribed circle of $DEF$ intersects $\omega$ at points $D$ and $M.$ The circumscribed circle of $BCG$ intersects $\omega$ at points $G$ and $N.$ Prove that lines $AD$ and $MN$ are parallel. [i]Proposed by Ágoston Győrffy, Remeteszőlős[/i]

KoMaL A Problems 2024/2025, A. 887

Tags: combinatorial geometry , geometry , grid , komal

A non self-intersecting polygon is given in a Cartesian coordinate system such that its perimeter contains no lattice points, and its vertices have no integer coordinates. A point is called semi-integer if exactly one of its coordinates is an integer. Let $P_1, P_2,\ldots, P_k$ denote the semi-integer points on the perimeter of the polygon. Let ni denote the floor of the non-integer coordinate of $P_i$. Prove that integers $n_1,n_2,\ldots ,n_k$ can be divided into two groups with the same sum. [i]Proposed by Áron Bán-Szabó, Budapest[/i]

KoMaL A Problems 2022/2023, A. 845

Tags: geometry , komal

The incircle of triangle $ABC$ is tangent to sides $BC$, $AC$, and $AB$ at points $D$, $E$ and $F$, respectively. Let $A'$ denote the point of the incircle for which circle $(A'BC)$ is tangent to the incircle. Define points $B'$ and $C'$ similarly. Prove that lines $A'D$, $BE'$, and $CF'$ are concurrent. [i]Proposed by Áron Bán-Szabó, Budapest[/i]

KoMaL A Problems 2018/2019, A. 746

Tags: number theory , congruence , komal

Let $p$ be a prime number. How many solutions does the congruence $x^2+y^2+z^2+1\equiv 0\pmod{p}$ have among the modulo $p$ remainder classes? [i]Proposed by: Zoltán Gyenes, Budapest[/i]

KoMaL A Problems 2021/2022, A. 804

Tags: combinatorics , komal

There is a city with $n$ citizens. The city wants to buy [i]sceptervirus[/i] tests with which it is possible to analyze the samples of several people at the same time. The result of a test can be the following: [list] [*][i]Virus positive[/i]: there is at least one currently infected person among the people whose samples were analyzed, and none of them were healed from an earlier infection. [*][i]Antibody positive[/i]: there is at least one person who was healed from an earlier infection among the people whose samples were analyzed, and none of them are infected now. [*][i]Neutral[/i]: either all of the people whose samples were analyzed are not infected, or there is at least one currently infected person and one person who was healed from an earlier infection. (Viruses and antibodies in samples completely neutralize each other.) [/list] What is the smallest number of tests to buy if we would like to know if the sceptervirus is present now or it has been present earlier? (The samples are taken from the people at the same time. The people are either infected now, have been infected earlier, or haven't contacted the virus yet.) [i]Proposed by Csongor Beke, Cambridge[/i]

KoMaL A Problems 2021/2022, A. 807

Tags: combinatorics , graph theory , spanning tree , komal

Let $n>1$ be a given integer. Let $G$ be a finite simple graph with the property that each of its edges is contained in at most $n$ cycles. Prove that the chromatic number of the graph is at most $n+1$.

KoMaL A Problems 2017/2018, A. 721

Tags: inequalities , algebra , komal

Let $n\ge 2$ be a positive integer, and suppose $a_1,a_2,\cdots ,a_n$ are positive real numbers whose sum is $1$ and whose squares add up to $S$. Prove that if $b_i=\tfrac{a^2_i}{S} \;(i=1,\cdots ,n)$, then for every $r>0$, we have $$\sum_{i=1}^n \frac{a_i}{{(1-a_i)}^r}\le \sum_{i=1}^n \frac{b_i}{{(1-b_i)}^r}.$$

KoMaL A Problems 2023/2024, A. 864

Tags: geometry , komal

Let $ABC$ be a triangle and $O$ be its circumcenter. Let $D$, $E$ and $F$ be the respective tangent points of the incircle of $\triangle ABC$, and sides $BC$, $CA$ and $AB$. Let $M$ and $N$ be the respective midpoints of sides $AB$ and $AC$. Let $M'$ and $N'$ be the respective reflections of points $M$ and $N$ across lines $DE$ and $DF$. Let lines $CM'$ and $BN'$ intersect lines $DE$ and $DF$ at points $H$ and $J$, respectively. Prove that the points $H$, $J$ and $O$ are collinear. [i]Proposed by Luu Dong, Vietnam[/i]

KoMaL A Problems 2019/2020, A. 779

Tags: geometry , Tangents , circles , incenter , concurrent , reflection , komal

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.

KoMaL A Problems 2019/2020, A. 768

Tags: geometry , combinatorics , komal

Let $S$ be a shape in the plane which is obtained as a union of finitely many unit squares. Prove that the ratio of the perimeter and the area of $S$ is at most $8$.

KoMaL A Problems 2023/2024, A. 863

Tags: number theory , Analytic Number Theory , komal

Let $n\ge 2$ be a given integer. Find the greatest value of $N$, for which the following is true: there are infinitely many ways to find $N$ consecutive integers such that none of them has a divisor greater than $1$ that is a perfect $n^{\mathrm{th}}$ power. [i]Proposed by Péter Pál Pach, Budapest[/i]

KoMaL A Problems 2022/2023, A. 833

Tags: combinatorics , lattice points , komal

Some lattice points in the Cartesian coordinate system are colored red, the rest of the lattice points are colored blue. Such a coloring is called [i]finitely universal[/i], if for any finite, non-empty $A\subset \mathbb Z$ there exists $k\in\mathbb Z$ such that the point $(x,k)$ is colored red if and only if $x\in A$. $a)$ Does there exist a finitely universal coloring such that each row has finitely many lattice points colored red, each row is colored differently, and the set of lattice points colored red is connected? $b)$ Does there exist a finitely universal coloring such that each row has a finite number of lattice points colored red, and both the set of lattice points colored red and the set of lattice points colored blue are connected? A set $H$ of lattice points is called [i]connected[/i] if, for any $x,y\in H$, there exists a path along the grid lines that passes only through lattice points in $H$ and connects $x$ to $y$. [i]Submitted by Anett Kocsis, Budapest[/i]

KoMaL A Problems 2021/2022, A. 828

Tags: geometry , komal

Triangle $ABC$ has incenter $I$ and excircles $\Omega_A$, $\Omega_B$, and $\Omega_C$. Let $\ell_A$ be the line through the feet of the tangents from $I$ to $\Omega_A$, and define lines $\ell_B$ and $\ell_C$ similarly. Prove that the orthocenter of the triangle formed by lines $\ell_A$, $\ell_B$, and $\ell_C$ coincides with the Nagel point of triangle $ABC$. (The Nagel point of triangle $ABC$ is the intersection of segments $AT_A$, $BT_B$, and $CT_C$, where $T_A$ is the tangency point of $\Omega_A$ with side $BC$, and points $T_B$ and $T_C$ are defined similarly.) Proposed by [i]Nikolai Beluhov[/i], Bulgaria

KoMaL A Problems 2024/2025, A. 907

Tags: komal , combinatorics

$2025$ light bulbs are operated by some switches. Each switch works on a subset of the light bulbs. When we use a switch, all the light bulbs in the subset change their state: bulbs that were on turn off, and bulbs that were off turn on. We know that every light bulb is operated by at least one of the switches. Initially, all lamps were off. Find the biggest number $k$ for which we can surely turn on at least $k$ light bulbs. [i]Based on an OKTV problem[/i]

KoMaL A Problems 2022/2023, A. 830

Tags: number theory , komal

For $H\subset \mathbb Z$ and $n\in\mathbb Z$ let $h_n$ denote the number of finite subsets of $H$ in which the sum of the elements is $n$. Determine whether there exists $H\subset \mathbb Z$ for which $0\notin H$ and $h_n$ is a finite even number for every $n\in\mathbb{Z}$. (The sum of the elements of the empty set is $0$.) [i]Proposed by Csongor Beke, Cambridge[/i]

KoMaL A Problems 2017/2018, A. 706

Tags: komal , function equation , function , algebra

Find all positive integer $k$s for which such $f$ exists and unique: $f(mn)=f(n)f(m)$ for $n, m \in \mathbb{Z^+}$ $f^{n^k}(n)=n$ for all $n \in \mathbb{Z^+}$ for which $f^x (n)$ means the n times operation of function $f$(i.e. $f(f(...f(n))...)$)

KoMaL A Problems 2021/2022, A. 827

Tags: combinatorics , komal

Let $n>1$ be a given integer. In a deck of cards the cards are of $n$ different suites and $n$ different values, and for each pair of a suite and a value there is exactly one such card. We shuffle the deck and distribute the cards among $n$ players giving each player $n$ cards. The players' goal is to choose a way to sit down around a round table so that they will be able to do the following: the first player puts down an arbitrary card, and then each consecutive player puts down a card that has a different suite and different value compared to the previous card that was put down on the table. For which $n$ is it possible that the cards were distributed in such a way that the players cannot achieve their goal? (The players work together, and they can see each other's cards.) Proposed by [i]Anett Kocsis[/i], Budapest

2016 Indonesia TST, 4

Tags: combinatorics , komal

The Hawking Space Agency operates $n-1$ space flights between the $n$ habitable planets of the Local Galaxy Cluster. Each flight has a fixed price which is the same in both directions, and we know that using these flights, we can travel from any habitable planet to any habitable planet. In the headquarters of the Agency, there is a clearly visible board on a wall, with a portrait, containing all the pairs of different habitable planets with the total price of the cheapest possible sequence of flights connecting them. Suppose that these prices are precisely $1,2, ... , \binom{n}{2}$ monetary units in some order. prove that $n$ or $n-2$ is a square number.

KoMaL A Problems 2019/2020, A. 777

Tags: combinatorics , komal , planar graph , graph theory

A finite graph $G(V,E)$ on $n$ points is drawn in the plane. For an edge $e$ of the graph, let $\chi(e)$ denote the number of edges that cross over edge $e$. Prove that \[\sum_{e\in E}\frac{1}{\chi(e)+1}\leq 3n-6.\][i]Proposed by Dömötör Pálvölgyi, Budapest[/i]

KoMaL A Problems 2021/2022, A. 812

Tags: komal , game , winning strategy , combinatorics

Two players play the following game: there are two heaps of tokens, and they take turns to pick some tokens from them. The winner of the game is the player who takes away the last token. If the number of tokens in the two heaps are $A$ and $B$ at a given moment, the player whose turn it is can take away a number of tokens that is a multiple of $A$ or a multiple of $B$ from one of the heaps. Find those pair of integers $(k,n)$ for which the second player has a winning strategy, if the initial number of tokens is $k$ in the first heap and $n$ in the second heap. [i]Proposed by Dömötör Pálvölgyi, Budapest[/i]

KoMaL A Problems 2020/2021, A. 798

Tags: combinatorics , probability , komal , expected value

Let $0<p<1$ be given. Initially, we have $n$ coins, all of which have probability $p$ of landing on heads, and probability $1-p$ of landing on tails (the results of the tosses are independent of each other). In each round, we toss our coins and remove those that result in heads. We keep repeating this until all our coins are removed. Let $k_n$ denote the expected number of rounds that are needed to get rid of all the coins. Prove that there exists $c>0$ for which the following inequality holds for all $n>0$ \[c\bigg(1+\frac{1}{2}+\cdots+\frac{1}{n}\bigg)<k_n<1+c\bigg(1+\frac{1}{2}+\cdots+\frac{1}{n}\bigg).\]

KoMaL A Problems 2024/2025, A. 901

Tags: geometry , geometric transformation , komal

Let $A'B'C'$ denote the reflection of scalene and acute triangle $ABC$ across its Euler-line. Let $P$ be an arbitrary point of the nine-point circle of $ABC$. For every point $X$, let $p(X)$ denote the reflection of $X$ across $P$. [b]a)[/b] Let $e_{AB}$ denote the line connecting the orthogonal projection of $A$ to line $BB'$ and the orthogonal projection of $B$ to line $AA'$. Lines $e_{BC}$ and $e_{CA}$ are defined analogously. Prove that these three lines are concurrent (and denote their intersection by $K$). [b]b)[/b] Prove that there are two choices of $P$ such that lines $Ap(A')$, $Bp(B')$ and $Cp(C')$ are concurrent, and the four points $p(A)p(A')\cap BC$, $p(B)p(B')\cap CA$, $p(C)p(C')\cap AB$, and $K$ are collinear. [i]Proposed by Áron Bán-Szabó, Budapest[/i]

KoMaL A Problems 2017/2018, A. 702

Tags: geometry , inequalities , optimization , geometric inequality , komal

Fix a triangle $ABC$. We say that triangle $XYZ$ is elegant if $X$ lies on segment $BC$, $Y$ lies on segment $CA$, $Z$ lies on segment $AB$, and $XYZ$ is similar to $ABC$ (i.e., $\angle A=\angle X, \angle B=\angle Y, \angle C=\angle Z $). Of all the elegant triangles, which one has the smallest perimeter?

KoMaL A Problems 2022/2023, A. 843

Tags: number theory , komal

Let $N$ be the set of those positive integers $n$ for which $n\mid k^k-1$ implies $n\mid k-1$ for every positive integer $k$. Prove that if $n_1,n_2\in N$, then their greatest common divisor is also in $N$.