#ThisWeeksFiddler, 20260703

Skriv en kommentar

This week the #puzzle is: Can You Fit the Stars on the Flag? #coding #bisection #desmos

When designing her new nation’s flag, Retsy Boss wanted to compactly arrange some stars. These stars were positioned along a square grid, but she only wanted to include stars whose centers were at most two units away from some point on the plane.
For example, if she had centered the circle on a star itself, then she could have placed a total of 13 stars on the flag, as shown below:
What is the greatest number of stars Retsy could have placed on the flag?

And for extra credit:

After 250 years, the nation has commissioned Retsy Boss VIII to design a new flag with one star for each of the nation’s current 58 states. As an homage to the original flag design, Retsy wants to select 58 stars from the square grid that are all at most some distance R from a point on the plane.
What is the minimum distance R that Retsy can use?

Can You Fit the Stars on the Flag?

Solution, possibly incorrect:

Desmos Program

Method 1: Recreate the situation in Desmos and mess around. First define a function to count the number of stars (the stars have integer coordinates). The center of the circle:

(x1,y1)(x_1,y_1)

The distance to the center from another point:

f(x,y)=(x−x1)2+(y−y1)2f\left(x,y\right)=\left(x-x_{1}\right)^{2}+\left(y-y_{1}\right)^{2}

Use rounded values for the other point:

g(x,y)=f(round⁡(x),round⁡(y))g\left(x,y\right)=f\left(\operatorname{round}\left(x\right),\operatorname{round}\left(y\right)\right)

This function will be 1, if the middle of a unit square is within the circle with radius r1:

h(x,y)={g(x,y)≤r12:1,0}h\left(x,y\right)=\left\{g\left(x,y\right)\le r_{1}^{2}:1,0\right\}

Compute the area of all the unit squares:

S=∫−r1−1r1+1∫−r1−1r1+1h(x,y)dydxS=\int_{-r_{1}-1}^{r_{1}+1}\int_{-r_{1}-1}^{r_{1}+1}h\left(x,y\right)dydx

x1=0.25,y1=0.5,r1=2,S=14x_1 = 0.25, y_1 = 0.5, r_1 = 2, S = 14

Method 2: Create a program to go through a lot of options.

Result 1: 14 (x1: 0.063600, y1: 0.499700)

Result: 14 stars.

And for extra credit:

Same methods.

x1=0.500,y1=0.125,r1=4.155193,S=58x_1 = 0.500, y_1 = 0.125, r_1 = 4.155193, S = 58

My program is surprisingly sensitive to Δ\Delta, the distance between different (x,y) combinations to try. I employ bisection to fine tune the solution.

Max stars for r = 4.155180, d = 0.000100: 57
                        (x1: 0.000000, y1: 0.000000)
Max stars for r = 4.155190, d = 0.000100: 57
                        (x1: 0.000000, y1: 0.000000)
Max stars for r = 4.155200, d = 0.000100: 58
                        (x1: 0.125000, y1: 0.500000)
Max stars for r = 4.155210, d = 0.000100: 58
                        (x1: 0.125000, y1: 0.500000)

4.1550000 < r < 4.1560000
4.1550000 < r < 4.1555000
4.1550000 < r < 4.1552500
4.1551250 < r < 4.1552500
4.1551875 < r < 4.1552500
4.1551875 < r < 4.1552188
4.1551875 < r < 4.1552031

Result 2: 4.1551875 - 4.1551953
                        (x1: 0.125000, y1: 0.500000)

The 2 methods largely agree. Result: A radius of 4.1552.

Skriv en kommentar