## Traian Lalescu Student contest 2011 Problem 2

Let be a square-free positive integer, and denote by the set of its divisors. Consider , a set with the following properties:

- ;
- ;
- .

Show that there exists a positive integer such that .

Traian Lalescu student contest 2011

**Idea: **Since is square-free, any of its divisors can be identified with a subset of the set of the prime divisors of , denoted . The set is identified with a set of parts of with the following properties:

- ;
- ;
- ;

We can prove that is stable under union also. (try)

If , then we are done. Else there exists such that between and there are no other sets (the order is inclusion). Consider all such sets which can be proved to be disjoint, and their union is . Then the sets in are all unions of , and this can be done in ways.

The argument works just as smoothly if we consider the divisors of ordered by the division operation.