A new December and a new bunch of puzzles from mscroggs.co.uk.

My first attempt is further down. But I thought of a better way.

These are equivalent:

• Writing n as a sum of m odd, positive integers (5 = 1+3+1).
• Writing n+m as a sum of m even, positive integers (8 = 2+4+2).
• Writing (n+m)/2 as a sum of m positive integers (4 = 1+2+1).

And how many ways can I write the last sum? Stars and bars. Imagine writing 4 as 1 1 1 1. We want to convert this to 3 positive integers. We do this by adding 2 bars in between, like 1 | 1 1 | 1. (3-1 = 2.) The bars could be added in 3 different positions, between 2 1s. (4-1 = 3.) Only 1 bar in each position. We can do this in (3 c 2) different ways. This is 3*2/2*1 = 3. Anyway, 1 | 1 1 | 1 corresponds to 1 | 1+1 | 1 = 1 | 2 | 1, corresponds to the 4 = 1+2+1.

Going back, writing (n+m)/2 as a sum of m positive integers can be done in ((n+m)/2-1 c m-1) different ways.

Anyway.

• Write 14 as m odd, positive integers.
• Write 14+m as m even, positive integers.
• Write (14+m)/2 as m positive integers.

To write 14 as a sum of m odd, positive integers, m must be at least 2 and at most 14. Also m is even, because the sum of an odd number of odd integers would be odd. Let’s look at these.

m	((14+m)/2-1 c m-1)
2	7
4	56
6	126
8	120
10	55
12	12
14	1

And when we add up the right column, we get 377.

First attempt:

There’s probably a smarter way to do this. But I needed an intermediary step, before I could answer the primary question. First: How many ways can I write a sum of odd, positive integers, if I don’t care about the order?

Sum	Integers
0	(nothing)
1	1*1
2	2*1 (1)
3	3*1 1*3 (2)
4	4*1 1*1+1*3
5	5*1 2*1+1*3 1*5
6	6*1 3*1+1*3 1*1+1*5
7	7*1 4*1+1*3 2*1+1*5 1*1+2*3 1*7
8	8*1 5*1+1*3 3*1+1*5 2*1+2*3 1*1+1*7
9	9*1 6*1+1*3 4*1+1*5 3*1+2*3 2*1+1*7 1*1+1*3+1*5 1*9
10	10*1 7*1+1*3 5*1+1*5 4*1+2*3 3*1+1*7 2*1+1*3+1*5 1*1+3*3 1*3+1*7 2*5 1*1+1*9
11	11*1 8*1+1*3 6*1+1*5 5*1+2*3 4*1+1*7 3*1+1*3+1*5 2*1+3*3 1*1+1*3+1*7 1*1+2*5 2*1+1*9 1*11
12	12*1 9*1+1*3 7*1+1*5 6*1+2*3 5*1+1*7 4*1+1*3+1*5 3*1+3*3 2*1+1*3+1*7 2*1+2*5 3*1+1*9 1*1+2*3+1*5 1*5+1*7 1*3+1*9 1*1+1*11
13	13*1 10*1+1*3 8*1+1*5 7*1+2*3 6*1+1*7 5*1+1*3+1*5 4*1+3*3 3*1+1*3+1*7 3*1+2*5 4*1+1*9 2*1+2*3+1*5 1*1+1*5+1*7 1*1+1*3+1*9 2*1+1*11 1*1+4*3 2*3+1*7 1*3+2*5 1*13
14	14*1 11*1+1*3 9*1+1*5 8*1+2*3 7*1+1*7 6*1+1*3+1*5 5*1+3*3 4*1+1*3+1*7 4*1+2*5 5*1+1*9 3*1+2*3+1*5 2*1+1*5+1*7 2*1+1*3+1*9 3*1+1*11 2*1+4*3 1*1+2*3+1*7 1*1+1*3+2*5 1*1+1*13 1*3+1*11 1*5+1*9 2*7

(1) I find this result for 2 by adding a 1 to the result for 1. 1 = 1*1. 2 = 1*1+1 = 2*1.

(2) I find this result for 3 by first adding a 1 to the result for 2 (getting the first new result), and then adding a 3 to the result for 0 (getting the second new result).

I only actually need the last cell. Let’s look a little closer at it. E.g. 3*1+1*11 is 1+1+1+11 (4 elements), when we don’t care about the order. Let’s look at how many different ways each sum can be written (how many permutations, like 1+1+1+11 = 1+1+11+1 = 1+11+1+1 = 11+1+1+1, 4 different ways).

Sum	#Elements	#Perms
14*1	14	1
11*1+1*3	12	12 (1)
9*1+1*5	10	10
8*1+2*3	10	(10 c 2) = 45 (2)
7*1+1*7	8	8
6*1+1*3+1*5	8	8*7 = 56 (3)
5*1+3*3	8	(8 c 3) = 56
4*1+1*3+1*7	6	6*5 = 30
4*1+2*5	6	(6 c 2) = 15
5*1+1*9	6	6
3*1+2*3+1*5	6	6 * (5 c 2) = 6*10 = 60 (4)
2*1+1*5+1*7	4	4*3 = 12
2*1+1*3+1*9	4	4*3 = 12
3*1+1*11	4	4
2*1+4*3	6	(6 c 2) = 15
1*1+2*3+1*7	4	4*3 = 12
1*1+1*3+2*5	4	4*3 = 12
1*1+1*13	2	2
1*3+1*11	2	2
1*5+1*9	2	2
2*7	2	1

(1) Among the 12 positions, I choose 1 for the 3.

(2) Among the 10 positions, I choose 2 for a 3. I can do this in “10 choose 2” ways.

(3) Among the 8 positions, I choose 1 for the 3. I can do this in 8 different ways. Among the remaining 7 positions, I choose 1 for the 5. I can do this in 7 different ways.

(4) Combining methods 2 and 3.

Finally we have to add up the right column. The result is 373. I did some of this manually, I must have missed a step somewhere. Oh yeah, I think I missed 3*3+5, good for 4 further permutations.