COMBINATORICS MARATHON: SEASON 2

[Corei13]

Oops! I forgot it is a marathon !

New problem:
You are given $n$ integers $1,2, \cdots ,n$. At each step you can choose any number of numbers from the $n$ numbers and then choose any positive integer $d$. Then you subtract $d$ from all of your chosen numbers. Your task is to make all the numbers equal to $0$. At least how many steps do you need ?

[*Mahi*]

$\left \lfloor log_2 n \right \rfloor +1$

First we notice a thing that, making some numbers equal is our goal as that would lessen the numbers to be made $0$ as equal numbers can be calculated together. Now we notice that at the starting, with a step we can reduce the set from $1,2, \cdots ,n$ to $1,2, \cdots , \left \lfloor \frac n 2 \right \rfloor $ by subtracting $\left \lfloor \frac n 2 \right \rfloor$ from $\left \lfloor \frac n 2 \right \rfloor +1$ to $n$. So we get if the required number of steps is $a_n$ then $a_n = a_{ \left \lfloor \frac {n} 2 \right \rfloor} + 1$ .
So by recursion, we get $a_n=\left \lfloor log_2 n \right \rfloor +1$

$\text{Post edited due to some "Hurry Hitches"}$

[sourav das]

Actually $1,2,..n$ to $1,2...\left \lfloor \frac{n}{2} \right \rfloor$. And ans: $\left \lfloor log_{2}n \right \rfloor+1$
Post another problem...

[*Mahi*]

Sorry for those little hitch...I was in a real hurry...But the $1,2,..n$ to $1,2, \cdots , \left \lceil \frac n 2 \right \rceil$ part is right , check again.

[Corei13]

Actually it should be " We can reduce $1,2,\cdots ,n$ to $1, 2, \cdots \left \lfloor \frac{n}{2} \right \rfloor$ "
Otherwise you won't do it in $ \lfloor log_2 {n} \rfloor + 1$ steps in all cases.

[sourav das]

New problem plzzzz

[*Mahi*]

It's easy to prove using NT, but I was looking if someone can give a combinatorial proof:
New Problem!
$\boxed 4$ Prove that $\binom{2^n - 1}{k}$ is odd for all $k \leq (2^n -1)$

Post edited due to another fingerslip

[Masum]

It's easy to prove using NT, but I was looking if someone can give a combinatorial proof:
New Problem!
$\boxed 4$ Prove that $\binom{2^n}{k}$ is odd for all $k \leq 2^n$

Obviously wrong!! Choose $n=2,k=2$. Then \[\binom42=6\]

[*Mahi*]

Thanks Masum bhai. I hope the problem is alright now.

[SANZEED]

Sorry, but my solution is by Number Theory. I would like to request the others for a combinatorial solution.

The term can be expanded as follows: \[\binom{2^{n}-1}{k}=\frac{(2^{n}-1)(2^{n}-2)...(2^{n}-k-1)}{1\cdot 2\cdot 3...k}\]
Now if $2^{s}\leq k\leq 2^{s+1}$, then the highest power of $2$ in the denominator is \[\left \lfloor \frac{k!}{1} \right \rfloor+\left \lfloor \frac{k!}{2} \right \rfloor+\left \lfloor \frac{k!}{4} \right \rfloor+...+\left \lfloor \frac{k!}{2^{s}} \right \rfloor=2^{s+1}a ,(k=2^{s}a)\].
Now in the numerator, note that if $i$ is odd, then $2^{n}-i$ is odd and for even $i$, $2^{n}-i$ is divisible by $2$. So the highest power of $2$ in the numerator just means the highest power of $2$ in the denominator, which is \[\left \lfloor \frac{k!}{1} \right \rfloor+\left \lfloor \frac{k!}{2} \right \rfloor+\left \lfloor \frac{k!}{4} \right \rfloor+...+\left \lfloor \frac{k!}{2^{s}} \right \rfloor=2^{s+1}a ,(k=2^{s}a)\].
This proves the claim.