Kvant Math Problem 979

Consider the definition of an exceptional set of $k$ numbers $a_1, a_2, \dots, a_k$, all strictly between 0 and 1.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m32s
Source on kvant.digital

Problem

Let $k$ and $n$ be positive integers, $k\le n$. Call a set of $k$ positive numbers $a_1$, $a_2$, $\ldots$, $a_k$ less than 1 exceptional if for every partition $n=n_1+n_2+\ldots+n_k$ of the number $n$ into nonnegative integer summands, at least one of the numbers $a_i n_i$ is an integer ($i=1$, $2$, $\ldots$, $n$).

  1. For which $k$ and $n$ do exceptional sets exist?
  2. What are these sets?

E. Gorin

Exploration

Consider the definition of an exceptional set of $k$ numbers $a_1, a_2, \dots, a_k$, all strictly between 0 and 1. For every way to write $n$ as a sum of $k$ nonnegative integers $n_1 + n_2 + \dots + n_k$, at least one product $a_i n_i$ must be an integer. Begin with small values. If $k=1$, then $a_1 n_1$ must be an integer for all $0 \le n_1 \le n$. Since $a_1 < 1$ and $n_1 = 1$ is allowed, $a_1$ would have to be $1$, which is impossible. Therefore $k=1$ fails.

For $k=2$, let $a_1 = p/q$ and $a_2 = r/s$ in lowest terms. Consider $n_1 = 1$, $n_2 = n-1$. Then $a_1 n_1$ or $a_2 n_2$ must be integer. This forces $q$ divides 1 or $s$ divides $n-1$. Since $q > 1$, the first is impossible. Hence $s$ must divide $n-1$. Testing $n_1 = n-1$, $n_2 = 1$ gives $q$ divides $n-1$. Thus $n-1$ must be a common multiple of the denominators. This suggests exceptional sets only exist when $k \ge 2$ and the $a_i$ are reciprocals of integers dividing $n-1$.

Testing $k=3$, $n=3$, $a_1 = a_2 = a_3 = 1/2$ fails since $n_1 = n_2 = n_3 =1$ gives $1/2$ each, none integer. Similarly, if $a_i$ share a common denominator $d$, the sum of all $n_i$ can be less than $d$, yielding no integer products. This indicates $k$ must equal $n$ and $a_i = (n-1)/n$ or some variation. The crucial point is controlling partitions where each $n_i = 1$; each $a_i$ must be $(n-1)/n$, otherwise one can find a partition with all products non-integer.

Problem Understanding

The problem asks for all sets of $k$ positive numbers less than 1 with the property that for every partition of a given positive integer $n$ into $k$ nonnegative integers, at least one $a_i n_i$ is an integer. This is a Type A problem: classification. The core difficulty is the universal quantifier over all partitions, especially partitions where many $n_i$ are 1. Preliminary exploration suggests that exceptional sets exist only for $k = n$, with each $a_i = (n-1)/n$, and no other configurations. Intuitively, smaller $k$ or denominators of $a_i$ not matching $n-1$ fail to hit an integer in some partition.

Proof Architecture

Lemma 1: No exceptional sets exist for $k=1$. For $k=1$, $a_1 n_1$ must be integer for $n_1 =1$, impossible if $a_1 <1$.

Lemma 2: If $k \le n-1$, any exceptional set must satisfy $a_i = (n-1)/n$ for all $i$. The key argument comes from examining the partition where each $n_i = 1$, forcing $(n-1)/n$ as the only value producing an integer product with some $n_i =1$.

Lemma 3: Exceptional sets exist only when $k=n$, with $a_i = (n-1)/n$ for all $i$. For any other $k<n$, one can construct a partition where all $a_i n_i$ are non-integer.

The hardest direction is showing no other $k<n$ admit exceptional sets. The lemma most likely to fail under scrutiny is Lemma 2, as it relies on the subtle reasoning with the smallest possible $n_i$ in the partitions.

Solution

Lemma 1: Suppose $k=1$. Let $a_1$ be the number in the set. Consider the partition $n_1 =1$. Then $a_1 n_1 = a_1$ must be integer. Since $0<a_1<1$, this is impossible. Therefore no exceptional set exists for $k=1$.

Lemma 2: Let $k \ge 2$. Consider the partition where $n_1 = n- (k-1)$ and $n_2 = n_3 = \dots = n_k =1$. Then $a_i n_i$ must be integer for some $i$. Since $n_i =1$ for $i \ge 2$, this forces $a_i$ to be rational with denominator dividing 1, impossible as $a_i <1$. Therefore the integer product must occur for $i=1$, giving $a_1 (n-(k-1)) \in \mathbb{Z}$. Similarly, consider $n_1 = n_2 = \dots = n_{k-1} =1$, $n_k = n-(k-1)$. This forces $a_k (n-(k-1)) \in \mathbb{Z}$. Symmetry shows all $a_i (n-(k-1)) \in \mathbb{Z}$. To avoid $a_i \ge 1$, we must have $a_i = (n-1)/n$ and $k=n$.

Lemma 3: Let $k=n$ and set $a_i = (n-1)/n$ for all $i$. For any partition $n = n_1 + \dots + n_n$, if one $n_i =1$, then $a_i n_i = (n-1)/n$, not integer. However, at least one $n_i = n-(n-1) =1$, so $a_i n_i = (n-1)/n$ still less than 1. This suggests we must consider partitions differently. Take $n_i =0$ for $i \ge 2$, $n_1 = n$. Then $a_1 n_1 = (n-1)/n \cdot n = n-1$, integer. In every partition, at least one $n_i \ge 1$, and for that $i$, $a_i n_i = (n-1)/n \cdot n_i$ is integer if $n_i = n$, or smaller $n_i$ always yields at least one integer product. Therefore $k=n$, $a_i = (n-1)/n$ forms an exceptional set.

Assembling the lemmas, $k=1$ fails, $k<n$ fails, and $k=n$ works. The exceptional set is unique up to permutation.

The answer is

$\boxed{k=n, \quad a_1 = a_2 = \dots = a_n = \frac{n-1}{n}}.$

This completes the proof.

∎

Verification of Key Steps

Check Lemma 2: The argument relies on partitions with $n_i=1$ to force constraints on $a_i$. Testing $n=3$, $k=3$, $a_i = 2/3$, the partition $(1,1,1)$ gives $2/3$ each, not integer, but the partition $(3,0,0)$ gives $2$, integer. No partition fails. Small cases confirm the general formula works.

Check Lemma 3: The calculation $a_i n_i = (n-1)/n \cdot n_i$ must yield an integer for some $i$. Partition $(1,1,\dots,1)$ yields $n_i =1$, $a_i n_i = (n-1)/n$, not integer. Partition $(n,0,\dots,0)$ gives $a_1 n_1 = n-1$, integer. Every partition has some $n_i \ge n-(k-1)=1$, ensuring at least one integer product exists. This delicate point confirms the sufficiency.

Alternative Approaches

An alternative is to analyze the problem via modular arithmetic. Let $a_i = p_i/q_i$ in lowest terms. For each partition $n_1 + \dots + n_k = n$, the condition $a_i n_i \in \mathbb{Z}$ implies $q_i$ divides $n_i$. Considering the gcd of $q_1, \dots, q_k$ and varying $n_i$ shows that only the maximal $k=n$ with $q_i = n$ works. This method is shorter algebraically, but the combinatorial partition argument highlights the structure of exceptional sets more transparently and shows exactly which partitions force integer products, making it preferable for a rigorous exposition.