We have $2012$ sticks with integer length, and sum of length is $n$. We need to have sticks with lengths $1,2,....,2012$. For it we can break some sticks ( for example from stick with length $6$ we can get $1$ and $4$). For what minimal $n$ it is always possible?
Problem
Source: St Petersburg Olympiad 2012, Grade 9, P7
Tags: combinatorics, number theory
Vrangr
29.09.2017 16:30
RagvaloD wrote: We have $2012$ sticks with integer length, and sum of length is $n$. We need to have sticks with lengths $1,2,....,2012$. For it we can break some sticks ( for example from stick with length $6$ we can get $1$ and $4$). For what minimal $n$ it is always possible? Shouldn't we be able to get $2$ and $4$ from a stick of length $6$, or am I missing something?
RagvaloD
29.09.2017 16:33
rd1452002 wrote: RagvaloD wrote: We have $2012$ sticks with integer length, and sum of length is $n$. We need to have sticks with lengths $1,2,....,2012$. For it we can break some sticks ( for example from stick with length $6$ we can get $1$ and $4$). For what minimal $n$ it is always possible? Shouldn't we be able to get $2$ and $4$ from a stick of length $6$, or am I missing something? Yes, but if we need only $4$ and $1$ we can throw out 1 segment.
arvindf232
01.04.2018 16:00
Straight forward problem. $n$ must be at least $ 2012*2011+1 $, otherwise we can just take 2012 sticks of 2011, and clearly we don't get a any 2012 length stick. After taking off the length 2012, the remaining is 2011 sticks of total length at least $2012*2010+1$ , which is greater than $2011*2010+1$. We can thus similarly obtain a stick of 2011. We can complete obtaining the sticks through induction.
Pathological
24.05.2019 00:40
@above No not quite, since "After taking off the length $2012$" seems to assume that there exists a stick of length exactly $2012$. Pigeonhole tells us that there is a stick with length at least $2012$, but not exactly $2012.$ If the stick has length strictly greater than $2012$, then after removing the length $2012$ section we're still left with some extra bit, which means the number of sticks is still $2012$, and so we can't apply the inductive hypothesis (we'd require there to be $2011$ sticks). Fortunately, only a small tweak is required to fix that .
Do as arvindf232 did to show that $n \ge 2012^2 - 2012 + 1.$ Now, we'll show by strong induction that if $n$ sticks have total length $n^2 - n + 1$, then we can split them and toss out some scraps as needed in such a way as to produce sticks of lengths $1, 2, \cdots, n.$ When $n = 1$, this is obvious.
Suppose that it holds for $n \le k$.
When $n = k+1$, we have $k+1$ sticks of total length $k^2 + k + 1$ and wish to split them and discard some pieces to obtain sticks of lengths $1, 2, \cdots, k+1$. If there is a stick of length exactly $k+1$, then we can do as arvindf232 did. Otherwise, consider the stick of the longest length $\ell > k+1$ (we know it's $>k+1$ by Pigeonhole). Since the sum of lengths of the other $k$ sticks is $< (k^2 + k + 1) - (k+1) = k^2$, there is one of length $m \le k-1.$ Hence, cutting a section of length $k+1$ from the length $\ell$ one (to fulfill the $k+1$-length stick requirement) and scrapping the length $m$ one (so that there are $k$ sticks now, of lengths $\ell-(k+1)$ and all of the $k-1$ sticks other than the length $\ell$ and the length $m$ one), we can now successfully apply the inductive hypothesis since $k^2 + k + 1 - (k+1) - m \ge k^2 + k + 1 - (k+1) - (k-1) = k^2 - k + 1,$ completing the induction.
$\square$