Maths Olympiad Prep

Library / /9 of 9

, 2018

Number theory Difficulty 8.4 Shortlist Prove it Saudi Arabia

Let nn be an even positive integer. We fill in a number on each cell of a rectangle table of nn columns and multiple rows as following:
i. Each row is assigned to some positive integer aa and its cells are filled by 00 or aa (in any order);
ii. The sum of all numbers in each row is nn.
Note that we cannot add any more row to the table such that the conditions (i) and (ii) still hold. Prove that if the number of 00's on the table is odd then the maximum odd number on the table is a perfect square.

Solution

Denote σ(n),τ(n)\sigma(n), \tau(n) as the sum of divisors and number of divisors of nn, respectively.
Consider a row with assigned number is aa, and suppose that there are bb cells on that row are filled by aa then n=abn = a b or aa is a divisor of nn. By condition ii), the number of rows of the table is exactly the number of positive divisors of nn.
Number of nonzero on each row is na\frac{n}{a}, thus the number of zero on each row is nnan - \frac{n}{a}. Number of zero on table is
an(nna)=an(na)=nτ(n)ana=nτ(n)σ(n). \sum_{a \mid n} \left(n - \frac{n}{a}\right) = \sum_{a \mid n} (n - a) = n \cdot \tau(n) - \sum_{a \mid n} a = n \cdot \tau(n) - \sigma(n) .
This number is odd and nn is even which imply that σ(n)\sigma(n) is odd. Put n=2kqn = 2^{k} \cdot q with qq is odd number then qq is also the maximum odd number on the table. The sum of divisor σ(n)\sigma(n) of nn is of form pαnσ(pα)\prod_{p^{\alpha} \| n} \sigma\left(p^{\alpha}\right).
- If p=2p = 2 then σ(2k)\sigma\left(2^{k}\right) is an odd number.
- If p>2p > 2 then σ(pα)=1+p++pα\sigma\left(p^{\alpha}\right) = 1 + p + \cdots + p^{\alpha} must be odd, which implies that α\alpha is even.
From this, we can conclude that all odd prime divisors of nn have even exponent, thus qq is a perfect square.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.