COMBINATORICS MARATHON: SEASON 2
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 ?
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 ?
ধনঞ্জয় বিশ্বাস
Re: COMBINATORICS MARATHON: SEASON 2
$\left \lfloor log_2 n \right \rfloor +1$
$\text{Post edited due to some "Hurry Hitches"}$
Last edited by *Mahi* on Thu Oct 13, 2011 10:34 pm, edited 1 time in total.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
Re: COMBINATORICS MARATHON: SEASON 2
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...
Post another problem...
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
Re: COMBINATORICS MARATHON: SEASON 2
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.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: COMBINATORICS MARATHON: SEASON 2
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.
Otherwise you won't do it in $ \lfloor log_2 {n} \rfloor + 1$ steps in all cases.
ধনঞ্জয় বিশ্বাস
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
Re: COMBINATORICS MARATHON: SEASON 2
New problem plzzzz
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
Re: COMBINATORICS MARATHON: SEASON 2
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
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
Last edited by *Mahi* on Mon Oct 17, 2011 2:46 pm, edited 1 time in total.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: COMBINATORICS MARATHON: SEASON 2
Obviously wrong!! Choose $n=2,k=2$. Then \[\binom42=6\]*Mahi* wrote: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$
One one thing is neutral in the universe, that is $0$.
Re: COMBINATORICS MARATHON: SEASON 2
Thanks Masum bhai. I hope the problem is alright now.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: COMBINATORICS MARATHON: SEASON 2
Sorry, but my solution is by Number Theory. I would like to request the others for a combinatorial solution.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$