Found problems: 137
KoMaL A Problems 2020/2021, A. 782
Prove that the edges of a simple planar graph can always be oriented such that the outdegree of all vertices is at most three.
[i]UK Competition Problem[/i]
KoMaL A Problems 2022/2023, A. 847
Let $A$ be a given finite set with some of its subsets called pretty. Let a subset be called small, if it's a subset of a pretty set. Let a subset be called big, if it has a pretty subset. (A set can be small and big simultaneously, and a set can be neither small nor big.) Let $a$ denote the number of elements of $A$, and let $p$, $s$ and $b$ denote the number of pretty, small and big sets, respectively. Prove that $2^a\cdot p\le s\cdot b$.
[i]Proposed by András Imolay, Budapest[/i]
KoMaL A Problems 2019/2020, A. 765
Find all functions $f:\mathbb{R}\to\mathbb{R}$ which satisfy the following equality for all $x,y\in\mathbb{R}$ \[f(x)f(y)-f(x-1)-f(y+1)=f(xy)+2x-2y-4.\][i]Proposed by Dániel Dobák, Budapest[/i]
KoMaL A Problems 2019/2020, A.756
Find all functions $f:\mathbb{R}\to\mathbb{R}$ which satisfy the following conditions: $f(x+1)=f(x)+1$ and $f(x^2)=f(x)^2.$
[i]Based on a problem of Romanian Masters of Mathematics[/i]
KoMaL A Problems 2021/2022, A. 823
For positive integers $n$ consider the lattice points $S_n=\{(x,y,z):1\le x\le n, 1\le y\le n, 1\le z\le n, x,y,z\in \mathbb N\}.$ Is it possible to find a positive integer $n$ for which it is possible to choose more than $n\sqrt{n}$ lattice points from $S_n$ such that for any two chosen lattice points at least two of the coordinates of one is strictly greater than the corresponding coordinates of the other?
[I]Proposed by Endre Csóka, Budapest[/i]
KoMaL A Problems 2021/2022, A. 820
Let $ABC$ be an arbitrary triangle. Let the excircle tangent to side $a$ be tangent to lines $AB,BC$ and $CA$ at points $C_a,A_a,$ and $B_a,$ respectively. Similarly, let the excircle tangent to side $b$ be tangent to lines $AB,BC,$ and $CA$ at points $C_b,A_b,$ and $B_b,$ respectively. Finally, let the excircle tangent to side $c$ be tangent to lines $AB,BC,$ and $CA$ at points $C_c,A_c,$ and $B_c,$ respectively. Let $A'$ be the intersection of lines $A_bC_b$ and $A_cB_c.$ Similarly, let $B'$ be the intersection of lines $B_aC_a$ and $A_cB_c,$ and let $C$ be the intersection of lines $B_aC_a$ and $A_bC_b.$ Finally, let the incircle be tangent to sides $a,b,$ and $c$ at points $T_a,T_b,$ and $T_c,$ respectively.
a) Prove that lines $A'A_a,B'B_b,$ and $C'C_c$ are concurrent.
b) Prove that lines $A'T_a, B'T_b,$ and $C'T_c$ are also concurrent, and their point of intersection is on the line defined by the orthocentre and the incentre of triangle $ABC.$
[i]Proposed by Viktor Csaplár, Bátorkeszi and Dániel Hegedűs, Gyöngyös[/i]
KoMaL A Problems 2022/2023, A. 850
Prove that there exists a positive real number $N$ such that for arbitrary real numbers $a,b>N$ it is possible to cover the perimeter of a rectangle with side lengths $a$ and $b$ using non-overlapping unit disks (the unit disks can be tangent to each other).
[i]Submitted by Benedek Váli, Budapest[/i]
KoMaL A Problems 2024/2025, A. 898
Let $n$ be a given positive integer. Ana and Bob play the following game: Ana chooses a polynomial $p$ of degree $n$ with integer coefficients. In each round, Bob can choose a finite set $S$ of positive integers, and Ana responds with a list containing the values of the polynomial $p$ evaluated at the elements of $S$ with multiplicity (sorted in increasing order). Determine, in terms of $n$, the smallest positive integer $k$ such that Bob can always determine the polynomial $p$ in at most $k$ rounds.
[i]Proposed by: Andrei Chirita, Cambridge[/i]
KoMaL A Problems 2022/2023, A. 844
The inscribed circle of triangle $ABC$ is tangent to sides $BC$, $AC$ and $AB$ at points $D$, $E$ and $F$, respectively. Let $E'$ be the reflection of point $E$ across line $DF$, and $F'$ be the reflection of point $F$ across line $DE$. Let line $EF$ intersect the circumcircle of triangle $AE'F'$ at points $X$ and $Y$. Prove that $DX=DY$.
[i]Proposed by Márton Lovas, Budapest[/i]
KoMaL A Problems 2019/2020, A. 773
Let $b\geq 3$ be a positive integer and let $\sigma$ be a nonidentity permutation of the set $\{0,1,\ldots,b-1\}$ such that $\sigma(0)=0.$ The [i]substitution cipher[/i] $C_\sigma$ encrypts every positive integer $n$ by replacing each digit $a$ in the representation of $n$ in base $b$ with $\sigma(a).$ Let $d$ be any positive integer such that $b$ does not divide $d.$ We say that $C_\sigma$ [i]complies[/i] with $d$ if $C_\sigma$ maps every multiple of $d$ onto a multiple of $d,$ and we say that $d$ is [i]cryptic[/i] if there exists some $C_\sigma$ such that $C_\sigma$ complies with $d.$
Let $k$ be any positive integer, and let $p=2^k+1.$
a) Find the greatest power of $2$ that is cryptic in base $2p,$ and prove that there is only one substitution cipher complying with it.
b) Find the greatest power of $p$ that is cryptic in base $2p,$ and prove that there is only one substitution cipher complying with it.
c) Suppose, furthermore, that $p$ is a prime number. Find the greatest cryptic positive integer in base $2p$ and prove that there is only one substitution cipher that complies with it.
[i]Proposed by Nikolai Beluhov, Bulgaria[/i]
KoMaL A Problems 2017/2018, A. 703
Let $n\ge 2$ be an integer. We call an ordered $n$-tuple of integers primitive if the greatest common divisor of its components is $1$. Prove that for every finite set $H$ of primitive $n$-tuples, there exists a non-constant homogenous polynomial $f(x_1,x_2,\ldots,x_n)$ with integer coefficients whose value is $1$ at every $n$-tuple in $H$.
[i]Based on the sixth problem of the 58th IMO, Brazil[/i]
KoMaL A Problems 2020/2021, A. 792
Let $p\geq 3$ be a prime number and $0\leq r\leq p-3.$ Let $x_1,x_2,\ldots,x_{p-1+r}$ be integers satisfying \[\sum_{i=1}^{p-1+r}x_i^k\equiv r \bmod{p}\]for all $1\leq k\leq p-2.$ What are the possible remainders of numbers $x_2,x_2,\ldots,x_{p-1+r}$ modulo $p?$
[i]Proposed by Dávid Matolcsi, Budapest[/i]
KoMaL A Problems 2021/2022, A. 826
An antelope is a chess piece which moves similarly to the knight: two cells $(x_1,y_1)$ and $(x_2,y_2)$ are joined by an antelope move if and only if
\[ \{|x_1-x_2|,|y_1-y_2|\}=\{3,4\}.\]
The numbers from $1$ to $10^{12}$ are placed in the cells of a $10^6\times 10^6$ grid. Let $D$ be the set of all absolute differences of the form $|a-b|$, where $a$ and $b$ are joined by an antelope move in the arrangement. How many arrangements are there such that $D$ contains exactly four elements?
Proposed by [i]Nikolai Beluhov[/i], Bulgaria
KoMaL A Problems 2021/2022, A. 824
An infinite set $S$ of positive numbers is called thick, if in every interval of the form $\left [1/(n+1),1/n\right]$ (where $n$ is an arbitrary positive integer) there is a number which is the difference of two elements from $S$. Does there exist a thick set such that the sum of its elements is finite?
Proposed by [i]Gábor Szűcs[/i], Szikszó
KoMaL A Problems 2021/2022, A. 816
Peter has $2022$ pieces of magnetic railroad cars, which are of two types: some have the front with north and the rear with south magnetic polarity, and some have the rear with north and the rear with south magnetic polarity (on these railroad cars the front and the rear can be distinguished). Peter wants to decide whether there is the same number of both types of cars. He can try to fit together two cars in one try. What is the least number of tries needed?
[i]Proposed by Dömötör Pálvölgyi, Budapest[/i]
KoMaL A Problems 2020/2021, A. 790
Andrew and Barry play the following game: there are two heaps with $a$ and $b$ pebbles, respectively. In the first round Barry chooses a positive integer $k,$ and Andrew takes away $k$ pebbles from one of the two heaps (if $k$ is bigger than the number of pebbles in the heap, he takes away the complete heap). In the second round, the roles are reversed: Andrew chooses a positive integer and Barry takes away the pebbles from one of the two heaps. This goes on, in each round the two players are reversing the roles. The player that takes the last pebble loses the game.
Which player has a winning strategy?
[i]Submitted by András Imolay, Budapest[/i]
KoMaL A Problems 2018/2019, A. 737
$100$ points are given in space such that no four of them lie in the same plane. Consider those convex polyhedra with five vertices that have all vertices from the given set. Prove that the number of such polyhedra is even.
KoMaL A Problems 2020/2021, A. 788
Solve the following system of equations:
$$x+\frac{1}{x^3}=2y,\quad y+\frac{1}{y^3}=2z,\quad z+\frac{1}{z^3}=2w,\quad w+\frac{1}{w^3}=2x.$$
KoMaL A Problems 2024/2025, A. 892
Given two integers, $k$ and $d$ such that $d$ divides $k^3 - 2$. Show that there exists integers $a$, $b$, $c$ satisfying $d = a^3 + 2b^3 + 4c^3 - 6abc$.
[i]Proposed by Csongor Beke and László Bence Simon, Cambridge[/i]
KoMaL A Problems 2023/2024, A. 874
[i]Nyihaha[/i] and [i]Bruhaha[/i] are two neighbouring islands, both having $n$ inhabitants. On island [i]Nyihaha[/i] every inhabitant is either a Knight or a Knave. Knights always tell the truth and Knaves always lie. The inhabitants of island [i]Bruhaha[/i] are normal people, who can choose to tell the truth or lie. When a visitor arrives on any of the two islands, the following ritual is performed: every inhabitant points randomly to another inhabitant (indepently from each other with uniform distribution), and tells "He is a Knight" or "He is a Knave'". On sland [i]Nyihaha[/i], Knights have to tell the truth and Knaves have to lie. On island [i]Bruhaha[/i] every inhabitant tells the truth with probability $1/2$ independently from each other. Sinbad arrives on island [i]Bruhaha[/i], but he does not know whether he is on island [i]Nyihaha[/i] or island [i]Bruhaha[/i]. Let $p_n$ denote the probability that after observing the ritual he can rule out being on island [i]Nyihaha[/i]. Is it true that $p_n\to 1$ if $n\to\infty$?
[i]Proposed by Dávid Matolcsi, Berkeley[/i]
KoMaL A Problems 2019/2020, A. 758
In a quadrilateral $ABCD,$ $AB=BC=DA/\sqrt{2},$ and $\angle ABC$ is a right angle. The midpoint of $BC$ is $E,$ the orthogonal projection of $C$ on $AD$ is $F,$ and the orthogonal projection of $B$ on $CD$ is $G.$ The second intersection point of circle $(BCF)$ (with center $H$) and line $BG$ is $K,$ and the second intersection point of circle $(BCF)$ and line $HK$ is $L.$ The intersection of lines $BL$ and $CF$ is $M.$ The center of the Feurbach circle of triangle $BFM$ is $N.$ Prove that $\angle BNE$ is a right angle.
[i]Proposed by Zsombor Fehér, Cambridge[/i]
KoMaL A Problems 2020/2021, A. 799
For a given quadrilateral $A_1A_2B_1B_2,$ a point $P$ is called [i]phenomenal[/i], if line segments $A_1A_2$ and $B_1B_2$ subtend the same angle at point $P$ (i.e. triangles $PA_1A_2$ and $PB_1B_2$ which can be also also degenerate have equal inner angles at point $P$ disregarding orientation).
Three non-collinear points, $A_1,A_2,$ and $B_1$ are given in the plane. Prove that it is possible to find a disc in the plane such that for every point $B_2$ on the disc, the quadrilateral $A_1A_2B_1B_2$ is convex and it is possible to construct seven distinct phenomenal points (with respect to $A_1A_2B_1B_2$) only using a right ruler.
With a right ruler the following two operations are allowed:
[list=1]
[*]Given two points it is possible to draw the straight line connecting them;
[*]Given a point and a straight line, it is possible to draw the straight line passing through the given point which is perpendicular to the given line.
[/list]
[i]Proposed by Á. Bán-Szabó, Budapest[/i]
KoMaL A Problems 2020/2021, A. 791
A lightbulb is given that emits red, green or blue light and an infinite set $S$ of switches, each with three positions labeled red, green and blue. We know the following:
[list=1]
[*]For every combination of the switches the lighbulb emits a given color.
[*]If all switches are in a position with a given color, the lightbulb emits the same color.
[*]If there are two combinations of the switches where each switch is in a different position, the lightbulb emits a different color for the two combinations.
[/list]
We create the following set $U$ containing some of the subsets of $S$: for each combination of the switches let us observe the color of the lightbulb, and put the set of those switches in $U$ which are in the same position as the color of the lightbulb.
Prove that $U$ is an ultrafilter on $S$. In other words, prove that $U$ satisfies the following conditions:
[list=1]
[*]The empty set is not in $U.$
[*]If two sets are in $U,$ their intersection is also in $U.$
[*]If a set is in $U,$ every subset of $S$ containing it is also in $U.$
[*]Considering a set and its complement in $S,$ exactly one of these sets is contained in $U.$
[/list]
KoMaL A Problems 2023/2024, A. 867
Let $p(x)$ be a monic integer polynomial of degree $n$ that has $n$ real roots, $\alpha_1,\alpha_2,\ldots, \alpha_n$. Let $q(x)$ be an arbitrary integer polynomial that is relatively prime to polynomial $p(x)$. Prove that
\[\sum_{i=1}^n \left|q(\alpha_i)\right|\ge n.\]
[i]Submitted by Dávid Matolcsi, Berkeley[/i]
KoMaL A Problems 2018/2019, A. 749
Given are two polyominos, the first one is an L-shape consisting of three squares, the other one contains at least two squares. Prove that if $n$ and $m$ are coprime then at most one of the $n\times n$ and $m\times m$ boards can be tiled by translated copies of the two polyominos.
[i]Proposed by: András Imolay, Dávid Matolcsi, Ádám Schweitzer and Kristóf Szabó, Budapest[/i]