Problem

Source: 2022 IGMO Christmas Edition #4 International Gamma Mathematical Olympiad

Tags: number theory, number of divisors



Because of inflation, Santa can’t afford buying gifts for all children this year. He decided to divide his ordered list of good children into those who will get a gift and those who won’t. To be as fair as possible, he came up with the following (seemingly random) rule: ”Each child has its own number on my list. If $n$ is a positive integer which satisfies $$\tau (nk) \le k \cdot \tau (n)$$for all positive integers $k \ge 2$, then the $n^{th}$ child from my list will get a gift. ” Characterize all positive integers $n$ such that the $n^{th}$ child from the list gets a gift this year. Note: $\tau (n)$ denotes the number of positive divisors of $n$.