Given a positive integer $n$, determine all functions $f$ from the first $n$ positive integers to the positive integers, satisfying the following two conditions: (1) $\sum_{k=1}^{n}{f(k)}=2n$; and (2) $\sum_{k\in K}{f(k)}=n$ for no subset $K$ of the first $n$ positive integers.
Problem
Source: Romania TST 2016 Day 3 P1
Tags: algebra, number theory
62861
01.11.2017 07:06
I feel like I've seen this before on WOOT practice olympiads, with $n = 50$. Maybe I'm imagining things. Anyways, we just want to characterize the $n$-multisets $\{a_1, \dots, a_n\}$ summing to $2n$ but with no subset summing to $n$. If $n = 1$ then the only possible multiset is $\{2\}$, so consider $n > 1$. Let $s_k = a_1 + \dots + a_k$ for $k = 1, 2, \dots, n$. If two of them, say $s_i, s_j$ with $i < j$, share the same residue modulo $n$, then $a_{i + 1} + \dots + a_j$ is less than $2n$ and is a multiple of $n$, so it is $n$; contradiction. Thus $s_1, \dots, s_n$ form a complete residue system modulo $n$. However, $s_1, \dots, s_n$ must form a complete residue system modulo $n$ for any arrangement of $a_1, \dots, a_n$. Then, it's easy to show that $a_1 \equiv \dots \equiv a_n \equiv r \pmod{n}$ for some $r \in \{0, \dots, n - 1\}$. It's easy to see $r = 0$ is impossible for $n > 1$. Now we consider some cases: If $r = 1$, then $a_1, \dots, a_n \in \{1, n + 1\}$ with sum $2n$; hence, $\{a_1, \dots, a_n\} = \{\underbrace{1, \dots, 1}_{n - 1 \; 1\text{s}}, n + 1\}$. This works. If $r = 2$ and $n \ge 3$, then $a_1, \dots, a_n \ge 2$ with sum $2n$; hence $\{a_1, \dots, a_n\} = \{\underbrace{2, \dots, 2}_{n \; 2\text{s}}\}$. This works when $n$ is odd. If $r = 3$ and $n \ge 4$, then $a_1, \dots, a_n \ge 3$ with sum $2n$, which is impossible. Conclusion: the only such $f$ are the ones whose ranges are a permutation of $\underbrace{1, \dots, 1}_{n - 1 \; 1\text{s}}, n + 1$, or if $n$ is odd, a range of $\underbrace{2, \dots, 2}_{n \; 2\text{s}}$.
tenplusten
01.11.2017 16:42
CantonMathGuy wrote: However, $s_1, \dots, s_n$ must form a complete residue system modulo $n$ for any arrangement of $a_1, \dots, a_n$. Then, it's easy to show that $a_1 \equiv \dots \equiv a_n \equiv r \pmod{n}$ for some $r \in \{0, \dots, n - 1\}$. Can you eloborate , more please?
ThE-dArK-lOrD
01.11.2017 16:49
This problem also appeared on Problems of Number Theory in Mathematical Competitions (Vol. 2 of Mathematical Olympiad Series) page 84-85.
tenplusten
01.11.2017 16:51
Can anyone explain why all of $a_i $'s are congruent modulo $n $?
TLP.39
02.11.2017 13:43
tenplusten wrote: Can anyone explain why all of $a_i $'s are congruent modulo $n $?
Compare the sequence $s_1, \dots, s_n$ when the permutation are $a_{\sigma(1)},a_{\sigma(2)},a_{\sigma(3)},...,a_{\sigma(n)}$ and $a_{\sigma(2)},a_{\sigma(1)},a_{\sigma(3)},...,a_{\sigma(n)}$
hakN
17.07.2021 19:45
We say $x$ cannot be achieved by $Q$ if for any $K \subseteq Q$, $\sum_{k \in K} f(k) \neq x$.
If $f$ satisfies the condition, then any permutation of $f$ also satisfies, so without loss of generality assume $f(1) \leq f(2) \leq \dots \leq f(n)$.
It is clear that $f(n) \leq n + 1$, and when $f(n) = n + 1$, $f(i) = 1$ for all $i \leq n-1$, and this clearly works.
Since $f(n) \neq n$, assume $3\leq f(n) = k \leq n - 1$. Let $S = \{1\leq i \leq n-1 : f(i) = 1\} , T = \{1,2, \dots n - 1\} - S$ and let $x = |S|$.
By averaging, we have $\frac{2n - k - x}{n - 1 - x} \geq 2 \implies x \geq k - 2$. Thus, by condition 2 we must have $k + k - 2 \leq n - 1 \implies k \leq \frac{n+1}{2}$.
Also, equality can be achieved if and only if $1 = f(1) = \dots = f(k-2) , 2 = f(k-1) = \dots = f(n-1) , k=f(n)$ but in that case it is easy to check that condition 2 is not satisfied.(We can take $\frac{n-1}{2}$ of 2's and one 1). Thus, $k < \frac{n+1}{2}$ and $x \geq k - 1$. So, $n - k + 1 > k$.
We have the sums $n - k , n - k - 1 , \dots ,n - 2k + 1 , \dots ,n - k - x$ cannot be achieved by $T$. If $n - k + 1$ can be achieved, then let that subset of $T$ be $K$ which satisfies $\sum_{y \in K} f(y) = n - k + 1$. Clearly, $|K| \geq 2$ since we assumed $f(n)$ is the largest among them. But then, if we remove one element from $K$ and let the new subset be $K'$, we have $n - k - 1 \leq \sum_{y \in K'} f(y) \leq n - 2k + 1$, contradicting the above hypothesis. Now, continuing by induction, we see that $2n - k - x$ is also cannot be achieved by $T$, but $\sum_{y \in T} f(y) = 2n - k - x$, contradiction! So $k \leq 2$, in which case $k = 2$. So we have $f(m) = 2$ for all $m = 1,2, \dots , n$. But that is a solution if and only if $n$ is odd.
Thus if $n$ is odd, the solutions are :($f(i) = n + 1$ for some $1 \leq i \leq n$, and $f(m) = 1 \ \forall m \neq i$) and ($f(m) = 2 \forall m$).
If $n$ is even, the solutions are : $f(i) = n + 1$ for some $1 \leq i \leq n$, and $f(m) = 1 \ \forall m \neq i$.