For positive integers $n, k, l$, we define the number of $l$-tuples of positive integers $(a_1,a_2,\cdots a_l)$ satisfying the following as $Q(n,k,l)$. (i): $n=a_1+a_2+\cdots +a_l$ (ii): $a_1>a_2>\cdots > a_l > 0$. (iii): $a_l$ is an odd number. (iv): There are $k$ odd numbers out of $a_i$. For example, from $9=8+1=6+3=6+2+1$, we have $Q(9,1,1)=1$, $Q(9,1,2)=2$, $Q(9,1,3)=1$. Prove that if $n>k^2$, $\sum_{l=1}^n Q(n,k,l)$ is $0$ or an even number.
Problem
Source: 2015 Korean Mathematical Olympiad P4
Tags: combinatorics, partitions, bijection
rkm0959
08.11.2015 07:17
Bump. This is a cool problem! The hint is in the tags.
MellowMelon
08.11.2015 18:16
Let $S(n,k) = \sum_{l=1}^n Q(n,k,l) $. We induct on $k$. The base case $k = 0$ is trivial since $Q$ is always 0 when $n > 0$. Suppose we know $S(n,k)$ is even for a fixed $k$ and all $n > k^2$, and consider $S(n,k+1)$ for some $n > (k+1)^2$. For any partition counted by $S(n,k+1)$ with $a_l > 1$, pair it with the same partition except with $a_l$ replaced with the two terms $a_l - 1$ and $1$. Let $T$ be the set of partitions that have not been paired up. Each partition in $T$ has $a_l = 1$ and combining 1 with $a_{l-1}$ makes an invalid partition. We can form a bijection between $T$ and the partitions counted by $S(n-2k-1, k)$ by taking each partition in $T$, removing the 1, and decreasing the other $k$ odd numbers by 2. We have $n-2k-1 > k^2$, so by the inductive hypothesis, $S(n-2k-1, k)$ is even. Then $|T|$ is even, meaning $S(n,k+1)$ is even as desired.
NguyenHungQuangKhai
31.12.2016 05:15
i don't understand the problem
mathverse06
19.06.2023 06:51
MellowMelon wrote: Let $S(n,k) = \sum_{l=1}^n Q(n,k,l) $. We induct on $k$. The base case $k = 0$ is trivial since $Q$ is always 0 when $n > 0$. Suppose we know $S(n,k)$ is even for a fixed $k$ and all $n > k^2$, and consider $S(n,k+1)$ for some $n > (k+1)^2$. For any partition counted by $S(n,k+1)$ with $a_l > 1$, pair it with the same partition except with $a_l$ replaced with the two terms $a_l - 1$ and $1$. Let $T$ be the set of partitions that have not been paired up. Each partition in $T$ has $a_l = 1$ and combining 1 with $a_{l-1}$ makes an invalid partition. We can form a bijection between $T$ and the partitions counted by $S(n-2k-1, k)$ by taking each partition in $T$, removing the 1, and decreasing the other $k$ odd numbers by 2. We have $n-2k-1 > k^2$, so by the inductive hypothesis, $S(n-2k-1, k)$ is even. Then $|T|$ is even, meaning $S(n,k+1)$ is even as desired. Wonderful solution^^
foolish07
21.08.2024 17:31
Can I use generating function to solve it?