Browse · MathNet
PrintMathematica competitions in Croatia
Croatia counting and probability
Problem
We say that two cells of the table are friendly if they have at least one common vertex. Into each cell of the table a positive integer less than or equal to is written, so that the numbers in friendly cells are relatively prime. Prove that some number appears in the table at least times.
(St. Petersburg olympiad 2001)
(St. Petersburg olympiad 2001)
Solution
Let's divide the given table into smaller squares . In each of these squares there is at most one even number and at most one number divisible by . Hence, at most numbers in the table are divisible by or . At least numbers remain, and each of them is equal to , or . By the box principle, at least one of these numbers appears at least times.
Techniques
Pigeonhole principleGreatest common divisors (gcd)