Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 IMO Problems/Problem 4"

(Created page with "Let n > 0 be an integer. We are given a balance and n weights of weight 2^0, 2^1,...2^n-1. We are to place each of the n weights on the balance, one after another, in such a way ...")
 
 
(24 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
Let n > 0 be an integer. We are given a balance and n weights of weight 2^0, 2^1,...2^n-1. We are to place each of the n weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
+
==Problem==
 +
Let <math>n > 0</math> be an integer. We are given a balance and <math>n</math> weights of weight <math>2^0,2^1, \cdots ,2^{n-1}</math>. We are to place each of the <math>n</math> weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
 
Determine the number of ways in which this can be done.
 
Determine the number of ways in which this can be done.
 +
 +
==Solution==
 +
Call our answer <math>W(n)</math>.
 +
We proceed to prove <math>W(n)=(2n-1)!!</math>.
 +
 +
It is evident <math>W(1)=1</math>.
 +
 +
Now, the key observation is that smaller weights can ''never'' add up to the weight of a larger weight, ''ie'' which side is heavier is determined completely by the heaviest weight currently placed. It follows, therefore, that the number of ways to place <math>n</math> weights on the balance according to the rule is the same no matter which <math>n</math> distinct powers of two are the weights, as each weight completely overpowers any smaller weight and is completely overpowered by any larger weight. That is, there is the 1st heaviest weight, the 2nd heaviest, the 3rd, ..., the n-th heaviest, and each weight is negligible compared to any heavier weight. Thus, any valid placement of <math>n</math> weights of weight <math>2^0,2^1, \cdots ,2^{n-1}</math> can changed by replacing <math>2^i</math> with the <math>(n-i)</math>-th heaviest weight in the set <math>{2^{a_k}}</math>, where <math>a_k \in \mathbb{Z}</math>, and vice versa, forming a <math>1:1</math> relation. With this in mind, we use recursion upon the last weight placement. There are <math>2n-1</math> choices; namely, you can put any weight on either side except for the heaviest weight on the right. For the first <math>n-1</math> weight placements, the answer reduces to <math>W(n-1)</math>. We can reduce <math>W(n-1)</math> in the same way.
 +
 +
<math>W(n)=(2n-1)W(n-1)=(2n-1)(2n-3)W(n-2)=...=(2n-1)!!W(1)=(2n-1)!!</math>
 +
 +
<math>\text{QED}</math>
 +
 +
==Alternative Solution==
 +
 +
We can compute the answer <math>W(n)</math> by conditioning on the position of the heaviest weight in the order of placement :
 +
<cmath>W(n)=\sum_{k=1}^{n}W(k-1)2^{n-k}\frac{(n-1)!}{(k-1)!}</cmath>
 +
The heaviest weight can only go to the left pan. <math>W(k-1)</math> is the number of ways to place the first <math>(k-1)</math> weights which got placed before the heaviest weight at position <math>k</math>. We used the fact that the number of valid ways does not depend on the actual weights because each weight is heavier than the sum of all the weights lighter than it. There are <math>\frac{(n-1)!}{(k-1)!}</math> ways to select <math>(n-k)</math> weights ( the order matters ) after the heaviest one out of <math>(n-1)</math> other weights . This is because there are <math>(n-1)</math> ways to select the 1st weight after the heaviest, <math>(n-2)</math> to select the next one etc.
 +
Each of these <math>(n-k)</math> weights can go to the left or the right pan so there are <math>2^{n-k}</math> ways to create all left-right combinations. 
 +
Rearange as recursion:
 +
<cmath> W(n)=2(n-1)\sum_{k=1}^{n-1}W(k-1)2^{n-1-k}\frac{(n-2)!}{(k-1)!}+W(n-1) = (2n-1)W(n-1)</cmath>
 +
That is:
 +
<cmath>W(n)=(2n-1)(2n-3)...1 = (2n-1)!!</cmath>
 +
as <math>W(1)=1</math> since if you have just one weight it can only go to the left pan.
 +
 +
--[[User:alexander_skabelin|alexander_skabelin]] 9:24, 13 July 2023 (EST)
 +
 +
{{alternate solutions}}
 +
 +
==See Also==
 +
 +
{{IMO box|year=2011|num-b=3|num-a=5}}

Latest revision as of 00:21, 19 November 2023

Problem

Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0,2^1, \cdots ,2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed. Determine the number of ways in which this can be done.

Solution

Call our answer $W(n)$. We proceed to prove $W(n)=(2n-1)!!$.

It is evident $W(1)=1$.

Now, the key observation is that smaller weights can never add up to the weight of a larger weight, ie which side is heavier is determined completely by the heaviest weight currently placed. It follows, therefore, that the number of ways to place $n$ weights on the balance according to the rule is the same no matter which $n$ distinct powers of two are the weights, as each weight completely overpowers any smaller weight and is completely overpowered by any larger weight. That is, there is the 1st heaviest weight, the 2nd heaviest, the 3rd, ..., the n-th heaviest, and each weight is negligible compared to any heavier weight. Thus, any valid placement of $n$ weights of weight $2^0,2^1, \cdots ,2^{n-1}$ can changed by replacing $2^i$ with the $(n-i)$-th heaviest weight in the set ${2^{a_k}}$, where $a_k \in \mathbb{Z}$, and vice versa, forming a $1:1$ relation. With this in mind, we use recursion upon the last weight placement. There are $2n-1$ choices; namely, you can put any weight on either side except for the heaviest weight on the right. For the first $n-1$ weight placements, the answer reduces to $W(n-1)$. We can reduce $W(n-1)$ in the same way.

$W(n)=(2n-1)W(n-1)=(2n-1)(2n-3)W(n-2)=...=(2n-1)!!W(1)=(2n-1)!!$

$\text{QED}$

Alternative Solution

We can compute the answer $W(n)$ by conditioning on the position of the heaviest weight in the order of placement : \[W(n)=\sum_{k=1}^{n}W(k-1)2^{n-k}\frac{(n-1)!}{(k-1)!}\] The heaviest weight can only go to the left pan. $W(k-1)$ is the number of ways to place the first $(k-1)$ weights which got placed before the heaviest weight at position $k$. We used the fact that the number of valid ways does not depend on the actual weights because each weight is heavier than the sum of all the weights lighter than it. There are $\frac{(n-1)!}{(k-1)!}$ ways to select $(n-k)$ weights ( the order matters ) after the heaviest one out of $(n-1)$ other weights . This is because there are $(n-1)$ ways to select the 1st weight after the heaviest, $(n-2)$ to select the next one etc. Each of these $(n-k)$ weights can go to the left or the right pan so there are $2^{n-k}$ ways to create all left-right combinations. Rearange as recursion: \[W(n)=2(n-1)\sum_{k=1}^{n-1}W(k-1)2^{n-1-k}\frac{(n-2)!}{(k-1)!}+W(n-1) = (2n-1)W(n-1)\] That is: \[W(n)=(2n-1)(2n-3)...1 = (2n-1)!!\] as $W(1)=1$ since if you have just one weight it can only go to the left pan.

--alexander_skabelin 9:24, 13 July 2023 (EST)

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2011 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_4&oldid=204547"