Can you solve this crossword where all hints are regular expressions?
At EuroPython 2024 I watched a lightning talk about the art of puzzle solving. In it, the speaker showed the regex crossword puzzle that you can see above, that I took from this URL. You are supposed to fill the hexagonal grid with letters so that all of the regular expressions shown match.
If you don't know regular expressions, the puzzle only uses a simple subset of the syntax:
.
;|
;?
, +
, and *
;[...]
and negated character sets with [^...]
; and()
and group references with \1
, \2
, etc.You can look this up and then you will be able to solve the challenge. You can also use the site regex101 to help you check what each regular expression means.
Give it some thought!
In the spirit of the puzzle hunting community, I will not share my solved grid here. If you need help, feel free to email me and we can talk it over.
P.S. if I understood correctly, in the puzzle hunting community you're not supposed to just fill in the grid. In some way, somehow, you are supposed to be able to extract an English word or phrase from that filled puzzle without any extra information, and then you check that you got it correctly by “checking your answer spoiler-free” in the website where I took the regex crossword from I am still stuck in that step!
]]>When will these two clocks synchronise again?
You have two digital clocks. One of them just displays the hours and minutes in the format HH:MM while the other is a stopwatch that displays minutes and seconds in the format MM:SS. The stopwatch wraps around at 59:59, when it goes back to 00:00.
On a certain day at 00:00, the stopwatch is turned on. When will the clock and the stopwatch have matching displays again? And how often does that happen?
Give it some thought!
The two clocks will have matching displays again at 01:01:01, then again at 02:02:02, 03:03:03, 04:04:04, ..., 23:23:23, so this happens 24 times per day.
To get to this conclusion, we start by realising that the stopwatch can actually be seen as a clock that shows the current time, but without the hours. Thus, the minutes display of the regular clock will always match the minutes display of the stopwatch.
To recap, the two clocks have displays in the format HH:MM and MM:SS and we already know that the MM sections always match. This means that for the two displays to display the same thing, we must have HH = MM = SS, which happens at 00:00:00, 01:01:01, ..., up to 23:23:23.
What if the stopwatch wraps around at 99:59 instead of 59:59?
]]>How can an infinite number of mathematicians figure out their own hat colours?
An infinite number of mathematicians are standing in a line. In a couple of minutes, a disruption in the space-time continuum will cause a black or white hat to appear on the head of each mathematician. After that happens, the mathematicians will try to guess their own hat colour (they can't see it) based on the colours of the hats of all other mathematicians.
What's the strategy that the mathematicians must agree on, before hand, so that only a finite number of mathematicians guesses wrong?
Give it some thought!
When we look at each matematician's hat we can create a sequence of \(0\)s and \(1\)s. For example, if everyone has a white hat except for the first three mathematicians, then we would have the sequence \((1,1,1,0,0,\cdots)\).
Let us say two sequences are alike if they are the same except for a finite number of positions. As an example, the sequence we get when all mathematicians have a white hat and the previous sequence are alike because they differ only in the first three positions: \((\underline{0}, \underline{0}, \underline{0}, 0, 0,\cdots)\).
For any sequence \(S\) we can think of all the other sequences with which \(S\) is alike. Let us call that group of alike sequences \([S]\). What the mathematicians must do is: for every single group \([S]\) they must pick a random sequence from that group and memorise it.
When they are given the hats, they must look at their colleagues and figure out in which group \([S]\) their hat sequence belongs. Then, they will recall the sequence they all memorized from that group and each mathematician will say that their hat is of the colour corresponding to their position on the memorized sequence. By definition, only a finite number of mathematicians guesses wrong because the sequence they will recreate and the real sequence are alike, i.e. they differ only in a finite number of positions.
]]>Can you prove that there are arbitrarily many primes in arbitrarily big intervals?
The problem statement asks you to prove that for any positive integer number \(k\) you can think of, there will be a certain lower bound \(n_0\) (that depends on \(k\)) such that for any integer \(n \geq n_0\), there is an interval of length \(n\) that contains exactly \(k\) primes. (When we talk about the length of the interval, we are talking about how many integers it contains.)
If the statement confused you a bit, that is ok. Let me rephrase it.
You and I will play a game. I will think of a positive integer \(k\). Now, your job is to come up with another positive integer \(n_0\) such that, if I pick a number \(n\) greater than \(n_0\), you can always find an interval of size \(n\) that contains \(k\) primes.
For example, if I thought of \(k = 5\), you could not pick \(n_0 = 4\). Why not? Because if I pick \(n = 4\), there is no interval of length \(4\) that contains \(5\) prime numbers... Especially because an interval of length \(4\) contains only \(4\) integers!
This problem was posed to me by my mathematician cousin and I confess that worried me a bit. Funnily enough, the problem has a surprisingly simple solution. (I am not saying you will get there easily. I am just saying that once you do, you will realise the solution was not very complicated.)
Give it some thought!
Remember:
Congratulations 🎉 to everyone who managed to solve this problem: Congratulations to you if you managed to solve this problem correctly! If you did, feel free to
If you managed to solve this problem, you can add your name to the list! You can also email me your solution and we can discuss it.
A thing I like about this problem is that not only can you prove that interesting statement about the prime numbers, but you can also determine exactly what the lower bound \(n_0\) is.
Let us say that \(p_k\) is the \(k\)-th prime. Then, if we set \(n_0 = p_k\), we are good to go. Let me show you why.
Suppose that \(n\) is any integer \(n \geq n_0\). Then, the interval \([1, n]\) contains \(p_k\) in it. Why? Because \(p_k = n_0\) and \(n \geq n_0\).
So, the interval \([1, n]\) contains \(k\) or more prime numbers. If it contains \(k\) prime numbers, we just found our interval of length \(n\) that contains exactly \(k\) primes. If it contains more than \(k\) primes, we must do something about it.
If the interval \([1, n]\) contains more than \(k\) prime numbers, then we start sliding the interval to the right, like so:...
]]>Can you align all of the coins on the right edge of the board?
The diagram above shows a 3 by 4 grid with 3 coins, one per row and one per column, such that the rightmost column of the grid is empty.
You are allowed to slide the coins to the columns on their right, but the coins can never leave the board (nor can they be moved back to the left). Also, you always have to move two coins at a time.
Thus, this is a legal move:
But moving a single coin, such as in the diagram below, is not allowed:
Your objective is to reach this position:
Can you do it?
What if you extend the board two columns to the left and two rows up, and add another two coins along the diagonal?
Give it some thought!
This is an adaptation of a problem from the book “Algorithmic Puzzles” by Anany Levitin and Maria Levitin.^{1}
Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:
Know how to solve this? Join the list of solvers by emailing me your solution!
You can move all coins to the right in 3 moves:
This diagram shows the evolution of the grid:
X . . . start
. X . .
. . X .
. X . . >
. X . .
. . . X >
. . X . >
. . X . >
. . . X
. . . X >
. . . X >
. . . X
If we extend the board up and left, we'd have this starting configuration:
X . . . . .
. X . . . .
. . X . . .
. . . X . .
. . . . X .
Now, consider the total number of spaces to the right of the coins:
X 1 2 3 4 5
. X 6 7 8 9
. . X 0 1 2
. . . X 3 4
. . . . X 5
We see that there are 15 spaces on the grid to the right of coins. We also know that each time we move two coins, the number of spaces to the right of the coins decreases by 2. Now, if we were to align all coins on the rightmost column, the number of spaces to the right of the coins would be 0. However, we can't...
]]>Three mathematicians discuss a beautiful flower garden and the coloured flowers within.
Three mathematicians were discussing a beautiful flower garden. The first mathematician said:
“It's a beautiful garden. All flowers are either red, yellow, or blue... And whatever three flowers you pick, one of them is bound to be red.”
The second mathematician said:
“It is indeed a beautiful garden! There are red flowers, yellow flowers, and blue flowers! I also noticed that, whatever three flowers you pick, one of them is bound to be yellow.”
The third mathematician, who had never been to the garden, remarked:
“That's interesting! If that's true, I can say that, whatever three flowers I pick, one of them is bound to be blue!”
The first two mathematicians glanced at each other and smiled.
Is the third mathematician right? Or wrong? Why?
Give it some thought!
This problem is from the amazing [book “To Mock a Mockingbird”][mock-mockingbird] by the mathematician Raymond Smullyan.^{1}
Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:
Know how to solve this? Join the list of solvers by emailing me your solution!
The third mathematician is right.
The first sentence of each mathematician establishes that all flowers in the garden are one of three colours (red, yellow, blue) and that all colours are represented; that is, there is at least one red flower, at least one yellow flower, and at least one blue flower.
Then, the first mathematician says that whatever three flowers you pick, one is bound to be red. This means that the garden cannot contain three or more flowers that are not red. After all, if there were, say, two yellow flowers and one blue flower, you could pick those three and there wouldn't be a red flower in there.
At the same time, we know there has to be at least one yellow flower and one blue flower, so we conclude the garden has an unknown number of red flowers, one yellow flower, and one blue flower.
Then, the second mathematician speaks! From their remark, we could make a similar independent conclusion: the garden has an unknown number of yellow flowers, one red flower, and one blue flower.
Thus, if we combine the two conclusions, we get that the garden has three flowers only:
Therefore, the third mathematician is also right: whatever three flowers you pick, one is bound to be blue.
Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox.
This is an Amazon Affiliate link and I may earn a commission if you purchase the book. This comes at no extra cost to you. ↩
Two realtors discuss who's netting the award for highest average commission, but it isn't clear who the winner is...
Alice and Bob are two realtors that work at the same premium real estate agency, WSH. Because WSH really wants to focus on selling premium properties, they instated a monetary prize that is awarded every two years to the realtor that has the highest average commission over the past two years.
The award for the years 2020 and 2021 is being attributed soon. One day, at the office, Alice overheard Bob gloating:
“I can't wait to get my money! I already know what I'll be doing with it!”
Alice turned to Bob and asked:
“How can you be so sure that you are the one netting the prize?”
Bob smirked and returned:
“I guess you haven't been paying attention, Alice! In 2020 I was the realtor with the highest average commission over that year... And in 2021 I did it again!”
Alice smiled and returned to work.
Who do you think is right? Is Bob definitely getting the award? Or is there a scenario in which Alice gets the prize?
Give it some thought!
Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:
Know how to solve this? Join the list of solvers by emailing me your solution!
Bob is wrong because there is a scenario in which Alice can win the award... Even though Bob had the highest average commission both in 2020 and 2021. Does this seem counterintuitive? Because it is... This is an instance of the Simpson's Paradox.
To paint a clearer picture of how the Simpson's Paradox comes about, I will create a fairly extreme hypothetical scenario:
Suppose that Alice and Bob are the only realtors working for WSH, so that we don't have to care about anyone else.
Suppose that, in 2020, these were the commissions each one made:
Furthermore, suppose that, in 2021, these were the commissions each one made:
Here is a table summarising the average commission each one of them made for each year:
2020 | 2021 | |
---|---|---|
Alice | \(\frac{1 \times 10000}{1} = 10000\) | \(\frac{1000 \times 20000}{1000} = 20000\) |
Bob | \(\frac{1 \times 10005}{1} = 10005\) | \(\frac{1 \times 20005}{1} = 20005\) |
As we can see, Bob has a higher average commission in 2020... But also in 2021!
However, if we add a third column for 2020 and 2021 combined, everything becomes clear:
2020 | 2021 | 2020 + 2021 | |
---|---|---|---|
Alice | \(\frac{1 \times 10000}{1} = 10000\) | \(\frac{1000 \times 20000}{1000} = 20000\) | \(\frac{1 \times 10000 + 1000 \times 20000}{1001} \approx 19990\) |
Bob | \(\frac{1 \times 10005}{1} = 10005\) | \(\frac{1... |
How can you swap the coloured pegs if they can only march forward?
Imagine seven round slots:
O O O O O O O
In the three left slots, you have Yellow pegs:
Y Y Y O O O O
In the three right slots, you have Green pegs:
Y Y Y O G G G
You have to swap the yellow pegs and the green ones, but of course there are some restrictions to what you can do:
So, for example, in the configuration below, the green peg can move to the marked slot by jumping over a yellow peg:
G Y O
^ ^
As another example, in the situation below, no peg can move:
O G G Y Y O
With these restrictions, can you swap all pegs? That is, can you move the pegs so that all green pegs end up on the left and all yellow pegs end up on the right?
Give it some thought!
You can try playing this out yourself: grab 6 coins and lay them in a straight line on a table. 3 coins on the left with the tails face up and the other 3 coins on the right with the other face up.
If you need any clarification whatsoever, feel free to ask in the comment section below.
This problem is based off of the puzzle you can see in the thumbnail picture, which you can play at Icon Park's Museum of Illusions.
Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:
Know how to solve this? Join the list of solvers by emailing me your solution!
To solve this problem, my best suggestion is to go one move at a time, and to try and think ahead 2 or 3 moves each time you are about to do something. You don't need to look ahead too much to be able to tell if a move is a bad idea or not.
With that said, that can be easier for some and harder for others!
I will share one possible solution below. Each line represents the positions of the pegs after one single move. But first, let me show you a video shared on Twitter where one of you solved this problem with candy:
]]>G1 forward, Y1 hop, Y2 forward, G1 hop, G2 hop, G3 forward, Y1 hop, Y2 hop, Y3 hop, G1 forward, G2 hop, G3 hop, Y2 forward, Y3 hop, G3 forward,...
Please help me identify these 100 light bulbs by turning ON and OFF their switches.
I have a very peculiar room in my house. It's a simple room that doesn't have much decoration. However, I do have 100 light bulbs hanging from the ceiling because I thought it would look cool. When I installed the 100 light bulbs I wanted maximum freedom, so I also installed 100 independent switches:
Of course I was completely silly, so I installed the switches in a room that is far from the room with the light bulbs and I completely forgot which light switch controls which light bulb. How can I identify which switch controls which light bulb in the least amount of trips possible?
For example, I could flip ON a switch and then go verify which light bulb turned ON, and I could do this for the 100 light bulbs... But that would take me 100 trips.
Give it some thought!
If you need any clarification whatsoever, feel free to ask in the comment section below.
This problem was adapted from here and is licensed under CC BY-SA 3.0.
Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:
Know how to solve this? Join the list of solvers by emailing me your solution!
We can devise a strategy that identifies \(2^n\) light bulbs in \(n\) trips making use of binary.
In short, what we do is number each switch in binary. Suppose the longest binary number has \(k\) digits. Then, we do \(k\) trips and for each trip \(t\) we turn ON the switches whose binary expansions have a \(1\) in the corresponding position. After the \(k\) trips, the times at which each light bulb was on will correspond to the binary expansion of its switch.
As an example, suppose we have 4 light bulbs and 4 switches. We number the four switches in binary:
This means that for the first trip we only turn ON switches 2 and 4, and for the second trip we only turn ON the switches 3 and 4. As two example associations, the light bulb associated with the switch 4 is the light bulb that was turned ON both times and the light bulb associated with the switch 1 is the light bulb that was turned OFF both times.
For 100 light bulbs, the largest binary number will be \(1100011\) (for 99), which means we'll need 7 trips.
Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox.
]]>Can you find the centre of the circle with just five lines?
Suppose you have a circle, like the one in the figure below. At your disposal, you have a compass, a straightedge (like a ruler, but without length ticks), and a pencil.
Can you find the centre of the circle with just five lines? (Every time you use the compass counts as one line, and every time you use the straightedge counts as another line.)
Give it some thought!
If you need any clarification whatsoever, feel free to ask in the comment section below.
Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:
Know how to solve this? Join the list of solvers by emailing me your solution!
There are many ways in which the centre of the circle can be found! However, doing that with just 5 lines is the challenge.
Recall that the centre of the circle is the point that is at the same distance of all the points in the circumference. So, if you draw any chord and then draw its bisector, you know that bisector will go through the centre of the circle (point A in the figure):
In the figure above, I picked two arbitrary points D and E and drew the chord [DE]. Then, I used D and E two draw to circles:
Then, the line defined by the two intersections of those two circles goes through the centre (A). If we do that once more, the intersections of those two bisectors give you the centre:
However, this uses a total of 8 lines. We want to do this in just 5... And yet, going down to 6 lines is easy: we just need to realise we don't really care about the chords, only their endpoints... And picking arbitrary points on the circumference doesn't cost any “lines”:
The final step comes from realising that we don't need 4 separate circles! The two bisector lines of the implied chords can be drawn with just 3 circles if we pick the points well enough!
After drawing the first two auxiliary circles, pick one of the circles. That circle will intersect the original circle at a point that you haven't used yet (H in the figure below). Use that point as the centre of the third circle, which you can draw with a radius equal to the other two auxiliary circles:...
]]>