Olympiad problems

2013 Princeton University Math Competition, 3

Tags: inequalities , evan orz , 1434 , xooks , i lost the game , otis

A graph consists of a set of vertices, some of which are connected by (undirected) edges. A [i]star[/i] of a graph is a set of edges with a common endpoint. A [i]matching[/i] of a graph is a set of edges such that no two have a common endpoint. Show that if the number of edges of a graph $G$ is larger than $2(k-1)^2$, then $G$ contains a matching of size $k$ or a star of size $k$.

2013 USA TSTST, 5

Tags: goofy , Ahhhh , induction , combinatorics , number theory , evan orz

Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$.

2024 Turkey Team Selection Test, 5

Tags: geometry , Olympiad Geometry , Complex numbers geometry , orthocenter , Centroid , evan orz

In a scalene triangle $ABC$, $H$ is the orthocenter, and $G$ is the centroid. Let $A_b$ and $A_c$ be points on $AB$ and $AC$, respectively, such that $B$, $C$, $A_b$, $A_c$ are cyclic, and the points $A_b$, $A_c$, $H$ are collinear. $O_a$ is the circumcenter of the triangle $AA_bA_c$. $O_b$ and $O_c$ are defined similarly. Prove that the centroid of the triangle $O_aO_bO_c$ lies on the line $HG$.

2023 European Mathematical Cup, 4

Tags: EMC 2023 , 2023 , functional equation , function , Ivan Novak orz , evan orz

Let $f\colon\mathbb{N}\rightarrow\mathbb{N}$ be a function such that for all positive integers $x$ and $y$, the number $f(x)+y$ is a perfect square if and only if $x+f(y)$ is a perfect square. Prove that $f$ is injective. [i]Remark.[/i] A function $f\colon\mathbb{N}\rightarrow\mathbb{N}$ is injective if for all pairs $(x,y)$ of distinct positive integers, $f(x)\neq f(y)$ holds. [i]Ivan Novak[/i]