This week the #puzzle is: Happy (Almost) New Year from The Fiddler! #MagicSquare #primes
A magic square is a square array of distinct natural numbers, where each row, each column, and both long diagonals sum to the same “magic number.” ,,,
A prime magic square is a magic square consisting of only prime numbers. Is it possible to construct a 4-by-4 prime magic square with a magic number of 2026? If so, give an example; if not, why not?
And for extra credit:
Find all values of N for which it is possible to construct an N-by-N prime magic square with a magic number of 2026. (Remember, the numbers in a magic square must all be distinct!)
Example of a magic square with magic sum 2026: Example of a prime magic square with magic sum 240:
506
509
512
499
47
7
79
107
511
500
505
510
37
101
31
71
501
514
507
504
73
19
89
59
508
503
502
513
83
113
41
3
Based on the methods found on entertainmentmathematics.nl, I code my own “find a prime pan magic square, 4×4”. For a magic sum of 240, it correctly finds a solution (see example above). For 2026, it does not. There is no magic square of this kind. However, here’s a few others:
43
131
877
977
193
181
809
857
857
997
23
151
653
1013
37
337
137
37
971
883
211
163
827
839
991
863
157
17
983
683
367
7
And for extra credit:
Thoughts:
N odd won’t work, as the sum of (odd) primes has to be even.
N = 2 won’t work, as no magic square of any kind exists for N = 2.
We’ve already shown that N = 4 doesn’t work.
There are 305 primes below 2026. N = 18 and above won’t work, because 182 = 324.
This week the #puzzle is: Can You Topple the Tower? #geometry #trigonometry #CenterOfMass #integral
A block tower consists of a solid rectangular prism whose height is 2 and whose base is a square of side length 1. A second prism, made of the same material, and with a base that’s L by 1 and a height of 1, is attached to the top half of the first block, resulting in an overhang as shown below.
When L exceeds some value, the block tower tips over. What is this critical length L?
And for extra credit:
Instead of rectangular prisms, now suppose the tower is part of an annulus. More specifically, it’s the region between two arcs of angle 𝜽 in circles of radius 1 and 2, as shown below.
For small values of 𝜽, the tower balances on one of its flat sides. But when 𝜽 exceeds some value, the tower no longer balances on a flat side. What is this critical value of 𝜽?
Last week I was busy. ( #AdventOfCode ) I misread the description of the puzzle, and by the time I realized my error, I didn’t have enough time left to fix my mistake. So it goes.
Highlight to reveal (possibly incorrect) solution:
This week the #puzzle is: Can You Take the Heat? #combinatorics #coding #recursion
In the YouTube show, “Hot Ones,” guests answer interview questions while consuming 10 hot sauces, one at a time, ranked in increasing spiciness from 1 to 10.
You have been invited on as a guest and want to prepare for the show. However, you don’t feel like purchasing all 10 sauces in advance. Your plan is to purchase fewer sauces, and then to combine sauces together for any you are missing. For example, if you are missing sauce #7, then you can instead simultaneously consume sauces #3 and #4, since 3 + 4 = 7. (I know the spiciness of the sauces isn’t linear, but for the purposes of this puzzle, let’s assume it is.)
After some pencil-and-paper scratch work, you realize you only need four spices.
… for how many sets of four spice numbers is it possible to generate all the numbers from 1 to 10 using each spice at most once?
And for extra credit:
You’re prepping for a new show, “Hotter Ones,” which has spices ranked from 1 to 100. Let N be the minimum number of spices needed to generate all the numbers from 1 to 100.
For how many sets of N spice numbers is it possible to generate all the numbers from 1 to 100 using each spice at most once? (Note that I am not asking for the value of N; that’s just something you’ll need to figure out en route to your answer.)
First a note. No, this isn’t just the “how many different kinds of coins do you need for paying all amounts of money”, as a coin can be used more than one time. No, this isn’t just the “how many weights do you need for weighing all weights”, as that is done on a scale and a weight can be used to subtract from the total.
Thankfully it’s related to these problems, so they got me thinking in the right way.
How many sauces (or chilis) needed to get all strengths 1-10? ⌈log2(10)⌉ = 4. It might be the chilis 1, 2, 4 and 8.
Recursion is a beautiful way to look at the problem. To begin with, we need chili 1, otherwise we can’t get to a (combined) strength of 1. Likewise, we need chili 2, otherwise we can’t get to a (combined) strength of 2. (1 + 1 isn’t allowed.) With chilis 1 and 2, we have access to combined strengths 1, 2 and 3 (and 0 — no chilis).
Choice A1: skip chili 3 and go straight to chili 4.
Choice B1: skip chili 4 and go straight to chili 5.
…
Choice B2: add chili 4.
Choice C1: skip chili 5 and go straight to chili 6.
…
Choice C2: add chili 5.
…
Choice A2: add chili 3.
Choice B1: skip chili 4 and go straight to chili 5.
…
Choice B2: add chili 4.
Choice C1: skip chili 5 and go straight to chili 6.
…
Choice C2: add chili 5.
…
The next step is to try adding chili 3. (A2.) With chilis 1, 2 and 3, we have access to strengths 1, 2, 3, 4, 5 and 6 (and 0). We already had access to 0-3. Now we also have access to 0+3 (actually we already had that one), 1+3, 2+3 and 3+3. The recursion bit is to then go on to try adding chili 4. (A2B2.)
The alternative to adding chili 3 is not to do it. (A1.) We then again try adding chili 4. (A1B2.) Or not. (A1B1.)
This is what I do in my program. When I have a bunch of chilis giving me all the strengths 1-10, I count it.
A lot of the puzzles I could solve within an hour. There are on the other hand 4 part 3s I spent a lot of time on or haven’t solved yet. My personal times:
This week the #puzzle is: A Loopy Holiday Gift Exchange #probabilities #coding #montecarlo #combinatorics
You are participating in a holiday gift exchange with your classmates. You each write down your own name on a slip of paper and fold it up. Then, all the students place their names into a single hat. Next, students pull a random name from the hat, one at a time. If at any point someone pulls their own name from the hat, the whole class starts over, with everyone returning the names to the hat.
Once the whole process is complete, each student purchases a gift for the classmate whose name they pulled. Gifts are handed out at a big holiday party at the end of the year.
At this party, you observe that there are “loops” of gift-giving within the class. For example, student A might have gotten a gift for B, who got a gift for C, who got a gift for D, who got a gift for A. In this case, A, B, C and D would form a loop of length four. Another way to have a loop of length four is if student A got a gift for C, who got a gift for B, who got a gift for D, who got a gift for A. And of course, there are other ways.
If there are a total of five students in the class, how likely is it that they form a single loop that includes the entire class?
And for extra credit:
If there are N students in the class, where N is some large number, how likely is it that they form a single loop that includes the entire class, in terms of N? (For full credit, your answer should be proportional to N raised to some negative power.)
If we had no bounds, there would be 5! = 120 ways to distribute the names.
The 1st bound is, that permutations where a person draws their own name are discarded. This also means the surviving permutations have no cycles of length 1. (Terminology and example calculations: Wikipedia.)
The 2nd bound is, that we want to compare permutations with a cycle of length 5 to those without, to calculate a probability.
How many permutations without cycles of length 1?
A permutation like that might consist of 2 cycles, 1 of length 2, 1 of length 3.
There are C(5,2) * 1! * 2! ways this can be done.
C(5,2) different ways to choose the 2 names for the 2 cycle.
1! = 1 way to permutate them, so that no person draws their own name.
The remaining names can be permutated in 2! = 2 ways.
C(5,2) * 1! * 2!
= 5*4/2*1 * 1 * 2
= 10 * 2
= 20
The bound means no cycle of length 4, because then the other cycle would have length 1.
A valid permutation might have a cycle of length 5.
There are C(5,5) * 4! ways this can be done.
C(5,5) = 1 — we have to choose all the names.
4! = 24 ways to permutate these names, without a person drawing their own name.
In all 20 + 24 = 44 ways to permutate the names, and 24 ways to achieve a 5 cycle.
24/44 = 0.545454545.
A monte carlo program roughly confirms this number.
I expand the program to look at other N’s. An analysis in Desmos suggests, that the formula should be 2.75 * N-1. If N = 5, this is 0.55. (Might 2.75 actually be e = 2.72? Hard to tell.)
This next bit will make much more sense if you are actually familiar with part 3. If you haven’t solved it yourself, you might want to look at this description.
Quest 11, part 3 has been described this way:
“Key insight 2 is that each round in a phase effectively only moves one duck from one column to another. Key insight 3 is that in phase 2, when a column get the number of ducks each column ends with, it will never get more/less (it won’t fluctuate). In other words, the number of ducks per column in phase 2 is either monotonically increasing or monotonically decreasing.” Source
“If you know that it is sorted, and effectively, every turn one duck moves from the “large” half to the low half, then how many ducks have to be moved to have exactly equal columns in the end?” Source
“Phase 2 brings the columns to equilibrium using a left to right flood of deficits. If the left column is smaller than the right, then a single duck moves to the left. When applied across the full range of columns in a single round, the smallest column (which must be on the left) gains a duck and the largest column (which must be on the right) loses a duck. The only way it’s not possible for a duck to move is if the columns are at equilibrium.” Source
Maybe I am dumb and just don’t see, that b actually follows from a.
Maybe I needed more than intuition and “when I used this method, I got the correct result”.
Anyway. I have tried writing a proof.
We have some columns of ducks.
a b c d e f g
a <= b <= c etc.
The average of a-g is x We can insert |, so that e.g. c <= x < d
a b c | d e f g
WHAT HAPPENS BEFORE |?
Choose the first among a-c (they are left of |), so that the chosen one is strictly smaller than the one to its right. Call this candidate m.
So we might have
a b c | d … (a < b) b b c | d … (a = b < c) c c c | d … (a = b = c < d)
Notice that it is always possible to choose m.
We might have
m b c | d …
In that case the next step is
m+1 b-1 c | d …
As b <= c, it follows that b-1 < c, and the next step is
m+1 b c-1 | d …
This goes on until we reach c and d.
m+1 b c | d-1 …
IMPORTANT: m grows 1, d-g shrinks 1. IMPORTANT: the list is still sorted. See below what happens when c = d.
We might also have
m m c | d …
In the first round we get 1 or more steps bringing us to this
m m+1 c | d-1 …
In the next round this becomes
m+1 m+1 c | …
IMPORTANT: each m grows 1, d-g shrinks accordingly. IMPORTANT: given z m’s, each m grows 1, d-g shrinks z. IMPORTANT: the list is still sorted after each round.
WHAT HAPPENS AFTER |?
Choose the last among d-g, so that the chosen one is strictly larger than the one to its left. Call this candidate n.
So we might have
… c | d e f g (f < g) … c | d e f f (e < f = g) … c | d e e e (d < e = f = g) … c | d d d d (c < d = e = f = g)
Notice that it is always possible to choose n.
We might have a step, right after d shrinking.
… | d-1 e f n
In that case we go through these steps.
… | d e-1 f n … | d e f-1 n … | d e f n-1
IMPORTANT: d goes back to d, n shrinks 1
We might have
… | d-1 e n n
In that case we go through these rounds
… | d e n n-1 … | d e n-1 n-1
IMPORTANT: d goes back to d, each n shrinks 1. IMPORTANT: given y n’s, each n shrinks 1, a-c grows y. IMPORTANT: the list is still sorted after y rounds.
We might have
… | n-1 n n n
In that case we end up here after a round
… | n-1 n-1 n-1 n-1
IMPORTANT: d goes to d-1 = n-1, each n shrinks 1. See below what happens when c = d. Otherwise we keep the property that c < d. IMPORTANT: given y n’s, each n shrinks 1, a-c grows y. IMPORTANT: the list is still sorted after y rounds.
To sum up:
We begin with a sorted list. A duck crosses the | in each round. The list before | will stay sorted. The list after | will stay sorted or go back to being sorted after a finite number of steps.
We are headed to a situation looking like
m m m | n n n n
or something similar.
This process ends when m = n = x. 1 round before the end we had something like
m-1 m m | n+1 n n n
All the way through the process, c < d. (Ending with m < n+1.)
Maybe all of this is easier to understand watching an example.
This week the #puzzle is: Can You Irrigate the Garden? #probabilities #geometry #trigonometry #average #integration
You and your assistant are planning to irrigate a vast circular garden, which has a radius of 1 furlong. However, your assistant is somewhat lackadaisical when it comes to gardening. Their plan is to pick two random points on the circumference of the garden and run a hose straight between them.
You’re concerned that different parts of your garden—especially your prized peach tree at the very center—will be too far from the hose to be properly irrigated.
On average, how far can you expect the center of the garden to be from the nearest part of the hose?
And for extra credit:
As before, your assistant intends to pick two random points along the circumference of the garden and run a hose straight between them.
This time, you’ve decided to contribute to the madness yourself by picking a random point inside the garden to plant a second peach tree. On average, how far can you expect this point to be from the nearest part of the hose?
My second was to use integration. I convert from “2 random points” to “1 random point and 1 fixed in a nice way” to “2 random points but with similar angles”. That way the integral is nicer.
This week the #puzzle is: The Randy Hall Problem #probabilities #MontyHall
You are a producer on a game show hosted by Randy “Random” Hall (no relation to Monty Hall). The show has three doors labeled 1 through 3 from left to right, and behind them are various prizes.
Contestants pick one of the three doors at which to start, and then they press an electronic button many, many times in rapid succession. Each time they press the button, they either stay at their current door or move to an adjacent door. If they’re at door 2 and move to an adjacent door, that new door will be 1 or 3 with equal probability.
Randy has decided that when a contestant presses the button while at door 2, there should be a 20 percent chance they remain at door 2.
As the producer, you want the chances of a contestant ultimately winding up at each of the three doors to be nearly equal after many button presses. Otherwise, mathematicians will no doubt write you nasty letters complaining about how your show is rigged.
If a contestant presses the button while at door 1 (or door 3), what should the probability be that they remain at that door?
And for extra credit:
Randy has an updated suggestion for how the button should behave at door 2. What hasn’t changed is that if a contestant at door 2 and moves to an adjacent door, that new door will be 1 or 3 with equal probability.
But this time, on the first, third, fifth, and other odd button presses that happen to be at door 2, there’s a 20 percent the contestant remains at door 2. On the second, fourth, sixth, and other even button presses that happen to be at door 2, there’s a 50 percent chance the contest remains at door 2.
Meanwhile, the button’s behavior at doors 1 and 3 should in no way depend on the number of times the button has been pressed.
As the producer, you want the chances of winding up at each of the three doors—after a large even number of button presses— to be nearly equal.
If a contestant presses the button while at door 1 (or door 3), what should the probability be that they remain at that door?
This week the #puzzle is: How Much Does Game 1 Matter? #probabilities #combinatorics #PascalsTriangle #animation
You and your opponent are beginning a best-of-seven series, meaning the first team to win four games wins the series. Both teams are evenly matched, meaning each team has a 50 percent chance of winning each game, independent of the outcomes of previous games.
As the team manager, you are trying to motivate your team as to the criticality of the first game in the series (i.e., “Game 1”). You’d specifically like to educate them regarding the “probability swing” coming out of Game 1—that is, the probability of winning the series if they win Game 1 minus the probability of winning the series if they lose Game 1. (For example, the probability swing for a winner-take-all Game 7 is 100 percent.)
What is the probability swing for Game 1?
And for extra credit:
Instead of a best-of-seven series, now suppose the series is much, much longer. In particular, the first team to win N games wins the series, so technically this is a best-of-(2N−1) series, where N is some very, very large number.
In the limit of large N, what is the probability swing for Game 1 in terms of N? (For full credit, I’m expecting an answer that is rather concise!)
Let’s first go through all the probabilities. I begin with the probabilities related to 7 played games, then 6 etc. In each case I calculate the probability based on a) the chance of winning a game is 0.5, b) the probabilities related to winning if this game is won/lost.
(1) The series is decided with a win. (2) The series is decided with a loss. (3) The series is decided in the last game, 50/50.
It is reassuring, that pw(a,a) = 0.5.
ps(1) = pw(1,0) – pw(0,1)
ps(1) = 0.65625 – 0.34375 = 21/32 – 11/32
ps(1) = 0.3125 = 5/16
Win the 1st game, and the probability of winning the series rises by more than 30%.
Another set of thoughts:
My pdf shows a few ways to look at this problem. A full series walks through this graph (page 1), starting at (0,0) and ending at some (4,b) or (a,4).
Page 2 tilts the graph.
If I extend the graph to include all the series, that have 7 games (e.g. (5,2)), what I’m looking at here is actually all the paths from (0,0) to any state with 7 played games. (See video above.) E.g. the path from (0,0) to (5,2) could go through (0,1), (1,1), (2,1), (2,2), (3,2) and (4,2). In reality, the 7th game wouldn’t be played, but for analysis purposes I need both paths going beyond (4,2) — the one going to (5,2) and the one going to (4,3).
A win is a path with at least 4 wins.
How many paths are there with 7 wins? 1.
How many paths are there with 6 wins? 7.
… 5 wins? 7!/5!2! = 21.
… 4 wins? 7!/4!3! = 35.
But the question was actually, how many paths are there, beginning in (1,0), with 4-7 wins? So, 3-6 wins out of 6.
1 + 6 + 6!/4!2! + 6!/3!3! = 1 + 6 + 15 + 20 = 42
Also, counting losses:
1 + 6 + 6!/4!2! = 1 + 6 + 15 = 22
There are 26 = 64 paths in all
The probability of winning from (1,0), pw(1,0), is 42/64 = 21/32 = 0.65625. This checks out.
For symmetry reasons, the probability of losing from (0,1) is also 0.65625 (it’s the probability of the other side winning from a similar position as already analyzed), so the probability of winning, pw(0,1), is 0.34375.
What we also see here is pw(1,0) – pw(0,1) = ((1 + 6 + 15 + 20) – (1 + 6 + 15)) / 26 = 20/26.
In a first to 4 / best of 7 game, ps(1) = 6!/3!3! / 26.
In a first to N / best of 2N-1 game, ps(1) = (2N-2)! / [((N-1)!)2 * 22N-2].
BTW, we have reproduced a couple of lines of Pascal’s Triangle.
Stuff from ommadawn.dk (Lise Andreasen) 