Blog
2025-01-01
Welcome to 2025! I'm on holiday for the first couple of weeks of 2025: this post will be replaced with the announcement of the winners once I'm back.
In the meantime, you can find solutions to all the Advent calendar puzzles at mscroggs.co.uk/puzzles/advent2024
and read this blog post about puzzle 23.
(Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
Add a Comment
2025-01-01
The puzzle on day 23 of this year's Advent calendar
is an interesting puzzle. After some hasty editing once it was pointed out to me that the original wording
was nonsense, the puzzle was this:
23 December
In a grid of squares, each square is friendly with itself and friendly with every square that is horizontally, vertically, or diagonally adjacent to it (and is not friendly with any other squares).
In a 5×5 grid, it is possible to colour 8 squares so that every square is friendly with at least two coloured squares:
![](javascript:showlimage("advent2024-23dec.png"))
It it not possible to do this by colouring fewer than 8 squares.
What is the fewest number of squares that need to be coloured in a
23×23 grid so that every square is friendly with at least two coloured squares?
As the squares that a square is friendly with are the same as those that would be attacked by a chess king on the square, the puzzle could be
re-expressed as: What is the fewest number of kings that need to be placed on a 23×23 chess board so that every square is attacked or occupied by at least two kings
(with no more than one king placed on each square)?
I came up with this puzzle while playing around with square grids in early November last year. I started by working out how many squares
need to be coloured for some smaller grids:
| Size of grid | Example grid | Minimum number of squares | ||||||||||||||||||||||||||||||||||||
| 2×2 | 2 | |||||||||||||||||||||||||||||||||||||
| 3×3 | 3 | |||||||||||||||||||||||||||||||||||||
| 4×4 | 8 | |||||||||||||||||||||||||||||||||||||
| 5×5 | 8 | |||||||||||||||||||||||||||||||||||||
| 6×6 | 10 |
This sequence was not on the OEIS, so I set about trying to work out the general formula for a term in this sequence.
Let \(a(n)\) be the minimum number of squared coloured for an \(n\) by \(n\) grid.
To work out the formula for \(a(n)\), we'll split the problem into 3 cases:
when \(n\) is a multiple of 3,
when \(n\) is 1 less than a multiple of 3,
when \(n\) is 2 less than a multiple of 3.
\(n=3k-1\)
When \(n\) is 1 less than a multiple of 3, it can be written as \(3k-1\) for some integer \(k\).
An upper bound
We can get an upper bound for the number of squares by finding a pattern of coloured squares that works, as the minimum number of squares will
then be at most this. For a 2×2 grid, we can colour 2 squares like this:
For a 5×5 grid, we can colour 8 squares like this:
For an 8×8 grid, we can colour 18 squares like this:
We can continue this pattern: in general for a \((3k-1)\)×\((3k-1)\) grid, we colour in pairs of squares with a gap of one between them in every third row.
This would involve colouring \(k\) rows of \(2k\) squares, so a total of \(2k^2\) squares.
Therefore \(a(3k-1)\leqslant2k^2\).
A lower bound
To obtain a lower bound, consider these squares in 5×5 grid:
or these squares in 8×8 grid:
The squares that neighbour these highlighted squares do not overlap, so two different squares must be coloured for each of these. This means that at least
2×4 (for a 5×5 grid) and 2×9 (for a 8×8 grid) squares must be coloured.
Continuing the pattern of highlighting the squares in every third row and every third column, we see that for a \((2k-1)\)×\((2k-1)\) grid, we must colour
at least \(2k^2\) squares, and so \(a(3k-1)\geqslant2k^2\).
The general term
Combining the lower and upper bounds, we can see that \(2k^2\leqslant a(3k-1)\leqslant2k^2\), and so \(a(3k-1)=2k^2\). As 23 is one less than a multiple of 3,
this first case is enough to solve the puzzle in the Advent calendar.
\(n=3k-2\)
When \(n\) is 2 less than a multiple of 3, it can be written as \(3k-2\) for some integer \(k\). We can obtain upper and lower bounds in a very similar way.
An upper bound
To get an upper bound, consider this pattern of coloured squares:
For a \((3k-2)\)×\((3k-2)\) grid, this pattern involves colouring \(k\) rows of \(2k\) squares, and so \(a(3k-2)\leqslant2k^2\).
A lower bound
To get a lower bound, consider this pattern of highlighted squares:
In exactly the same was as for \(n=3k-1\), we can see from this pattern that \(a(3k-2)\geqslant2k^2\).
The general term
Once again, our upper and lower bounds are equal, and so \(a(3k-2)=2k^2\).
\(n=3k\)
Here's where this question gets trickier/more interesting. If \(n\) is a multiple of 3, then it can be written at \(3k\) for some integer \(k\).
An upper bound
We can obtain an upper bound from this pattern:
For a \(3k\)×\(3k\) grid, this pattern involved colouring \(k\) rows of \(2k+1\) squares, and so \(a(3k)\leqslant2k^2+k\).
A lower bound
As in the previous sections, we can get an lower bound using this pattern:
For a \(3k\)×\(3k\) grid, the lower bound requires at least \(2k^2\) squares to be coloured.
We can increase this lower bound by 1 by looking at the
bottom right corner: the previous lower bound can colour at most one square adjacent to this, so there must be at least one more square next to that corner coloured.
So we have arrived at the lower bound \(a(3k)\geqslant2k^2+1\).
Bounds
In this case, the lower and upper bounds are not the same, so we are left with \(2k^2+1\leqslant a(3k)\leqslant 2k^2+k\). I've written
a Python script to compute terms of this sequence and have used it to find that:
- \(a(3)=3\)
- \(a(6)=10\)
- \(a(9)=21\)
- \(a(12)=36\)
For \(n=12\) and larger than this, the script takes a very long time, so I haven't checked any more terms.
The sequence and a conjecture
Overall, we've shown that:
$$
a(n) = \begin{cases}
2k^2&\text{if }n=3k-1\\
2k^2&\text{if }n=3k-2\\
\text{between }2k^2+1\text{ and }2k^2+k&\text{if }n=3k
\end{cases}
$$
This can be written slightly more succinctly as (where \(\lfloor x\rfloor\) means \(x\) rounded down to an integer):
$$
a(n) = \begin{cases}
\text{between }2\left(\frac{n}3\right)^2+1\text{ and }2\left(\frac{n}3\right)^2+\frac{n}3&\text{if }n\text{ is a multiple of 3}\\
2\left\lfloor\frac{n+2}3\right\rfloor^2&\text{if }n\text{ is not a multiple of 3}
\end{cases}
$$
I've submitted the sequence I have so far to the OEIS: A379726.
Based on the terms computed above, I conjecture that \(a(3k)=2k^2 + k\). If you have any ideas how I could increase my lower bound, or for any other way I could prove this, let me know!
Edit: OEIS sequence is published!
×2 (Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
In attempting (and failing) to solve the puzzle when it first came out, I noticed that there were quite a few ways to colour the squares/place the kings for each minimum solution, some quite symmetrical and interesting. I wondered how many such "colourings" existed for each size of grid. And so because I apparently had nothing better to do over the weekend, I invested an inordinate amount of time coding up a script to bruteforce the number of colourings, and then a similarly inordinate amount of time optimizing it so I could get past a 5x5 grid. Here are the results:
2x2: 6
3x3: 2
4x4: 1296
5x5: 371
6x6: 8
Haven't been able to go any farther with my current script, but for what it's worth, here it is on GitHub.
2x2: 6
3x3: 2
4x4: 1296
5x5: 371
6x6: 8
Haven't been able to go any farther with my current script, but for what it's worth, here it is on GitHub.
Aaron
Here is my solution:
Project
Pre-built
Probably not super useful as I didn't attempt to prove my results, but I did come up with a general formula for odd-sized squares (with floor and ceiling functions), and perhaps the way I decoupled the two dimensions could be a useful approach for you.
Project
Pre-built
Probably not super useful as I didn't attempt to prove my results, but I did come up with a general formula for odd-sized squares (with floor and ceiling functions), and perhaps the way I decoupled the two dimensions could be a useful approach for you.
Dan Whitman
The conjecture is correct. Super-brief sketch proof: divide the grid into 3x3 boxes, aggregate those into horizontal and vertical strips of width 1 box = 3 squares; say a strip is "cheap" if it contains only 2k shaded squares (hence, exactly two per box). Working box by box from one end of a cheap strip to the other in both directions we see that the shaded squares must be in the middle transverse row/column of each box in such a strip. Hence there can't be both a cheap horizontal strip and a cheap vertical strip, because the box where they meet is overconstrained. So either all h-strips are not-cheap or all v-strips are not-cheap, and either of those gives you at least 2k2+k shaded squares.
(This, along with everything M.S. wrote, generalizes straightforwardly to arbitrary rectangular grids.)×1 ×3
(This, along with everything M.S. wrote, generalizes straightforwardly to arbitrary rectangular grids.)
g
×1 ×3 Add a Comment
2024-12-22
I showed off and part-solved a prototype version of this puzzle with Katie Steckles in the fifteenth Finite Group livestream.
You can watch a recording of this stream, and watch our future streams if you sign up to
our Patreon.
I clearly haven't already made enough Christmas puzzles this year, so I've made another one. If you've used regular expressions before, head straight to
mscroggs.co.uk/regexmas to try the puzzle. If you've not, read on...
What is a regular expression
Regular expressions are strings of characters that can be used in multiple programming languages to validate text.
Regular expressions are usually written between two
/ characters. Between the slashes, characters have the following meaning:^(not inside square brackets) means the start of the text.$means the end of the text.- A set of characters are written between
[and]means any of these characters.
For example, the regular expression - A set of characters are written between
[^and]means any character except one of these. For example, the regular expression/^[^df]$/matches any character except d or f. ?means the previous item may or may not appear. For example, the regular expression/^ab?c$/matches "ac" or "abc".+means the previous item can appear one or more times. For example, the regular expression/^ab+c$/matches "abc", "abbc", "abbbc", and so on.*means the previous item can appear zero or more times. For example, the regular expression/^ab*c$/matches "ac", "abc", "abbc", and so on.{and}with a number between means the previous item can appear this number of times. For example, the regular expression/^ab{4}c$/matches "abbbbc".|means either the stuff to the left or the stuff to the right. For example, the regular expression/^ab|c$/matches "ab" or "c"..means any character. For example, the regular expression/^ab|.$/matches "ab" or any single character.(and)can be used to group together other symbols. Groups in brackets can be later referred to by writing\1,\2, etc to refer to the first, second, etc bracketed group. For example, the regular expression/^(a|b)\1$/matches "aa" or "bb".
/^[abc]$/ matches "a", "b", or "c".
The puzzle
My regular expression Christmas puzzle is shown below. You can either solve it on this page or at mscroggs.co.uk/regexmas
using the buttons or your keyboard, or you can download
this PDF of the puzzle.
In the grid below, write r, g, b, c, m, y, k, or w in every square so that:
- each row (reading left to right) satisfies the regular expression to the right of the row;
- each column (reading top to bottom) satisfies the regular expression below the column.
The squares containing an r will be coloured red,
those containing a g will be coloured green,
those containing a b will be coloured blue,
those containing a c will be coloured cyan,
those containing an m will be coloured magenta,
those containing a y will be coloured yellow,
those containing a k will be coloured black, and those containing a w will be left white.
/^w+yw+$/
/^([kw]+)[^kw]\1$/
/^(g|wwwg|gww)+.$/
/^wy?g*y+w+$/
/^((w|gg)(ww|g)){3}$/
/^[wg](w|g)[gw](.)\2+\1{2}$/
/^.g*[^y]$/
/^([gk][gk][gk])\1\1$/
/^yw+kw+y$/
/^w*b(bb)+w*$/
/^(w+)w?(bb?)\2\2\1$/
/^(www|bbb)+$/
/^w+gyw+$/
/^[wg]*y[wg]*$/
/^.*gwg.*gwb.*$/
/^[^g]+g+[^g]+$/
/^y?g+y?g+k?b+$/
/^[w]+g*w[^w]+$/
/^w+g+wg+[^g]+$/
/^w*yw*g+w*$/
/^w*y?g?y?w*$/
(Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
Add a Comment
2024-12-04
As usual, I spent some time this November,
designing this year's Chalkdust puzzle Christmas card
(with some help from TD).
![](javascript:showlimage("card2024.jpg"))
The card contains 10 puzzles. By splitting the answers into pairs of digits, then drawing lines between the dots on the cover for each pair of digits (eg if an answer is 201304, draw a line from dot 20 to dot 13 and another line from dot 13 to dot 4), you will reveal a Christmas themed picture. Colouring any region containing an even number of unused dots green and colour any region containing an odd number of unused dots red or blue will make the picture even nicer.
If you're in the UK and want some copies of the card to send to your maths-loving friends, you can order them at mscroggs.co.uk/cards.
If you want to try the card yourself, you can download this printable A4 pdf. Alternatively, you can find the puzzles below and type the answers in the boxes. The answers will automatically be used to join the dots and the appropriate regions coloured in...
| 1. | What is the largest number you can make by using the digits 1 to 4 to make two 2-digit numbers, then mutiplying the two numbers together? | Answer |
| 2. | What is the largest number you can make by using the digits 0 to 9 to make a 2-digit number and a 8-digit number, then mutiplying the two numbers together? | Answer |
| 3. | The expansion of \((2x+3)^2\) is \(4x^2+12x+9\). The sum of the coefficients of \(4x^2+12x+9\) is 25. What is the sum of the coefficients of the expansion of \((30x+5)^2\)? | Answer |
| 4. | What is the sum of the coefficients of the expansion of \((2x+1)^{11}\)? | Answer |
| 5. | What is the geometric mean of all the factors of 41306329? | Answer |
| 6. | What is the largest number for which the geometric mean of all its factors is 92? | Answer |
| 7. | What is the sum of all the factors of \(7^4\)? | Answer |
| 8. | How many numbers between 1 and 28988500000 have an odd number of factors? | Answer |
| 9. | Eve found the total of the 365 consecutive integers starting at 500 and the total of the next 365 consecutive integers, then subtracted the smaller total from the larger total. What was her result? | Answer |
| 10. | Eve found the total of the \(n\) consecutive integers starting at a number and the total of the next \(n\) consecutive integers, then subtracted the smaller total from the larger total. Her result was 22344529. What is the largest possible value of \(n\) that she could have used? | Answer |
×10 ×9 ×4 ×5 ×5(Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
I enjoyed solving problems for this card very much! Thanks a lot! I had a great time!
Happy New Year! Greetings from Ukraine.
Happy New Year! Greetings from Ukraine.
Anna
Matt, great card this year! Problems 1 and 2 are slightly ambiguous though in that you did not specify that each digit could only be used once.
I initially thought the answers were simply 44×44 = 1936 and 99×99999999 = 9899999901, respectively ????×1 ×1
I initially thought the answers were simply 44×44 = 1936 and 99×99999999 = 9899999901, respectively ????
Dan Whitman
×1 ×1 I find that I can enter seven correct answers without issue. however, an eighth answer causes the entire tree to vanish.
I'm using Firefox on Windows 11.
I'm using Firefox on Windows 11.
hakon
@HJ: I can't reproduce that error on Firefox or Chrome on Ubuntu - although I did notice I'd left some debug outputting on, which I've now removed. Perhaps that was causing the issue.
If anyone else hits this issue, please let me know. ×1
If anyone else hits this issue, please let me know.
Matthew
×1 On my machine (Mac, using either Firefox or Chrome, including private mode so no plugins) the puzzle disappears when I complete the answers for 1, 3 and 9. I'm presuming my answers are correct -- the pattern they create is pretty clear and looks reasonable.
HJ
Add a Comment
2024-11-21
The mscroggs.co.uk Advent Calendar is back for its tenth year!
Behind each door, there will be a puzzle with a three digit solution. The solution to each day's puzzle forms part of a logic puzzle:
It's nearly Christmas and something terrible has happened: there's been a major malfunction in multiple machines in Santa's toy factory, and
not enough presents have been made. Santa has a backup warehouse full of wrapped presents that can be used in the case of severe emergency, but the warehouse is locked.
You need to help Santa work out the code to unlock the warehouse so that he can deliver the presents before Christmas is ruined for everyone.
The information needed to work out the code to the warehouse is known by Santa and his three most trusted elves: Santa is remembering a three-digit number,
and each elf is remembering a one-digit and a three-digit number. If Santa and the elves all agree that the emergency warehouse should be opened, they can work out the code for the door as follows:
- Santa tells his three-digit number to the first elf.
- The first elf subtracts her three-digit number then multiplies by her one-digit number. She tells her result to the second elf.
- The second elf subtracts his three-digit number then multiplies by his one-digit number. He tells his result to the third elf.
- The third elf subtracts their three-digit number then multiplies by their one-digit number. Their result is a five-digit number that is the code to unlock the warehouse.
But this year, there is a complication: the three elves are on a diplomatic mission to Mars to visit Martian Santa and cannot be contacted, so you need to piece together their
numbers from the clues they have left behind.
Behind each day (except Christmas Day), there is a puzzle with a three-digit answer. Each of these answers forms part of a clue about Santa's and the elves' numbers.
You must use these clues to work out the code for the warehouse.
You can use this page to try opening the door. If you enter an incorrect code three times, the door mechanism locks until the following day.
Ten randomly selected people who solve all the puzzles, open the warehouse, and fill in the entry form behind the door on the 25th will win prizes!
![](javascript:showlimage("prizes2018.jpg"))
The prizes will include an mscroggs.co.uk Advent 2024 T-shirt. If you'd like one of the T-shirts from a previous Advent, they are available to order at merch.mscroggs.co.uk.
The winners will be randomly chosen from all those who submit the entry form before the end of 2024. Each day's puzzle (and the entry form on Christmas Day) will be available from 5:00am GMT. But as the winners will be selected randomly,
there's no need to get up at 5am on Christmas Day to enter!
As you solve the puzzles, your answers will be stored. To share your stored answers between multiple devices, enter your email address below the calendar and you will be emailed a magic link to visit on your other devices.
To win a prize, you must submit your entry before the end of 2024. Only one entry will be accepted per person. If you have any questions, ask them in the comments below,
on Bluesky,
or on Mastodon.
If you'd like to chat with other solvers, we'll be discussing the Advent Calendar in the #scroggs-advent-calendar channel in the Finite Group Discord: you
can join the Discord by following the link in this post on Patreon (you'll need to become a free member
on Patreon to unlock the post).
So once December is here, get solving! Good luck and have a very merry Christmas!
×9 ×2 ×2(Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
I am so appreciative that you continue to make these puzzles every year. I think I started doing them in 2017 and always enjoy them. Thank you!×1
Jessica
×1 Thanks Scroggs - first time I've done this and very much enjoyed the days and also the meta-puzzling. Brilliant!!. If you run in future years I have one request for a tiny tweak - I find the numbers on the advent calendar for the days very small for my ageing eye-sight - any chance of a bigger font? And last suggestion - when it gets to the end, provide a link to your "buy me a cup of tea" page as this is more than worth a few £s :-). Thanks again :-)
×1
Justin
×1 @Seth Cohen: Thanks Seth, I solved it by looking at the 5×5 picture and thinking harder. Thanks to Matthew for another enjoyable set of puzzles. I look forward to reading the proper solution.
Reza
Had a great time doing this puzzles again this year! 23 was particularly fun :) Thanks for taking the time to make this!
Bill V.
I enjoyed working the advent puzzles. Thank you for providing such fun entertainment and math challenges! Attempted most without any programming help but some begged for a programming solution. Refreshed some former Python skills to happily solve a few puzzles. Looking forward to math solutions. Merry Christmas and Happy Holidays!×1
Tony
×1 Add a Comment