For a positive integer $n$, a sum-friendly odd partition of $n$ is a sequence $(a_1, a_2, \ldots, a_k)$ of odd positive integers with $a_1 \le a_2 \le \cdots \le a_k$ and $a_1 + a_2 + \cdots + a_k = n$ such that for all positive integers $m \le n$, $m$ can be uniquely written as a subsum $m = a_{i_1} + a_{i_2} + \cdots + a_{i_r}$. (Two subsums $a_{i_1} + a_{i_2} + \cdots + a_{i_r}$ and $a_{j_1} + a_{j_2} + \cdots + a_{j_s}$ with $i_1 < i_2 < \cdots < i_r$ and $j_1 < j_2 < \cdots < j_s$ are considered the same if $r = s$ and $a_{i_l} = a_{j_l}$ for $1 \le l \le r$.) For example, $(1, 1, 3, 3)$ is a sum-friendly odd partition of $8$. Find the number of sum-friendly odd partitions of $9999$.
Problem
Source: Indian IMOTC 2013, Team Selection Test 3, Problem 1
Tags: combinatorics, Integer partitions
Ankoganit
03.03.2016 12:10
Please check the proof below, I am not too sure: Observe that the $a_1,a_2$ must equal $1$ to have a subsum for $1$ and $2$. Now we shall prove the following results: Claim 1: For every $i$ , (1a) either $a_i=a_{i-1}$ or $a_i=(a_1+a_2+...+a_{i-1})+1$ ; and (1b) all numbers upto $a_1+a_2+...+a_i$ can be represented using the number $a_1,a_2,...,a_i$. Proof. We shall use induction. The base case is easily verified. Suppose the statement holds for $i\le k-1$. Now obviously $a_k\ge a_{k-1}$. So we can have $a_k=a_{k-1}$. If not, then $a_k$ can be less than $(a_1+a_2+...+a_{k-1})+1$, since in that case we would have two representations for that number: one using the number $a_1,a_2,...,a_{k-1}$ (by the induction hypothesis), and one by $a_k$ itself. $a_k$ can't be greater than $(a_1+a_2+...+a_{k-1})+1$ as well, since then $(a_1+a_2+...+a_{k-1})+1$ will have no representation. Thus if $a_k\ne a_{k-1}$ we must have $a_k=(a_1+a_2+...+a_{k-1})+1$. For (1b), observe that numbers upto $(a_1+a_2+...+a_{k-1})$ can be already represented by the induction hypothesis, and for a $(a_1+a_2+...+a_{k-1})<x\le (a_1+a_2+...+a_{k-1}+a_k)$, represent $x-a_k$ by the induction hypothesis and add $a_k$. Also this implies that we can divide the sequence $\{a_i\}$ into 'run's, each being a maximal contagious block of the same number. The initial number of each block is one more than the sum of all preceding numbers. Claim 2. For all $i$, $a_i$ is an odd divisor of 10000, i.e., one of $1,5,25,125,625$. Proof. Take the smallest $i$ such that $a_i$ does not $10000$. Clearly it begins a run. Thus by claim 1 we have $a_i=a_1+a_2+...+a_{i-1}+1$. It can be easily shown via induction that $a_i|(a_1+a_2+...+a_j)+1$ for all $j\ge i$. Taking $j$ to be the last one we have $a_i|9999+1=10000$, a contradiction. Claim 3. The length of every run, except possibly the last one, is one less than an odd divisor of 10000. Proof. Take some non-last run, if exists, whose length, say $n$, is not so. By claim 2, the first number of this run is of the form $5^a$, so, by claim 1, the sum of all preceding numbers is $5^a-1$. Then the number next to the run is $(5^a-1)+5^a\times n +1=5^a(n+1)$ which again has to be one of the odd factors of $10000$. This forces that $n$ is one less than an odd divisor of 10000. Now by these three claims, we can easily list out all the possible sum-friendly odd partitions, by the following algorithm: 1)Start with 1's. 2)Take that number either $5^a-1$ times for some $a$ or numerous enough to reach 9999. 3)Add all preceding numbers, add 1 to it, to get the next number. 4)Now repeat from 2), until 9999 is reached. $\begin{array}{l} \underbrace{1,1,...,1}_{9999}\\ \underbrace{1,...1}_{624}, \underbrace{625,...,625}_{15}\\ \underbrace{1,..,1}_{124},\underbrace{125,...125}_{79}\\ \underbrace{1,...1}_{124}, \underbrace{125,..,125}_{4}, \underbrace{625,...625}_{15}\\ \underbrace{1,..,1}_{24},\underbrace{25,...,25}_{399}\\ \underbrace{1,...,1}_{24},\underbrace{25,...,25}_{24},\underbrace{625,...,625}_{15}\\ \underbrace{1,..,1}_{24},\underbrace{25,...,25}_{4},\underbrace{125,...125}_{79}\\ \underbrace{1,..,1}_{24},\underbrace{25,...,25}_{4}, \underbrace{125,..,125}_{4}, \underbrace{625,...625}_{15}\\ \underbrace{1,...,1}_4,\underbrace{5,...,5}_{1999}\\ \underbrace{1,...,1}_4,\underbrace{5,...,5}_{124},\underbrace{625,...,625}_{15}\\ \underbrace{1,...,1}_4,\underbrace{5,...,5}_{24},\underbrace{125,...125}_{79}\\ \underbrace{1,...,1}_4,\underbrace{5,...,5}_{24},\underbrace{125,..,125}_{4}, \underbrace{625,...625}_{15}\\ \underbrace{1,...,1}_4, \underbrace{5,...,5}_{4},\underbrace{25,...,25}_{399}\\ \underbrace{1,...,1}_4, \underbrace{5,...,5}_{4},\underbrace{25,...,25}_{24},\underbrace{625,...,625}_{15}\\ \underbrace{1,...,1}_4, \underbrace{5,...,5}_{4},\underbrace{25,...,25}_{4},\underbrace{125,...125}_{79}\\ \underbrace{1,...,1}_4, \underbrace{5,...,5}_{4},\underbrace{25,...,25}_{4}, \underbrace{125,..,125}_{4},\underbrace{625,...625}_{15}\end{array}$ These are $16$ in number. It is "easy" to verify that all of them work. I am looking forward for a confirmation that the above is correct or not. Also, i think there is a nicer proof, though I can't find it.
Ankoganit
06.03.2016 06:55
Hello I observed that the answer for $9,99,999,9999$ are $2^1,2^2,2^3,2^4$ respectively. Is it true in general? Does anyone have a nice proof for it?
MellowMelon
08.03.2016 03:45
Here is a recursive solution not specific to 9999. Abbreviate sum-friendly odd partition to SFOP. Let $c_n$ be the number of SFOPs of $n$. Lemma 1: In a SFOP, if $k$ copies of 1 are included, then all other numbers are a multiple of $k+1$.
Suppose not, and take the smallest number $a$ which is not a multiple of $k+1$. Let $a = q(k+1) + r$ for $0 < r < k+1$. Then $q(k+1)$ must be representable by the SFOP using only $k$ 1s and some multiples of $k+1$. By mod $k+1$, this representation can't use any 1s. But then $a$ can be represented both by $a$ itself and by adding $r$ copies of 1 to the representation for $q(k+1)$, contradicting uniqueness.
Corollary: In an SFOP for $n$, if $k$ copies of 1 are included, then $n+1$ is a multiple of $k+1$. Lemma 2: We have $c_0 = 1$. For $n > 0$, if we let $S$ be the set of positive divisors $d$ of $n+1$ for which $d/(n+1)$ is an odd number greater than 1, then for $n$ even, \[ c_n = \sum_{d \in S} c_{d-1}, \]and for $n$ odd, \[ c_n = 1 + \sum_{d \in S} c_{d-1}. \]
$c_0 = 1$ is obvious. For the remaining $n$, we construct all possible SFOPs recursively. First, there have to be $k$ copies of 1 by some $k$. Then by the corollary to lemma 1, $k+1$ divides $n+1$, and by lemma 1, all other numbers in the SFOP are multiples of $k+1$. This also means that either $k = n$ or $k+1$ is odd, since all SFOP numbers are odd.
Let $d = \frac{n+1}{k+1}$. Construct a new SFOP for $d-1$ by removing all the 1s and dividing the remaining numbers by $k+1$. This is an SFOP for $d-1$ because the original SFOP for $n$ must have had a unique representation for each multiple of $k+1$ at most $n$, which could not use any 1s by looking mod $k+1$. We have $(k+1)d = n+1$. Since $k+1$ could be chosen to be an arbitrary odd positive divisor of $n+1$ greater than 1, $d$ is an arbitrary element of the $S$ defined in the lemma statement.
Conversely, every SFOP for $d-1$ can be turned into an SFOP for $n$ by multiplying all terms by $k+1$ and adding $k$ copies of 1. So we conclude that the number of SFOPs for $n$ with $k$ copies of 1 is equal to $c_{d-1}$ when $k < n$.
If $k = n$ and $n$ is odd, then the summation in the lemma statement does not count this possibility, so we add 1.
Lemma 2 is a way to recursively compute any $c_n$. To solve the original problem and find the pattern in the previous post, we use lemma 2 to prove by induction that $c_{2^a 5^b - 1} = 2^{\max(0, b-1)}$ for $a = 0$ and $c_{2^a 5^b - 1} = 2^b$ for $a > 0$. The general form of $c_n$ seems tractable but tricky even for the case of $n+1$ having two odd prime divisors.