This week the #puzzle is: Happy 100th Fiddler! #counting #permutations #triangles #parallelograms #dozo #flag

Dozo is a strategy game with a rather distinctive board:

The board features 28 holes in which players place markers, with the goal of making an equilateral triangle of any size with one color.

How many distinct equilateral triangles can you find whose vertices are the centers of holes on the board? (If two triangles are congruent but have different vertices, they should still be counted as distinct.)

And for extra credit:

Happy Fourth of July! In celebration of America’s birthday, let’s count more shapes—not in a board game, but in the American flag:

In particular, consider the centers of the 50 stars depicted on the flag. How many distinct parallelograms can you find whose vertices are all centers of stars? (If two parallelograms are congruent but have different vertices, they should still be counted as distinct.)

Highlight to reveal (possibly incorrect) solution:

Program Handcount 1 and 2

I tried counting triangles both by hand and with a program. The handcount illustrated is actually a little wrong, because in a certain case (6 + 6) I forgot to count the triangles, where the tip pointed up. The program goes through all the options for the 1st and 2nd vertex, constructing the 3rd and testing whether this hypothetical 3rd is on the board. This was a little tricky, because my model of the board didn’t preserve angles and distances from the board. But I think I got there in the end. Result: 126 triangles.

And for extra credit:

Program

This time I went straight to the program. It goes through all the options for 3 vertices, constructing the 4th. There’s actually a charming set of formulas for constructing the 3 options for the 4th vertex. This time it didn’t matter that angles and distances weren’t preserved. Only tricky part was to detect, when the 1st, 2nd and 3rd vertex were on a line. Result: 5918 parallelograms.

***

For the 3rd time I’ve come back to weaving the web. This time because a friend kindly helped me turn a 3d object file into a physical object:

This week the #puzzle is: Can You Crack the Roman Code? #combinations #recursion (Link at the bottom.)

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Tribonacci numbers Program

What do we know?

1. If the scroll had 1 * I, there would be 1 solution.
2. If it had 2, there would be 2 solutions, (I,I) and (II).
3. If it had 3, there would be 4 solutions, (I,I,I), (II,I), (I,II) and (III).
4. If it had 4, there would be 3 cases:
   • All the solutions for 3 * I with (I) added.
   • All the solutions for 2 * I with (II) added.
   • All the solutions for 1 * I with (III) added.
5. So this should be 4 + 2 + 1 = 7 solutions.
6. In general it’s the case, that the number of solutions f(n) = f(n-1) + f(n-2) + f(n-3).
7. These are actually the tribonacci numbers.
8. f(10) = a(12) = 274.

Just to make sure, I also wrote a recursive program to do the actual search through the tree of possibilities. Same answer.

And for extra credit:

Spreadsheet

Good thing I wrote that program! I can simply use it again. It says there are 4000 solutions.

Just to make sure, I also made a spreadsheet, counting in another way. Same result. I am happy.

***

Last week I actually didn’t do that well. I made a lot of assumptions, and some of them were wrong. In both puzzles my pass no. 2 didn’t correspond with the official solution. I’ve discovered, that for the fiddler this happened, because I made a mistake in my calculations. The area of my tilted 2nd pass is not 1.0472, but 0.7585. Oops.

***

Can You Crack the Roman Code?

This week the #puzzle is: How Greedily Can You Mow the Lawn? #geometry #area #volume #GreedyAlgorithm (Link at the bottom.)

You’re mowing a circular lawn with a radius of 1 unit. You can mow in straight strips that are 1 unit wide.

The fewest number of passes you would need to mow the entire lawn is two, as shown below. In one pass (shown in blue) you can mow half the circle, and in the second pass (shown in red) you can mow the other half of the circle.

However, instead of minimizing the number of passes, you greedily choose how to orient each pass so it cuts as much of the unmowed grass as possible. A pass doesn’t have to go through the center of the circle and can be in any direction, but must be straight and cannot bend.

With this “greedy” approach, how many passes will it take for you to mow the entire lawn?

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Desmos 1

Let us go through what choices we have.

• Obviously the 1st pass is simply symmetrical, the middle of the pass going through the center. If it didn’t go through the center, it would cover less area. In my model this pass is horizontal.
• The 2nd pass might simply be the same, just in the other direction? It would get a lot of the 2 remaining bits, leaving 4 bits behind. If this pass is indeed vertical, again, the middle of it goes through the center, to cover as much area as possible. This area would be 0.9132. [ETA: Oops, should be 2 * 0.9132. Wrong conclusions follow.]
• Then I would need 2 passes to cover the remaining 4 bits, either 2 horizontal (or vertical) passes, covering 2 bits every time, or 2 passes crisscrossing, one going up, the other going down, again covering 2 bits every time.
• That would be 4 passes in all.
• Can it be done in a better way?
• I need at least 3 passes, because I can’t cover the 2 remaining bits after the 1st pass in just 1 more pass.
• What if the 2nd pass simply covered 1 of the remaining bits? This area turns out to be 0.6142. So this wouldn’t happen, as it is less than 0.9132.
• There’s an interesting option. What if the 2nd pass was tilted just right, so that it wouldn’t create 4 remaining bits, but only 2? This covers an area of 1.0472. Yes! This is indeed possible. A 3rd pass, tilted the other way, would cover the rest.
• I don’t know whether this is exactly the optimal way to do things. But it proves, that 3 passes can do the job.

And for extra credit:

Desmos 2 Researchgate

There’s something interesting going on at Researchgate, suggesting that a non-greedy solution would need at least 20 circles / 10 cylinders. Because the angular radius of each circle is 30^o.

This one is just me guessing most of the way, illustrated in Desmod:

• 1st and 2nd pass are symmetrical, with the middle of the cylinder passing through the center. They are also perpendicular.
• I assume the same goes for the 3rd pass.
• The next 4 passes (red in my model) are closing some gaps on the surface of the sphere between the 3 existing passes. E.g. one of these cylinders has x=y=z in the middle.
• This leaves 8 bits. I would need 4 more passes to cover these, again using cylinders passing through the center.
• Using this method, with the whole surface covered and all cylinders passing through the center, all of the volume has been covered.
• This would suggest 11 passes.

***

How Greedily Can You Mow the Lawn?

This week the #puzzle is: Can You Race Against Zeno? #integration #summation #speed #distance #time (Link at the bottom.)

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Desmos 1 – just to be confusing, the definition of t_Zeno1 here is slightly different.

Let’s look at what we know or define:

• d: the full distance (5 km – all we metric centric people thank you)
• t_init: the time spent running with the initial speed all the way (24 m)
• v₀: the initial speed (d/t_init) (also, t_init = d/v₀)
• a: the increase of speed as a factor (1.1)
• t_Zeno1: the time spent running under the new rule

With these definitions in place, let’s go running.

• Run at v₀ to cover the distance d/2^1. (Half of the distance is run at the initial speed.)
• Then run at v₀ * a to cover the distance d/2². (Half of the remaining distance is run after 1 speed increase.)
• Then run at v₀ * a² to cover the distance d/2³.
• Then run at v₀ * a³ to cover the distance d/2⁴.
• In general run at v₀ * aⁱ to cover the distance d/2ⁱ⁺¹.
• In general spend t_i to cover distance d/2ⁱ⁺¹.
• t_i = d/2ⁱ⁺¹ / (v₀ * aⁱ)
• t_i = (d/v₀) / (2ⁱ⁺¹ * aⁱ)
• t_i = t_init / (2ⁱ⁺¹ * aⁱ)
• t_Zeno1 = Σ_i=0 t_i
• t_Zeno1 = Σ_i=0 t_init / (2ⁱ⁺¹ * aⁱ)
• t_Zeno1 = t_init * Σ_i=0 1 / (2ⁱ⁺¹ * aⁱ)
• To get a good approximation, I can let the upper bound be finite, but growing.
• According to Desmos, t_Zeno1 = 22 m.

But seeing I am so close, maybe I can do this in a better way.

• The general formula for v can be written as
• v(t) = a^{(⌊-log₂(1-t)⌋)} * v₀
• Some examples:
  • v(0) = a^{(⌊-log₂(1-0)⌋)} = a^{(⌊-log₂(1)⌋)} = a^(⌊0⌋) = 1 * v₀
  • v(0.4) = a^{(⌊-log₂(1-0.4)⌋)} = a^{(⌊-log₂(0.6)⌋)} = a⁰ = 1 * v₀
  • v(0.5) = a^{(⌊-log₂(1-0.5)⌋)} = a^{(⌊-log₂(0.5)⌋)} = a^{(⌊-(-1)⌋)} = a * v₀
• Instead of the sum I can use an integral.
• t_Zeno1 = t_init * ∫ ₀¹ 1 / (v(t)/v₀) dd
• Because, for a small distance d_j the contribution to the time is:
• t_j = d_j / v(t_j)
• t_Zeno1 = Σ_{all j} t_j
• t_Zeno1 = Σ_{all j} d_j / v(t_j)
• t_Zeno1 = Σ_{all j} d * d_j/d / v(t_j)
• t_Zeno1 = d * Σ_{all j} d_j/d / v(t_j)
• t_Zeno1 = d * ∫ ₀¹ 1 / v(t) dd
• t_Zeno1 = d * ∫ ₀¹ 1 / (a^{(⌊-log₂(1-t)⌋)} * v₀) dd
• t_Zeno1 = d/v₀ * ∫ ₀¹ 1 / a^{(⌊-log₂(1-t)⌋)} dd
• t_Zeno1 = t_init * ∫ ₀¹ 1 / a^{(⌊-log₂(1-t)⌋)} dd
• qed
• Again, desmos calculates this as the integral being 0.916666666667, therefore t_Zeno1 = 24 m * 0.916666666667 = 22 m.

And for extra credit:

Desmos 2

Again, let’s look at what we know:

• v(t) is the speed at any given time.
• v(0) = v(1-1) = v₀ above.
• v(0.5) = v(1-1/2¹) = v₀ * a
• v(0.75) = v(1-1/2²) = v₀ * a²
• v(0.875) = v(1-1/2³) = v₀ * a³
• In general v(1-1/2ⁱ) = v₀ * aⁱ
• And v(t) is a smooth function.
• This calls for a double log system!
• Let’s try simply plugging in some numbers first in Desmos. Looks good.
• Then let’s try to describe this function.
• v(t) = v_opp(1-t) (running the opposite way)
• v_opp(1/2ⁿ) = v₀ * aⁿ
• v_opp(log₂(t)) = v₀ * a^-log₂(t)
• v(t) = v_opp(1-t) = v₀ * a^-log₂(1-t)
• Double log confirms, just writing it as v(t) = v₀ * (1-t)^-0.137504 instead.
• t_Zeno2 = t_init * ∫ ₀¹ 1 / a^-log₂(1-t) dd
• The value of the integral is 0.879118155787, therefore t_Zeno1 = 24 * 0.879118155787 = 21.0988.

***

Can You Race Against Zeno?

This week the #puzzle is: Can You Squeeze the Bubbles? #circles #geometry #area #minimize (Link at the bottom.)

And for extra credit:

But first. Last week I made a booboo. At some point I began trusting my assumption about the probabilities so much, that I didn’t figure out, why my monte carlo results didn’t line up. This again lead to me saying 2 was the correct answer to the extra credit, when in fact… well, as I said, my monte carlo said something else. Something better. This is a detail from my heat map 5.

The lowest values occur, not in the corner (4), but towards the middle of the side (3). And the ratio is something like 2.7. Earlier heat maps actually showed this more clearly. Here’s the 3d image based on my monte carlo data, and for comparison the other 3d image again:

The important feature is that there’s a dip along the lower edge. Corner low, middle of side lower. Sigh. Anyway. Back to the puzzles from this week.

Highlight to reveal (possibly incorrect) solution:

Desmos live Two Circles Calculator Desmos image

So, here’s the big assumption: The best possible choice for the next center is to tuck it as far into the previous circle(s) as possible. 2nd center goes on the periphery of the 1st. 3rd center goes where the 2 first circles cross each other, into the little “fjord”. Etc. See model on Desmos.

(This is among other things assuming, that being on the periphery, being a distance of 1 from the center, isn’t being inside the circle.)

The next question then is: What is the area of this figure? Looking at the image, we have 7 circles. But then we have to subtract 6 green figures, so as not to double count. And 6 blue figures twice. And 6 black figures 3 times. (Also note, 1 green figure = 1 orange figure + 2 black figures; 1 blue figure = 1 orange figure + 1 black figure.)

Area of circle: π 1² = π = 3.14159.

Area of overlap between 2 circles, like the middle circle and the one to the right of it – this is also 2 orange figures and 5 black figures: From Two Circles Calculator, 1.22837.

Area of black figure: From Two Circles Calculator, 0.18122.

Area of orange figure: (1.22837 – 5 * 0.18122) / 2 = 0.161135.

Area of blue figure: 0.161135 + 0.18122 = 0.342355.

Area of green figure: 0.161135 + 2 * 0.18122 = 0.523575.

Area of the whole figure: 7 * 3.14159 – 6 * 0.523575 – 2 * 6 * 0.342355 – 3 * 6 * 0.18122 = 11.479.

And for extra credit:

Desmos image

It’s actually easier to look at hexagons and triangles. Each hexagon consists of 6 triangles. Each triangle is actually part of 3 hexagons. Therefore adding 1 hexagon only contributes 6/3 = 2 new triangles.

The area of such 2 triangles is √ 0.75 = 0.8660. The function f(N) is therefore 0.866 * N.

Test: Going from 7 circles in the above fiddler to 19 (in a symmetrical way) adds 12 circles. The area grows by 3 orange figures and 5 black figures for each new circle “on a corner” and 2 orange figures and 3 black figures for each new circle “on an edge”. This is on average 2.5 * 0.161135 + 4 * 0.18122 = 1.1277175. As N goes up, the edge circles will dominate. An edge circle contributes 2 * 0.161135 + 3 * 0.18122 = 0.86593. QED.

***

Can You Squeeze the Bubbles?

Og vi skal selvfølgelig også betragte Hugo-finalist-novellerne fra i år.

Allerede noget bedre at vælge mellem. “Three Faces of a Beheading” blev i mit hoved et godt stykke tid, så det er min favorit.

Anmeldelse af “Three Faces of a Beheading” (gratis), af Arkady Martine. Novelle. 2024. Hugo-finalist.

Skitse: En mulighed for et computerspil er, at en enkelt spiller kan have et stort publikum. Det kan derfor også have stor betydning, når en spiller gør noget usædvanligt. I et autoritært samfund gør noget forbudt, noget farligt.

Er det science fiction? Jeps.

Temaer: Det omtalte spil er baseret på noget historisk. Der var en gang en kejser og et oprør. Noget historisk kan fortælles på forskellige måder. En historikers forsøg på at få mening i, hvad der egentlig skete, kan føre et nyt sted hen. Hvad var folks motiver? Hvem havde alliancer? Hvad er fortællingen her? Hvis der er en.

Hvis man ønsker at sige noget om sin samtid, så kan man også vinkle noget historisk på en passende måde.

Min fornemmelse er, at forfatteren er intelligent og veluddannet (fx er der fodnoter til novellen) og har valgt en indviklet metode. Bl.a. er der pudsige skift mellem 1. og 2. person. Jeg læste novellen 2 gange, for at være nogenlunde sikker på det hele.

Er det godt? Ja. Ja, det er det egentlig. 👽👽👽

Anmeldelse af “Stitched to Skin like Family Is” (gratis), af #NghiVo. Novelle. 2024. Hugo-finalist.

Skitse: Sommeren ’31 kan det godt være lidt indviklet at være kinesisk i Illinois, USA. Således også for hende her, der i øvrigt er rigtig god til at lappe tøj og sy det om. (I får mig ikke til at skrive omf*randre! Jeg gør det ikke!) Hun kan også få noget ud af at lytte til tøj. Og så leder hun efter sin bror.

Er det science fiction? Aldeles ikke. Fantasy.

Temaer: Hun kan noget med tøj og sko, specielt hvis hun har haft fat i det før.

Så mærker hun også racisme.

Er det godt? Hm. Det var jo et indviklet spørgsmål. Jeg gættede ikke det hele fra første linje. Jeg har sympati med hovedpersonen. Tjo. 👽👽👽

Anmeldelse af “Marginalia”  (gratis), af #MaryRobinetteKowal. Novelle. 2024. Hugo-finalist.

Skitse: Her til lands er snegle kæmpestore, og man kan sagtens dø af at møde dem eller deres fodspor af syre. Margery skal på en eller anden måde håndtere, at hendes lillebror helt vildt gerne vil se sneglen, og at deres syge mor helst ikke må være alene.

Er det science fiction? Nej. Fantasy.

Temaer: Der går klassekamp i det her. Baronen mener, at han gør det så godt. Men passer han faktisk godt på sine tidligere ansatte? Ved han, hvad de har brug for? Og forstår han godt, at dem “under ham” kan være klogere og mere intelligente?

Er det godt? Ja. Der blev dog ved med at være underlige ting i teksten. Fx at Margery tilsyneladende brygger øl og vasker tøj samtidig. Men alligevel. 👽👽👽

This week the #puzzle is: Can You Weave the Web? #geometry #trigonometry #probability (Link at the bottom.)

A spider weaves a web within a unit square (i.e., a square with side length 1) in the following haphazard manner:

First, the spider picks two points at random inside the square. In particular, it picks the points “uniformly,” meaning any point is equally likely to be picked as any other point.

Next, the spider connects the two points with a strand of silk and extends the strand to two sides of the square. For example, here is a web made of 10 silk strands that were picked as described:

Within the unit square, which point (or points) is most likely to be on a new strand of silk, whose two defining points have not yet been picked?

(While the probability that any specific point winds up being precisely on the new strand is zero, some points and regions are nevertheless more likely to be on the strand than others.)

And for extra credit:

Highlight to reveal (possibly incorrect) solution:

Program 1 Program 2 Desmos Heat map 1, 2, 3, 4, 5, 6. 3d image.

Okay, this was a tough one.

The main realization here is: Given the 2 points, the longer the line segment within the square is, the higher the number of points on the segment. So, for any given point I can ask, what lengths of line segments do we have, systematically going all the way around the point? This can again be changed to, what is the distance to the square going all away around the point? The longer the sum of the lengths of the segments, the higher the probability a given point was hit. The sum of the lengths evolves in an area.

The area only tells me something about the probabilities compared to each other! I don’t actually calculate any probabilities directly.

For the fiddler, Desmos just supplied a picture of what was going on. For extra credit I got some useful numbers. I construct a graph for “what is the distance between this point and the square, in all possible directions”. Then I calculate the area under the graph for one turn around the possible angles. Experimentation shows, the area is somewhere between 1.76274717407 and 3.52549434808. (Feel free to play around with model.) The max seems to be right in the middle of the square, and the min in the corners.

In order to be sure of my numbers I use the monte carlo method in program 1. Construct a lot of lines. For each line, note which parts of the square it goes through. (I have subdivided the square into smaller squares.) Again, I get the same max and min positions, and it points towards the middle and the corners of the square.

Finally in program 2 I use the integral method to calculate (more) exact numbers. Max is in smack dab (0.5, 0.5).

As max I get 3.5254943481 and as min 1.7627475763. The ratio is 1 / 0.5000001141 = 1.999999544. I feel pretty confident saying it is actually 2.000. The Desmos numbers confirm this.

I also constructed some fun heat maps of the situation, and a 3d image. And one of my programs hates the number 14?

***

Can You Weave the Web?