This December I participated in Advent of Code.
Days 1-6 happened without a lot of drama (only 1 question on the forum). This phase also mostly saw me coding in a sandbox (exception: day 3, part 2). Day 7 I permanently changed to my PC. The tasks were rather easy for me. I didn’t really try to come up with a fast answer, in part because the sandbox + my tablet was a slow way to code. My examples below manipulate the test data, but ran on the actual data as well.
A new December and a new bunch of puzzles from mscroggs.co.uk.
n = 99999…999
= 1055 – 1
n3 = (1055 – 1)3
= (1055)3 + 3*(1055)2*(-1) + 3*(1055)*(-1)2 + (-1)3
= 10165 – 3*10110 + 3*1055 – 1
10000...0000...0000...000
- 300...0000...000
+ 300...000
- 1
==========================
9999...9700...0299...999
So now we just have to count the 9s and 7s and the 2.
The 1 lives in position 1. The 3 above it has a 3 in position 56. The next 3 is in position 111. Finally the 1 above it is in position 166.
The result of adding and subtracting is 9s from position 1 to 55, a 2 at position 56, then some 0s, a 7 at position 111 and finally 9s from position 112 to 165. 55*9+2+7+54*9 = 990. Which happens to be 55*18.
Just to test my logic here: if n had been 9999 (4 digits), n3 would be 999,700,029,999. 4*9+2+7+3*9 = 72 = 4*18. Checks out.
A new December and a new bunch of puzzles from mscroggs.co.uk.
n + n+1 + n+2 + … n+10 = 2024
Let m = n+5
m-5 + m-4 + … m + … m+5 = 2024
11m = 2024
m = 2024/11 = 184
n = m-5 = 179
A new December and a new bunch of puzzles from mscroggs.co.uk.
I think the example is also a hint.
A number with 1 factor would be 1. And that’s not 13.
A number with 2 factors would be a prime. Number p, factors 1 and p. The geometric mean would be (1*p)1/2. We can’t get 13 to fit there.
A number with 3 factors has a special property. There’s a square here somewhere. The number, p2, has factors 1, p and p2. This accounts for p2 = 1 * p2 = p * p, the 2 different ways to write p2. Like, 9 = 1*9 = 3*3. The geometric mean works out to be p, isn’t that neat? So my guess is that we’re looking for 132 = 169.
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:
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.
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.
A new December and a new bunch of puzzles from mscroggs.co.uk.
14 is even, so 2 is a factor. The other factor is 7, a prime, so it can’t be constructed by multiplying lower numbers.
100 d100: One factor is 2, to get an even product the lowest possible way. Then the other factor of the product is a prime p, in this case 101, to make the product impossible. (Anything lower could be reached with 198 * 2 * p.) The product is 202.
A new December and a new bunch of puzzles from mscroggs.co.uk.
The only way to reach the sum 16 with 5 different positive integers is 1+2+3+4+6.
The lowest possible sum with 5 different positive integers is 1+2+3+4+5 = 15. In order to reach 16, one of these integers has to be 1 higher. If the integers are still different after this operation, the only candidate is 5.
Alternate proof: Play Killer Sudoku.
The product is 1*2*3*4*6 = 144.
Stuff from ommadawn.dk (Lise Andreasen) 