Skip to main content
OlympiadHQ

Browse · MathNet

Print

Mathematica 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)
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)