Compositions of $20$ that have exactly $14$ summands

107 Views Asked by At

Question: Prove that for each of the $27132$ of these (compositions of $20$ with exactly $14$ summands), there is always a collection of consecutive summands which sum to $5$.

I know that I'm supposed to use the pigeonhole principle to prove this. I think that my main problem is that I'm not entirely sure what the question is saying. Does anyone have an idea on how to prove this? Thanks very much in advance

1

There are 1 best solutions below

0
On

HINT:

As @N.F.Taussig pointed out, the number of ways to break $20$ into $14$ positive numbers (ordering matters) is equal to the number of ways to insert $13$ $+$ signs into the $19$ spaces.

$$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$

Here is an example of such a breakdown:

$$1 + 1 \square 1 + 1 + 1 + 1 + 1 + 1 \square 1 + 1 + 1 \square 1 \square 1 + 1 + 1 \square 1 \square 1 + 1 + 1 + 1 \\ = 1 + 2 + 1 + 1 + 1 + 1 + 2 + 1 + 3 + 1 + 3 + 1 + 1 + 1= 20$$

Now what does a chunk of consecutive summands summing to $5$ look like? The parentheses and the curly braces show two such sample chunks:

$$(1 + 1 \square 1 + 1 + 1) + 1 + 1 + 1 \square 1 + 1 + 1 \square 1 \square 1 + \{ 1 + 1 \square 1 \square 1 + 1 \}+ 1 + 1 \\ = (1 + 2 + 1 + 1) + 1 + 1 + 2 + 1 + 3 + \{1 + 3 + 1\} + 1 + 1= 20$$

In the first example (the chunk enclosed by parentheses) this is caused by a $+$ sign in the 5th position, and a bit of thinking should convince you that whenever this happens, that means the corresponding initial chunk sums to $5$.

In the second example (the chunk enclosed by curly braces), this is caused by two $+$ signs in the 13th and 18th positions, i.e. they are $5$ positions apart. Again, a bit of thinking should convince you that whenever two $+$ signs are $5$ positions apart, the corresponding enclosed chunk sums to $5$.

So you just need to show that, by placing $13$ $+$ signs into $19$ spaces, either the 5th position will be filled, or the 15th position (i.e. 5th from the end) will be filled, or there will be two $+$ signs which are $5$ positions apart.

Can you finish from here, or do you need more hints?