[ Pairing and grouping; bijections ] [ Proof by contradiction ]

There is a set of natural numbers (it is known that there are at least seven numbers), and the sum of any seven of them is less than 15, while the sum of all numbers in the set is 100. What is the smallest number of numbers that can be in the set?
A set of 50 numbers, each equal to 2, satisfies the condition.

If the set contains no more than 49 numbers, then they can be divided into 7 groups such that each group contains 7 or fewer numbers. According to the condition, the sum of the numbers in each group is less than 15, that is, no more than 14. Therefore, the sum of the numbers in all seven groups is no more than \(7 \cdot 14 = 98\), which is less than 100. Contradiction.

## Answer

\section*{[ Fundamental Theorem of Arithmetic. Factorization into Primes ]

| Problem 34993 Topics: | Partitions into pairs and groups; bijections | ] Difficulty: 3 |
| ---: | :--- | :---: | :--- |
| [ | Classical combinatorics (miscellaneous) | ] Classes: $8,9,10$ |
| [ | Set theory (miscellaneous) | ] |

Prove that an odd number, which is the product of \(n\) distinct prime factors, can be represented as the difference of squares of two natural numbers in exactly \(2^{n-1}\) different ways.

## Hint

\(2^{n-1}\) is the number of ways to partition a set of \(n\) prime factors into two subsets.

## Solution

Let \(m = p_1 p_2 \ldots p_n\), where \(p_1, p_2, \ldots, p_n\) are distinct odd prime numbers. We will solve the equation \(x^2 - y^2 = m\) in natural numbers. This equation can be rewritten as \((x - y)(x + y) = p_1 p_2 \ldots p_n\), from which it follows that the factor \(x - y\) is the product of some (possibly none, in which case \(x - y = 1\)) numbers from the set \(p_1, p_2, \ldots, p_n\), and the factor \(x + y\) is the product of the remaining numbers from this set. The factor \(x - y\) corresponds to the smaller product. Thus, each solution \((x, y)\) corresponds to a partition of the set of \(n\) numbers into two subsets.

Conversely, let there be some partition of the numbers \(p_1, p_2, \ldots, p_n\) into two subsets. Denote by \(t\) and \(s\) (\(t < s\)) the products of the numbers in these subsets (\(t \neq s\), since the numbers \(p_1, p_2, \ldots, p_n\) are distinct). Then there exists a unique pair of natural numbers \((x, y) = \left(\frac{s + t}{2}, \frac{s - t}{2}\right)\) such that \(x - y = t\) and \(x + y = s\) (\(x\) and \(y\) are natural numbers because \(t\) and \(s\) are odd).

Thus, the number of representations of \(m\) as the difference of squares of two natural numbers is equal to the number of ways to partition a set of \(n\) elements into two subsets, which is \(2^{n-1}\) (half the number of \(2^n\) all subsets). Send a comment

## Problem