Suppose that $p$ is a prime number. Find all natural numbers $n$ such that $p|\varphi(n)$ and for all $a$ such that $(a,n)=1$ we have \[ n|a^{\frac{\varphi(n)}{p}}-1 \]

Click for solution For $p|\varphi(n)$, we need that $n$ has a prime divisor $\equiv 1 \mod p$ or $p^2|n$. Let $c(n)$ be the highest order any $a$ coprime to $n$ has $\mod n$. By existence of primitive roots $\mod p^s$ for odd primes $p$, we get that $c(p^s)=\varphi(p^s)$. Also $c(2)=1 , c(4)=2 , c(2^{k+2}) = 2^k$ for $k \geq 1$. Additionally we have $c(ab)=\mathrm{lcm}(c(a),c(b))$ for all $a,b$. What we want is $c(n) \cdot p | \varphi(n)$. Let $n=\prod p_i^{v_i}$ be the prime decomposition of $n$. Then this is equivalent to $p \cdot \mathrm{lcm}_i (\varphi(p_i^{v_i})) | \prod \varphi(p_i^{v_i})$, so we must loose some factor $p$ in the $\mathrm{lcm}$, happening iff $p|\varphi(p_s^{v_s}) , \varphi(p_t^{v_t})$ for different $s,t$, equivalent to that there are two different primes $\equiv 1 \mod p$ dividing $n$ or at least one such prime together with $p^2|n$.

Suppose $n$ coins are available that their mass is unknown. We have a pair of balances and every time we can choose an even number of coins and put half of them on one side of the balance and put another half on the other side, therefore a comparison will be done. Our aim is determining that the mass of all coins is equal or not. Show that at least $n-1$ comparisons are required.

Click for solution Let $x_1,\ldots,x_n$ be the masses of the coins. A comparison tells us whether $x_{a_1}+\ldots+x_{a_k}-(x_{b_1}+\ldots+x_{b_k})=0$ or not for some subset $\{a_i\}\cup\{b_j\}\subset\overline{1,n}$. Suppose we make $n-2$ comparisons. We want to prove that there can be two different situations, one in which all $x_i$ are equal and one in which they are not, which cannot be distinguished by the $n-2$ comparisons. These $n-2$ comparisons give us a homogeneous linear system with $n$ unknowns and $n-2$ equations, so its solution space has dimension $\ge 2$. This means that in addition to the family of solutions given by $x_1=x_2=\ldots=x_n$, it must have other solutions as well, and this is what we wanted.

Suppose $ABC$ is a triangle with $M$ the midpoint of $BC$. Suppose that $AM$ intersects the incircle at $K,L$. We draw parallel line from $K$ and $L$ to $BC$ and name their second intersection point with incircle $X$ and $Y$. Suppose that $AX$ and $AY$ intersect $BC$ at $P$ and $Q$. Prove that $BP=CQ$.

Let $x_1,x_2,\ldots,x_n$ be real numbers. Prove that \[ \sum_{i,j=1}^n |x_i+x_j|\geq n\sum_{i=1}^n |x_i| \]

Click for solution My own solution is rather complicated, but I know there are other solutions that are simpler. Anyway here is my solution: We use induction on $n$. Easily we can verify that if $x_i=0$ for some $i$ then the result can be derived from case $n-1$. Now we will show that if $x_i=-x_j$ for some $i$ and $j$ then the result can be derived from the case $n-2$. First observer a small lemma: Lemma : $|x-y|+|x+y|\geq |x|+|y|$ Proof : By triangle inequality we have $|x-y|+|x+y|\geq 2|x|$ and $|x-y|+|x+y|\geq 2|y|$. Adding these two and dividing by two we get the result. Now suppose that $x_1=-x_2$. Now by lemma we have the following inequalities: \[ |x_1+x_i|+|x_2+x_i|\geq |x_1|+|x_i| (3\leq i\leq n) \] \[ |x_i+x_1|+|x_i+x_2|\geq |x_2|+|x_i| (3\leq i\leq n) \] And we obviously have : \[ |x_1+x_2|=0 , |x_2+x_1|=0 , |x_1+x_1|=2|x_1| , |x_2+x_2|=2|x_2| \] And from the induction hypothesis for $n-2$ we have : \[ \sum_{i,j=3}^n |x_i+x_j|\geq (n-2)\sum_{i=3}^n |x_i| \] By adding all the above inequalities/equalities we have \[ \sum_{i,j=1}^n |x_i+x_j|\geq n\sum_{i=1}^n |x_i| \] which is what we wanted. Now we may assume that no $x_i$ is zero and for no $i,j$ we have $x_i+x_j=0$. Now take the function $f$ to be $\sum_{i,j=1}^n |x_i+x_j|-n\sum_{i=1}^n |x_i|$. Now assume that we add some $x_i$ a small value $\epsilon$. Then some terms in $f$ will increase by $\epsilon$ and some will decrease and some do not change. (Count the term $|x_i+x_i|$ twice) But since we have that no term in $f$ is zero, if rather than increasing $x_i$ by $\epsilon$ we decrease it by $\epsilon$ the terms in $f$ that were increasing will decrease and the ones that were decreasing will increase. So we can either increase $x_i$ by $\epsilon$ or decrease it such that $f$ is not increased (At this point $f$ behaves like a linear function in $x_i$) Also note that value of $\epsilon$ can be increased until one of the terms in $f$ become zero, but then value of $f$ is by the above arguments, non-negative and so we have the results. So assume that $\epsilon$ can be increased to infinity without having any of the terms become zero. But we have this propery for every $x_i$ so there is no $x_i$ between two others, that is there are $a$ of $x_i$s equal to $t$ and $b$ others equal to $s$. ($a+b=n$) Supposing that $|t|<|s|$ ,just increase the $\epsilon$ for all $x_i$s equal to $t$ until we have $|t|=|s|$ or $t=0$. But if $t=0$ then we are done. So assume $t\neq 0$. But then $t=s$, or else we have $t=-s$ which can be derived from the case $x_i+x_j=0$. But then the inequality becomes like this : \[ 2n^2|t|\geq n^2|t| \] which is obviously true.

Let $ABC$ be a triangle such that it's circumcircle radius is equal to the radius of outer inscribed circle with respect to $A$. Suppose that the outer inscribed circle with respect to $A$ touches $BC,AC,AB$ at $M,N,L$. Prove that $O$ (Center of circumcircle) is the orthocenter of $MNL$.

Let $G$ be a tournoment such that it's edges are colored either red or blue. Prove that there exists a vertex of $G$ like $v$ with the property that, for every other vertex $u$ there is a mono-color directed path from $v$ to $u$.

Click for solution We'll prove it by induction. Show that it is true for $n=3$ vertices (trivial) and assume it is true for $n-1$. We'll say that a point that satisfies the given condition is a 'powerful point'. Take $G$ a graph with $n$ vertices. Suppose it has no powerful point. For any vertex $v$, the subgraph $G-v$ has $n-1$ vertices and thus has a powerful point. Then there's a powerful point for $G-v_1$, for $G-v_2$, ..., for $G-v_n$. If two of these were the same, this vertex would be a powerful point for $G$. So they must all be distinct. Thus each vertex has monochromatic paths to exactly $n-2$ other vertices; for each vertex $v$, let $f(v)$ be the vertex it doesn't reach. Consider the sequence $v, f(v), f(f(v)), \ldots$. Eventually some vertex must appear twice. Consider the first time this happens. If this vertex is not $v$ itself, then it must have two distinct 'ancestors' (points that don't reach it), which is absurd (since each vertex has exactly one other vertex that doesn't reach it). Then the first vertex to appear again must be $v$, and we must have a cycle. However, if the cycle contains fewer than $n$ vertices, then there must be a powerful point in this subgraph, which contradicts the fact that each vertex can't reach the next one in the cycle. Thus the cycle has $n$ vertices, that is, it is the whole graph. So order the vertices according to their position in the cycle as $v_1, v_2, \ldots, v_n$, where $f(v_i)=v_{i+1}$. Now we will draw more edges than there originally were. If there's a red path from $v$ to $u$, draw the red edge $vu$; the same goes for blue paths (of course, if the path from $v$ to $u$ is just the edge $vu$, we don't draw it again). Is it possible for two vertices $v, u$ to have both a blue edge $vu$ and a red edge $vu$? No, because then $v$ would reach all the points that $u$ reaches, and in particular $v$ would reach $f(v)$, absurd. It is easy to see, then, that each two vertices $v, u$ are joined by two edges $vu, uv$, each of which can be red or blue, unless $u=f(v)$ or vice-versa. Now, for each vertex $v$, consider the number of red edges $vx$. Clearly it is at most $n-2$ and at least $0$. So there must be two vertices with the same number of red edges $v, u$. Now, if $vu$ is red, then $v$ has at least as many red edges as $u$ does; in particular, for $u$ to have the same number of red edges, $uv$ must be red too. It follows that $vu, uv$ are either both red or both blue. Assume that they're both red (the other case is analogous). Now take $f(v), f(u)$. If $vf(u)$ was red, then there would be a red path $uvf(u)$ from $u$ to $f(u)$, absurd. Then $vf(u)$ is blue. Analogously $uf(v)$ is blue too. Now, if $f(v)v$ were blue, then there would be a blue path $uf(v)v$, from $u$ to $v$; then there would be a blue $uv$ edge too, absurd. So $f(v)v, f(u)u$ are red. Finally, if $f(v)f(u)$ were blue, then there would be a blue path $uf(v)f(u)$ from $u$ to $f(u)$, absurd. So $f(v)f(u), f(u)f(v)$ are red. By induction, $f(f(u)), f(f(v))$ are joined by red edges too, and so on. It follows, also, that $f(f(v))f(v)$ is red, and so on; by induction, $v_{i+1}v_i$ is red for all $i$. But then we can go from any vertex to any other vertex through a red path on the cycle!

We have $n$ points in the plane, no three on a line. We call $k$ of them good if they form a convex polygon and there is no other point in the convex polygon. Suppose that for a fixed $k$ the number of $k$ good points is $c_k$. Show that the following sum is independent of the structure of points and only depends on $n$ : \[ \sum_{i=3}^n (-1)^i c_i \]

Click for solution We call a set of $k$ points bad if this set is not good (guessable definition ). Given $k$, the number of bad $k$-subsets of our initial set $S$ will be denoted by $b_k$. When the $n$ points are vertices of a convex polygon, all subsets are good, so in order to reach the conclusion we need to show that for all possible arrangements of the $n$ points, we have $\sum_{k=3}^n(-1)^kb_k=0$. We can prove this by finding a correspondence among bad sets, pairing each bad set to another bad set whose size has the opposite parity. Suppose our $n$ vertices do not form a convex $n$-gon, and let $A_1,\ldots,A_t$ be the points lying inside the convex hull of $S$. Any bad set which does not contain $A_1$ but whose strict convex hull contains $A_1$ will be paired to the set we get from it by adjoining $A_1$. This way, we have found several pairs of bad sets, and several bad sets have been left unpaired. Among these, pair the ones which do not contain $A_2$ but whose strict convex hull contains $A_2$ to the set we get by adjoining $A_2$, and so on. I hope it's Ok.

Let $n$ be a fixed natural number. a) Find all solutions to the following equation : \[ \sum_{k=1}^n [\frac x{2^k}]=x-1 \] b) Find the number of solutions to the following equation ($m$ is a fixed natural) : \[ \sum_{k=1}^n [\frac x{2^k}]=x-m \]

Click for solution Let $x=\sum_{i=0} a_i2^i , a_i \in \{0,1\}$. \[ \sum_{k=1}^n [\frac x{2^k}]=\sum_{k=1}^n \frac{x}{2^k}-\sum_{k=1}^n\{\frac{x}{2^k}\}=x-\frac{x}{2^n}-\sum_{k=1}^n \{\frac{x}{2^k}\}=x-\frac{x}{2^n}-\sum_{k=1}^{n} \sum_{i=0}^{k-1} a_i2^i=x-\frac{x}{2^n}-\sum_{i=0}^{n-1} a_i(1-\frac{1}{2^{n-i}})=x-[\frac{x}{2^n}]-\sum_{i=0}^{n-1}a_i. \] Therefore equation \[ \sum_{k=1}^n [\frac{x}{2^k}]=x-m \] equavalent to \[ [\frac{x}{2^n}]+\sum_{i=0}^{n-1} a_i =m \] and easy solved.

Let $l,m$ be two parallel lines in the plane. Let $P$ be a fixed point between them. Let $E,F$ be variable points on $l,m$ such that the angle $EPF$ is fixed to a number like $\alpha$ where $0<\alpha<\frac{\pi}2$. (By angle $EPF$ we mean the directed angle) Show that there is another point (not $P$) such that it sees the segment $EF$ with a fixed angle too.

Click for solution Let $n$ be the line through $P$ which is parallel to $\ell,m$, and let $S,T$ be points on $\ell,m$ respectively such that $\angle SPT=2\angle EPF\ (1)$. Finally, let $Q$ be the fourth vertex of the parallelogram $SPTQ$. We'll prove that the point we're looking for is $Q$, and that $\angle EQF=\pi-\angle EPF\ (*)$. Since $QF\mapsto QE$ is a projective transformation, and so is the map sending a line through $Q$ to the line which makes an angle of $\pi-\angle EPF$ with it (such that the two lines have the appropriate orientation, i.e. the same as the orientation of the angle $\angle EPF$), it suffices to check $(*)$ for three particular positions of $E,F$ on $\ell,m$. We'll take the first two to be $E\to\infty,F\to\infty$, where the conclusion is easy to draw, and we'll take the third one such that $PF$ is the angle bisector of $\angle QPT$. Because of $(1),\ PE$ is the angle bisector of $\angle QPS$. Since $SE$ is the external angle bisector of $\angle PSQ$, it means that $E$ is the $P$-excenter of $PSQ$, so $QE$ must be the external angle bisector of $\angle PQS$, and thus orthogonal to the angle bisector of $\angle PQS$. This latter line is parallel to $PF$, the angle bisector of $\angle QPT$, so we have $QE\perp PF$. In the same way we show that $QF\perp PE$, so $Q$ is the orthocenter of $PEF$, and $(*)$ folows.

Let $n$ be a fixed natural number. Find all $n$ tuples of natural pairwise distinct and coprime numbers like $a_1,a_2,\ldots,a_n$ such that for $1\leq i\leq n$ we have \[ a_1+a_2+\ldots+a_n|a_1^i+a_2^i+\ldots+a_n^i \]

Let $ABC$ be an acute angle triangle. Suppose that $D,E,F$ are the feet of perpendicluar lines from $A,B,C$ to $BC,CA,AB$. Let $P,Q,R$ be the feet of perpendicular lines from $A,B,C$ to $EF,FD,DE$. Prove that \[ 2(PQ+QR+RP)\geq DE+EF+FD \]

Suppose we have a simple polygon (that is it does not intersect itself, but not necessarily convex). Show that this polygon has a diameter which is completely inside the polygon and the two arcs it creates on the polygon perimeter (the two arcs have 2 vertices in common) both have at least one third of the vertices of the polygon.