Breaking pencils in two

If there were no more than $1008$ pencils of each length $1,\tfrac12,\tfrac14,...$ in the box, the total length of pencils would be less (we can only make a finite number of breaks, and so the number of pencils in the box will always be finite) than the infinite sum $1008\big(1 + \tfrac12 + \tfrac14 + \tfrac18 + \cdots\big) \; = \; 2 \times 1008 \; = \; 2016$ which is not possible. Thus there must be at least $1009$ pencils of some length in the box at any stage.

It is possible to have an arrangement where there are no more than $1009$ pencils of any one length.

• Break 1007 pencils in half, leaving 1009 pencils of length $1$ and 2014 pencils of length $\tfrac12$ .
• Break 1005 of the length $\tfrac12$ pencils in half, leaving 1009 pencils of length $\tfrac12$ and 2010 pencils of length $\tfrac14$ .
• Break 1001 of the length $\tfrac14$ pencils in half, leaving 1009 pencils of length $\tfrac14$ and 2002 pencils of length $\tfrac18$ .
• Break 993 of the length $\tfrac18$ pencils in half, leaving 1009 pencils of length $\tfrac18$ and 1986 pencils of length $\tfrac1{16}$ .
• Keep on going until there are fewer than 1009 pencils of the shortest length.

There are infinitely many ways to break those 2016 sticks. But the question is asking us what is the value of x so that if we choose any of those infinite ways, at any step we will have at least x sticks of same kind. So I assume that it is clear by now what the question is asking. Now let us say that the length of one of those 2016 sticks is 1 unit. We observe that the subsequent lengths of sticks will be of form 1/2^n where n is an integer. Now let us say there are ai pieces of the length 1/2^i. We have the equation a0 +a1/(2^1) + a2 /(2^2) +a3/(2^3)+.....= 2016 The solution of the values of ai from here represents each and every case possible. Now in all those solution sets, there exists a maximum value of ai. We need to find the minimum of the set of maximum values of ai to answer the question.

To do that first simply consider the equation a0+a1/2 = 2016. Now one solution of this equation is going to be (1008,2016) We observe that if we increase the value of a0, the value of a1 decreases. So in these solutions the case we are looking for will be when a0=a1=1344 (in this case), because out of all the solutions of the above equation, the minimum of max(a0,a1) will be 1344.

Extending this argument further, in the case of 3 variables a0+a1/2+a2/4= 2016, we observe this same again. Now here the equality a0=a1=a2 corresponds to (1152,1152,1152) triplet. ( I hope it is clear why we are choosing the equal values, if its not let me know in the comments I will elaborate it more) But luckily here we could get the integer values of a. Now in case we get a non integer as in a0+a1/2+a2/4+a3/8= 2016 case the optimised solution is (1075.2,1075.2,1075.2,1075.2) But clearly we can see our ai cannot take non integral values. So we have to round it off the right way. Now to round off, if we choose a0 as 1076, then it would give us the answer 1076 because all the other values are going to be less than it. But if we chose a0 as 1075, then at least one of the other three values is greater than 1075.2. Combining these two observations we can say that in case of non integral values, we take the ceiling of the non integral value as answer.

Now coming to our question the equation now to be solved is a (1+(1/2)+(1/2^2)+(1/2^3)+....) =2016 Now since we are tending to infinity the infinite sum tends to 2 but is still slightly less than 2 by a very very small amount. So a is going to be bigger than 1008 by very very small amount but when we take its ceiling function, we get 1009.

I hope this helps. If any part is not clear, let me know and I will elaborate.

Just a question for Nur or whom ever made this a weekly problem: why make 2016 sticks and not 2018? It doesn’t change much but make the problem up-to-date.

Taking the instructions that:

We start with 2016 sticks

1. picking a stick at random, it is broken into two equal halves and both are replaced in the box
2. continue repeating this process, but stop sometime or somewhere in the process and then count the number of equal-sized sticks.

It is apparent that 2015 is a guaranteed maximum number for equal-length sticks. I will choose to stop ( during the process) after the first selection.

I do not understand Mark Henning's solution (sorry, Mark!). I also do not understand the answer 1009.

I originally picked 1008, since after 1008 selections, there would still be a minimum of 1008 equal-length sticks available (guaranteed). Mark's solution, however, pointed me to the answer 2015 (thank you Mark).

If any time during this process can include " just after the process starts, but before I select a stick ", then the answer could be 2016.

I'd like to elaborate on finding solutions to problems in which random members are chosen and manipulated, such as in this one. First off, in this particular case, the problem is asking for a guarantee of 'x'. With this in mind, we can reinterpret the question like so:

Let 'n' be the number of sticks that we start with, with each having a length of 1 unit. Consider the fact that when breaking each stick, the sum of the lengths of all the sticks remains at n units. Let's consider the set of all configurations of sticks that can be achieved by some combination of picking sticks and breaking them into two equal halves. We can now rephrase the question like so: what is the lower bound on the highest number of equal-length sticks for every member of this set?

Now this turns into an optimization problem. Can we come up with some configuration that, when taking any number of sticks and splitting them, will result in a greater number of equal-length sticks? Let's reason through this step by step. First, we have 2016 sticks, all of equal length. Taking any one of those sticks and splitting them will give us 2015 equal-length sticks, which is a lower number than 2016, so our original setup was not an optimal solution. Now we start looking at extremes. If we took all 2016 sticks and split them, we would have 4032 sticks, which is definitely not optimal. But what if we took 1008 of those 2016 sticks and split them? Then, we would have 2016 half-length sticks, and 1008 full-length sticks. Notice the symmetry we have achieved here. If we segregate the 1008 full-length sticks, we will have 2016 half-length sticks, which is just a scaled down copy of our original setup. Now we can take half of those 2016 half-length sticks, split them, and come up with 1008 half-length sticks and 2016 quarter-length sticks.

Now imagine applying this process indefinitely. How would we know if we have achieved an optimum (a lower bound on the highest number of equal-length sticks)? If we took any random stick from this configuration, it's length would be 1/2^m where 'm' is some integer, and there would be 1008 sticks of its kind. Breaking it up would give us 1007 sticks of length 1/2^m, yes, but it would also give us 1010 sticks of length 1/2^(m+1), because the number of sticks of length 1/2^(m+1) used to be 1008, but we just added 2 more sticks to that group. This means that the highest number of equal-length sticks for this new configuration is 1010. This value is greater than that of our previous configuration, 1008, and since we could've picked any stick from that configuration, it means that configuration is an optimal solution (and that 1008 is the lower bound). So why isn't it the solution to the problem?

As some have pointed out, the problem is looking at configurations that can be achieved by any number of iterations of the process (the process being: "taking a stick and splitting it into equal halves"). Our configuration required an infinite number of steps. So our configuration is not valid because it cannot be achieved by any number of steps, for infinity is not a number. Admittedly, the question used the word "time" when describing steps of the process, which fuzzes up some interpretations. For instance, it is mathematically possible to perform an infinite number of steps in a finite amount of time, through a process known as a "Supertask" (https://en.wikipedia.org/wiki/Supertask). However, we have 3 tries to solve the problem, so if you input 1008 the first time and didn't get it right, at least you have 2 more tries. I agree that the wording is a bit fuzzy, though.

Now as for finding a configuration in a finite number of steps, this turned out to be somewhat tedious. Firstly, you can assume that because 1008 didn't work, and it was a supposed lower bound, the next potential lower bound would be at 1009. And it does turn out that 1009 has a solution, although this solution takes some working out to find. I used the fact that the infinite sum '(1 + 1/2 + 1/4 + ...) = 2', and that if I wanted to modify the sum to be finite but still equal to 2, I can cut off the series at any point, and multiply the last term by 2. For example, '(1 + 1/2 + 1/4 + 1/8 + 2/16) = (1 + 1/2 + 1/4 + 1/8 + 1/8) = 2'. I then related 2016 to the nearest power of 2, which is 2048 (so 2016 = 2048 - 32). So if we let 'p = 2048/2 = 1024', then we have: '2048 = (p + p/2 + p/4 + p/8 + p/16 + p/32 + p/64 + p/128 + p/256 + p/512 + (2*p)/1024)'. Substituting 'p' for '1009 = p - 15', we get: '(p-15) + (p-15)/2 + (p-15)/4 + (p-15)/8 + (p-15)/16 +(p-15)/32 + (p-15)/64 + (p-15)/128 + (p-15)/256 + (p-15)/512 + (2p-30)/1024) = 2018'. Note that the last term, '(2p-30)/1024', can be written as '1 + 994/1024'. We subtract out that extra 1 from this term, and also the first term 'p-15', to get 'p-16', so that our total sum is now equal to 2016. So our final result is:

1008 sticks of unit-length, 9 groups of 1009 sticks of '1/2, 1/4, 1/8, 1/16, 1/32, 1/64, 1/128, 1/256, and 1/512' lengths, and 994 sticks of 1/1024 length.

The problem asks for a number x such that, no matters how many times we repeat the process, we can be sure that at least x sticks will have the same length. We can consider sticks of 1 unit of lenght initially. We can represent ai, i=0,1,2,3,4,...m, where "ai" means the ammount of sticks of length "(1/2)^i". In this way (a0,a1,a2,a3,...,am) will represent the different amounts for each length (in decreasing order)

   Note 1: When we break a stick of length (1/2)^i, ai dicreases in 1 and a[i+1] goes up in 2. (because we made two new pieces with the first one)

   Note 2: Let´s N be the inital number of sticks and let´s x be the wanted number, i.e. NO MATTERS HOW MANY STICKS WE BREAK, WE WILL HAVE 
   ALWAYS AT LEAST x STICKS WITH THE SAME LENGTH. I afirm that x > N/2:

     N= Sum(ai·(1/2)^i) <= Sum(x·(1/2)^i) = xSum((1/2)^i) = x(2-1/2^m) < 2x,   so is clear that x > N/2.

Let´s see some numeric examples to practice with the notation:

 For example, if we take 3 initial sticks, in the first step we will have (3). In the second step (2,2)

 For n=4, (4) then (3,2) and no matters how many steps we take, we will always have AT LEAST 3 with the same length.

 For n=5 the solution is also x=3: (5) , (4,2) , (3,4), (3, 3, 2) and no matters how many steps we take, we will always have AT LEAST 3 with the same length.

 For n=6 the solution is x=4: (6) , (5,2), (4,4) which is the solution (as we are going to prove).

I afirm that given a inital natural number N of sticks, the general solution is x = WholePart(N/2) + 1. Let´s see it:

Case 1

Case 1: If N is an odd number, N=2n+1, I afirm that the solution would be x = WholePart(N/2) + 1 i.e. x=n+1

According to Note 1, we begin with (n+1, 2n).

If 2n<=n+1, we have the solution. Else we have (n+1, n+1, 2n-2). 

If 2n-2 <= n+1, we have the solution. Else, we have (n+1, n+1, n+1,2n-6).

And we continue the process till the last term is <= n+1.

After k steps, we have (n+1, n+1, n+1,......., 2n+2-2^k) and we continue the process while 2n+2-2^k <= n+1. Solving this equation, we get that k is the first 
natural number such that 2^k>=n+1. 

So, the solution will be (n+1, n+1, n+1, ....., 2n+2-2^k) being the first k values "n+1", and 2n+2-2^k por the k+1 position.

Case 2

Case 2. If N is an even number, the reasoning is quiet similar and the solution will be (n+1, n+1, n+1, ....., 2n+2-2^k) being the first k-1 values "n+1", and 
2n+2-2^k por the k position.

Let´s see two examples:

Example 1

  Case 1. Odd number = 17. 
  x = Whole Part(17/2)+1= 9 must be the solution.

  The first k such that 2^k>=9 is k=4, so according to above (9,9,9,9,2) is the solution and this is true because 9+9/2+9/4+9/8+2/16= 17

Example 2

  Case 2. Even number= 2016
  x =  Whole Part(2016/2)+1= 1009 must be the solution.

 The first k such that 2^k>=1009 is k=10. So (1009, 1009, 1009, 1009, 1009, 1009, 1009, 1009, 1009, 994) is the solution and this is true because 
1009 + 1009/2 +1009/4 +1009/8 + 1009/16 + 1009/32 + 1009/64 + 1009/128 +  1009/256 + 994/512 = 2016