Olympiad problems

2011 QEDMO 9th, 8

Tags: weights , algorithms

There are $256$ lumps of metal that have different weights in pairs. With the help of a beam balance , one may now compare every two lumps. Find the smallest number $m$ such that you can be sure to find the heaviest as well as the lightest lump with the weighing process.

2014 German National Olympiad, 5

Tags: combinatorics , weights , coins

There are $9$ visually indistinguishable coins, and one of them is fake and thus lighter. We are given $3$ indistinguishable balance scales to find the fake coin; however, one of the scales is defective and shows a random result each time. Show that the fake coin can still be found with $4$ weighings.

2021 Romanian Master of Mathematics Shortlist, C2

Tags: RMM Shortlist , graph theory , weights , combinatorics

Fix a positive integer $n$ and a finite graph with at least one edge; the endpoints of each edge are distinct, and any two vertices are joined by at most one edge. Vertices and edges are assigned (not necessarily distinct) numbers in the range from $0$ to $n-1$, one number each. A vertex assignment and an edge assignment are [i]compatible[/i] if the following condition is satisfied at each vertex $v$: The number assigned to $v$ is congruent modulo $n$ to the sum of the numbers assigned to the edges incident to $v$. Fix a vertex assignment and let $N$ be the total number of compatible edge assignments; compatibility refers, of course, to the fixed vertex assignment. Prove that, if $N \neq 0$, then the prime divisors of $N$ are all at most $n$.