An (unordered) partition $P$ of a positive integer $n$ is an $n$-tuple of nonnegative integers $P=(x_1,x_2,\cdots,x_n)$ such that $\sum_{k=1}^n kx_k=n$. For positive integer $m\leq n$, and a partition $Q=(y_1,y_2,\cdots,y_m)$ of $m$, $Q$ is called compatible to $P$ if $y_i\leq x_i$ for $i=1,2,\cdots,m$. Let $S(n)$ be the number of partitions $P$ of $n$ such that for each odd $m<n$, $m$ has exactly one partition compatible to $P$ and for each even $m<n$, $m$ has exactly two partitions compatible to $P$. Find $S(2010)$.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
Unit10
20.04.2021 19:15
Can someone post the solution?
Mikeglicker
25.04.2021 23:42
Ho I will gve you a solution! The answer is 9 and here is how I got it. First observe that we can rephrase the question as in how many ways we can pick n natural numbers b1<=....<=bn (if a_i=m we put m times the number i) for which b1+...+bn=2010 and also every even number is the sum of b_i in 2 different ways, and every odd number in a single way. First note making 2 in two different ways is only with b1=b2=1, b3=2. Next note that the rest of the sequence must all be even because if odd m is in a_i then m+2 can be written in two ways, m+1+1 and m+2. Now lets construct b_i one by one, meaning we start wuith stating how many 2's it has, then how many 3's and then 4's and so on. Note that by the time you are done telling how many of some number there is in the sequence the next smaalestnumber is already determined and must equal the sum of all previous b_i. The reason for this is that one can pretty easily see that all numbers less then this sum can already be expressed in 2 ways, so now we cant take anything strictly less then the sum because that ,eans we have a third way to express this number. Also we must take something not larger then the sum in order to express it in a secound way. Therefore we can now tell that if by the time we say all numbers that equal something no matter what we do next if the total sum of them is m then in the end the total sum must be devisable by m. therefore m belongs to the divisors of 2010=2*3*5*67 so any time we are done adding elements of one number we are left on a number from the set (because we already know we start with 1,1 leaving us on 2) 2*3 2*5 2*67 2*3*5 2*3*67 2*5*67 2*3*5*67 and now just try case by case If first time we end in 2*3 secound time must end on either 2*3*5 or 2*3*67 and third is already 2010 so 2 way possibilities if we start on 2*3. Similarly 2 possibilities if we start on 2*5 or 2*7. There are 3 more possibilities of starting at 2*3*5 or 2*3*67 or 2*5*67 each must then stop at 2010 so a total of not more and not less than 9 possiblities. Quite difficult isnt it?
Luffy.wang
26.08.2021 14:16
@above,I think the ans to this question is 13 instead of 9 However,your conclusion that the biggest number in {bi} equals the sum of all previous bi is quite right
CANBANKAN
04.04.2023 07:23
Repost of my solution from Shu Zhi Mi (it's in Chinese, but it should be easy to understand anyways, will write in English later)
Attachments:
