Found problems: 137
KoMaL A Problems 2022/2023, A. 849
For real number $r$ let $f(r)$ denote the integer that is the closest to $r$ (if the fractional part of $r$ is $1/2$, let $f(r)$ be $r-1/2$). Let $a>b>c$ rational numbers such that for all integers $n$ the following is true: $f(na)+f(nb)+f(nc)=n$. What can be the values of $a$, $b$ and $c$?
[i]Submitted by Gábor Damásdi, Budapest[/i]
KoMaL A Problems 2020/2021, A. 783
A polyomino is a figure which consists of unit squares joined together by their sides. (A polyomino may contain holes.) Let $n\ge3$ be a positive integer. Consider a grid of unit square cells which extends to infinity in all directions. Find, in terms of $n$, the greatest positive integer $C$ which satisfies the following condition: For every colouring of the cells of the grid in $n$ colours, there is some polyomino within the grid which contains at most $n-1$ colours and whose area is at least $C$.
Proposed by Nikolai Beluhov, Stara Zagora, Bulgaria and Stefan Gerdjikov, Sofia, Bulgaria
KoMaL A Problems 2024/2025, A. 906
Let $\mathcal{V}_c$ denote the infinite parallel ruler with the parallel edges being at distance $c$ from each other. The following construction steps are allowed using ruler $\mathcal V_c$:
[list]
[*] the line through two given points;
[*] line $\ell'$ parallel to a given line $\ell $at distance $c$ (there are two such lines, both of which can be constructed using this step);
[*] for given points $A$ and $B$ with $|AB|\ge c$ two parallel lines at distance $c$ such that one of them passes through $A$, and the other one passes through $B$ (if $|AB|>c$, there exists two such pairs of parallel lines, and both can be constructed using this step).
[/list]
On the perimeter of a circular piece of paper three points are given that form a scalene triangle. Let $n$ be a given positive integer. Prove that based on the three points and $n$ there exists $C>0$ such that for any $0<c\le C$ it is possible to construct $n$ points using only $\mathcal V_c$ on one of the excircles of the triangle.
[i]We are not allowed to draw anything outside our circular paper. We can construct on the boundary of the paper; it is allowed to take the intersection point of a line with the boundary of the paper.[/i]
[i]Proposed by Áron Bán-Szabó[/i]
KoMaL A Problems 2022/2023, A.838
Sets \(X\subset \mathbb{Z}^{+}\) and \(Y\subset \mathbb{Z}^{+}\) are called [i]comradely[/i], if every positive integer \(n\) can be written as \(n=xy\) for some \(x\in X\) and \(y\in Y\). Let \(X(n)\) and \(Y(n)\) denote the number of elements of \(X\) and \(Y\), respectively, among the first \(n\) positive integers.
Let \(f\colon \mathbb{Z}^{+}\to \mathbb{R}^{+}\) be an arbitrary function that goes to infinity. Prove that one can find comradely sets \(X\) and \(Y\) such that \(\dfrac{X(n)}{n}\) and \(\dfrac{Y(n)}{n}\) goes to \(0\), and for all \(\varepsilon>0\) exists \(n \in \mathbb{Z}^+\) such that
\[\frac{\min\big\{X(n), Y(n)\big\}}{f(n)}<\varepsilon. \]
KoMaL A Problems 2020/2021, A. 802
Let $P$ be a given regular $100$-gon. Prove that if we take the union of two polygons that are congruent to $P,$ the ratio of the perimeter and area of the resulting shape cannot be more than the ratio of the perimeter and area of $P.$
KoMaL A Problems 2021/2022, A. 817
Let $ABC$ be a triangle. Let $T$ be the point of tangency of the circumcircle of triangle $ABC$ and the $A$-mixtilinear incircle. The incircle of triangle $ABC$ has center $I$ and touches sides $BC,CA$ and $AB$ at points $D,E$ and $F,$ respectively. Let $N$ be the midpoint of line segment $DF.$ Prove that the circumcircle of triangle $BTN,$ line $TI$ and the perpendicular from $D$ to $EF$ are concurrent.
[i]Proposed by Diaconescu Tashi, Romania[/i]
KoMaL A Problems 2022/2023, A.836
For every \(i \in \mathbb{N}\) let \(A_i\), \(B_i\) and \(C_i\) be three finite and pairwise disjoint subsets of \(\mathbb{N}\). Suppose that for every pairwise disjoint sets \(A\), \(B\) and \( C\) with union \(\mathbb N\) there exists \(i\in \mathbb{N}\) such that \(A_i \subset A\), \(B_i \subset B\) and \(C_i \subset C\). Prove that there also exists a finite \(S\subset \mathbb{N}\) such that for every pairwise disjoint sets \(A\), \(B\) and \(C\) with union $\mathbb N$ there exists \(i\in S\) such that \(A_i \subset A\), \(B_i \subset B\) and \(C_i \subset C\).
[i]Submitted by András Imolay, Budapest[/i]
KoMaL A Problems 2022/2023, A. 840
The incircle of triangle $ABC$ touches the sides in $X$, $Y$ and $Z$. In triangle $XYZ$ the feet of the altitude from $X$ and $Y$ are $X'$ and $Y'$, respectively. Let line $X'Y'$ intersect the circumcircle of triangle $ABC$ at $P$ and $Q$. Prove that points $X$, $Y$, $P$ and $Q$ are concyclic.
Proposed by [i]László Simon[/i], Budapest
KoMaL A Problems 2018/2019, A. 745
A clock hand is attached to every face of a convex polyhedron. Each hand always points towards a neighboring face and every minute, exactly one of the hands turns clockwise to point at the next face. Suppose that the hands on neighboring faces never point towards one another. Show that one of the hands makes only finitely many turns.
The Golden Digits 2024, P3
Let $p$ be a prime number and $\mathcal{A}$ be a finite set of integers, with at least $p^k$ elements. Denote by $N_{\text{even}}$ the number of subsets of $\mathcal{A}$ with even cardinality and sum of elements divisible by $p^k$. Define $N_{\text{odd}}$ similarly. Prove that $N_{\text{even}}\equiv N_{\text{odd}}\bmod{p}.$
KoMaL A Problems 2024/2025, A. 888
Let $n$ be a given positive integer. Find the smallest positive integer $k$ for which the following statement is true: for any given simple connected graph $G$ and minimal cuts $V_1, V_2,\ldots, V_n$, at most $k$ vertices can be chosen with the property that picking any two of the chosen vertices there exists an integer $1\le i\le n$ such that $V_i$ separates the two vertices.
A partition of the vertices of $G$ into two disjoint non-empty sets is called a [i]minimal cut[/i] if the number of edges crossing the partition is minimal.
[i]Proposed by András Imolay, Budapest[/i]
KoMaL A Problems 2024/2025, A. 897
Let $O$ denote the origin and let $\gamma$ be the circle with center $(1,0)$ and radius $1$ in the Cartesian system of coordinates. Let $\lambda$ be a real number from the interval $(0,2)$, and let the line $x=\lambda$ intersect the circle $\gamma$ at points $P$ and $Q$. The lines $OP$ and $OQ$ intersect the line $x=2-\lambda$ at the points $P'$ and $Q'$, respectively. Let $\mathcal G$ denote the locus of such points $P'$ and $Q'$ as $\lambda$ varies over the interval $(0,2)$. Prove that there exist points $R$ and $S$ different from the origin in the plane such that for every $A\in \mathcal G$ there exists a point $A'$ on line $OA$ satisfying
\[ A'R^2=(A'S-OS)^2=A'A\cdot A'O.\]
[i]Proposed by: Áron Bán-Szabó, Budapest[/i]
KoMaL A Problems 2024/2025, A. 889
Let $W,A,B$ be fixed real numbers with $W>0$. Prove that the following statements are equivalent.
[list]
[*] For all $x, y, z\ge 0$ satisfying $x+y\le z+W, x+z\le y+W, y+z\le x+W$ we have $Axyz+B\ge x^2+y^2+z^2$.
[*] $B\ge W^2$ and $AW^3+B\ge 3W^2$.
[/list]
[i]Proposed by Ákos Somogyi, London[/i]
KoMaL A Problems 2024/2025, A. 905
We say that a strictly increasing sequence of positive integers $n_1, n_2,\ldots$ is [i]non-decelerating[/i] if $n_{k+1}-n_k\le n_{k+2}-n_{k+1}$ holds for all positive integers $k$. We say that a strictly increasing sequence $n_1, n_2, \ldots$ is [i]convergence-inducing[/i], if the following statement is true for all real sequences $a_1, a_2, \ldots$: if subsequence $a_{m+n_1}, a_{m+n_2}, \ldots$ is convergent and tends to $0$ for all positive integers $m$, then sequence $a_1, a_2, \ldots$ is also convergent and tends to $0$. Prove that a non-decelerating sequence $n_1, n_2,\ldots$ is convergence-inducing if and only if sequence $n_2-n_1$, $n_3-n_2$, $\ldots$ is bounded from above.
[i]Proposed by András Imolay[/i]
KoMaL A Problems 2023/2024, A. 861
Let $f(x)=x^2-2$ and let $f^{(n)}(x)$ denote the $n$-th iteration of $f$. Let $H=\{x:f^{(100)}(x)\leq -1\}$. Find the length of $H$ (the sum of the lengths of the intervals of $H$).
KoMaL A Problems 2023/2024, A. 872
For every positive integer $k$ let $a_{k,1},a_{k,2},\ldots$ be a sequence of positive integers. For every positive integer $k$ let sequence $\{a_{k+1,i}\}$ be the difference sequence of $\{a_{k,i}\}$, i.e. for all positive integers $k$ and $i$ the following holds: $a_{k,i+1}-a_{k,i}=a_{k+1,i}$. Is it possible that every positive integer appears exactly once among numbers $a_{k,i}$?
[i]Proposed by Dávid Matolcsi, Berkeley[/i]
KoMaL A Problems 2024/2025, A. 893
In a text editor program, initially there is a footprint symbol (L) that we want to multiply. Unfortunately, our computer has been the victim of a hacker attack, and only two functions are working: Copy and Paste, each costing 1 Dürer dollar to use. Using the Copy function, we can select one or more consecutive symbols from the existing ones, and the computer memorizes their number. When using the Paste function, the computer adds as many new footprint symbols to the sequence as were selected in the last Copy. If no Copy has been done yet, Paste cannot be used. Let $D(n)$ denote the minimum number of Dürer dollars required to obtain exactly $n$ footprint symbols. Prove that for any positive integer $k$, there exists a positive integer $N$ such that \[D(N)=D(N+1)+1=D(N+2)=D(N+3)+1=D(N+4)=\ldots=D(N+2k-1)+1=D(N+2k).\]
[i]Based on a problem of the Dürer Competition[/i]
KoMaL A Problems 2022/2023, A. 852
Let $(a_i,b_i)$ be pairwise distinct pairs of positive integers for $1\le i\le n$. Prove that
\[(a_1+a_2+\ldots+a_n)(b_1+b_2+\ldots+b_n)>\frac29 n^3,\]
and show that the statement is sharp, i.e. for an arbitrary $c>\frac29$ it is possible that
\[(a_1+a_2+\ldots+a_n)(b_1+b_2+\ldots+b_n)<cn^3.\]
[i]Submitted by Péter Pál Pach, Budapest, based on an OKTV problem[/i]
KoMaL A Problems 2020/2021, A. 781
We want to construct an isosceles triangle using a compass and a straightedge. We are given two of the following four data: the length of the base of the triangle $(a),$ the length of the leg of the triangle $(b),$ the radius of the inscribed circle $(r),$ and the radius of the circumscribed circle $(R).$ In which of the six possible cases will we definitely be able to construct the triangle?
[i]Proposed by György Rubóczky, Budapest[/i]
KoMaL A Problems 2022/2023, A. 832
Assume that the number of offspring for every man can be $0,1,\ldots, n$ with with probabilities $p_0,p_1,\ldots,p_n$ independently from each other, where $p_0+p_1+\cdots+p_n=1$ and $p_n\neq 0$. (This is the so-called Galton-Watson process.) Which positive integer $n$ and probabilities $p_0,p_1,\ldots,p_n$ will maximize the probability that the offspring of a given man go extinct in exactly the tenth generation?
KoMaL A Problems 2024/2025, A. 904
Let $n$ be a given positive integer. Luca, the lazy flea sits on one of the vertices of a regular $2n$-gon. For each jump, Luca picks an axis of symmetry of the polygon, and reflects herself on the chosen axis of symmetry. Let $P(n)$ denote the number of different ways Luca can make $2n$ jumps such that she returns to her original position in the end, and does not pick the same axis twice. (It is possible that Luca's jump does not change her position, however, it still counts as a jump.)
[b]a)[/b] Find the value of $P(n)$ if $n$ is odd.
[b]b)[/b] Prove that if $n$ is even, then
\[P(n)=(n-1)!\cdot n!\cdot \sum_{d\mid n}\left(\varphi\left(\frac{n}d\right)\binom{2d}{d}\right).\]
[i]Proposed by Péter Csikvári and Kartal Nagy, Budapest[/i]
KoMaL A Problems 2021/2022, A. 829
Let $G$ be a simple graph on $n$ vertices with at least one edge, and let us consider those $S:V(G)\to\mathbb R^{\ge 0}$ weighings of the vertices of the graph for which $\sum_{v\in V(G)} S(v)=1$. Furthermore define
\[f(G)=\max_S\min_{(v,w)\in E(G)}S(v)S(w),\]
where $S$ runs through all possible weighings.
Prove that $f(G)=\frac1{n^2}$ if and only if the vertices of $G$ can be covered with a disjoint union of edges and odd cycles.
($V(G)$ denotes the vertices of graph $G$, $E(G)$ denotes the edges of graph $G$.)
KoMaL A Problems 2023/2024, A. 862
Let $ABCD$ be a cyclic quadrilateral inscribed in circle $\omega$. Let $F_A, F_B, F_C$ and $F_D$ be the midpoints of arcs $AB, BC, CD$ and $DA$ of $\omega$. Let $I_A, I_B, I_C$ and $I_D$ be the incenters of triangles $DAB, ABC, BCD$ and $CDA$, respectively.
Let $\omega_A$ denote the circle that is tangent to $\omega$ at $F_A$ and also tangent to line segment $CD$. Similarly, let $\omega_C$ denote the circle that is tangent to $\omega$ at $F_C$ and tangent to line segment $AB$.
Finally, let $T_B$ denote the second intersection of $\omega$ and circle $F_BI_BI_C$ different from $F_B$, and let $T_D$ denote the second intersection of $\omega$ and circle $F_DI_DI_A$.
Prove that the radical axis of circles $\omega_A$ and $\omega_C$ passes through points $T_B$ and $T_D$.
KoMaL A Problems 2022/2023, A. 841
Find all non-negative integer solutions of the equation $2^a+p^b=n^{p-1}$, where $p$ is a prime number.
Proposed by [i]Máté Weisz[/i], Cambridge
KoMaL A Problems 2019/2020, A. 770
Find all positive integers $n$ such that $n!$ can be written as the product of two Fibonacci numbers.