Corner Solutions

February 13, 2022February 14, 2022 OverseerLeave a comment

This week’s Classic from Dean Ballard asks about placing prime numbers on the corners of a cube such that the 4 corners on every face add up to the same number. First we will look at general solutions and then take a look at solutions for primes:

We label the numbers on the corners of a cube somewhat arbitrarily with letters [a,b,c,d,e,f,g,h]:

We notice that if the face sums are equal we get a set of six simultaneous equations relating pairs of corners of faces with a shared edge:

a+b=f+g; c+d=e+h; c+f=a+h; d+g=b+e, b+c=g+h, a+d=e+f

Solving these simultaneously we find there is no unique solution but a family of solutions with the requirement that all the long diagonal corner differences be equal:

Solution Condition: (a-f) = (e-d) = (g-b) = (c-h ) .

We can find a non-prime solution quickly with the arithmetic progression [0, 1, 2, 3, 4, 5, 6, 7] assigned as [a,b,c,d,e,f,g,h] = [3, 4, 7, 0, 1, 2, 5, 6]. Permuting corner pairs also produces valid solutions. Each long diagonal corner difference is 1 and the face sums are 18. This is interesting because it implies that any arithmetic progression can be a solution to the general non-prime puzzle since we can obviously multiply all the corners of a valid solution or add a constant and still have a valid solution. However there are many non-arithmetic progressions that form valid solutions as well.

Looking for primes we can quickly see a solution with [a,b,c,d,e,f,g,h] =[13, 17, 31, 3, 5, 11, 19, 29] or when sorted [3, 5, 11, 13, 17, 19, 29, 31] . The long diagonal corner differences are 2 and the face sums are 64. There is a solution nearby with [a,b,c,d,e,f,g,h] = [13, 17, 31, 5, 7, 11, 19, 29] or when sorted [5, 7, 11, 13, 17, 19, 29, 31]. The long diagonal corner differences are 2 and the face sums are 66.

For further prime solutions we can hunt for them (the twin prime conjecture implies there are an infinite number of prime pairs with any even gap) or even use our observation above that all arithmetic progressions are solutions. According to Green-Tao there will also be a very large (infinite?) number of solutions of this type. Looking in Wikipedia we see the following table for prime arithmetic progressions:

Choosing values for k=8 terms we find a solution [a,b,c,d,e,f,g,h] = [829, 1039, 1669, 199, 409, 619, 1249, 1459] or when sorted [199, 409, 619, 829, 1039, 1249, 1459, 1669]. The long diagonal corner differences are 210 and the face sums are 3736.

Hat Attack

November 21, 2021November 23, 2021 OverseerLeave a comment

This week’s Riddler Classic is a variant of the familiar hat color guessing game with a twist. Here the four participants are on the corners of a square and can only see hats of their neighbor’s along the edges of the square they are connected to. The challenge is to come up with a strategy for the players to guess the color of their own hats that guarantees at least one of the players correctly guesses their hat color, no matter what combination of the three colors of hats are placed on the four players. Since there are no restrictions on the hat colors or placements there are 3^4 or 91 possible games to make sure we have at least one winner for.

One question we can ask right away is: “why should it be possible to do this at all?” It is not immediately obvious that it is the case, however there are similar games where it is the case. One way to analyze these games is to try to understand the strategy from the bottom up. Here we will take a more general computational search approach which will allow us to solve for strategies with larger N, different shape polygons, etc in the future.

We note that each of the players (labeled clockwise V1, V2, V3, V4) can only use information from two other players’ hats. V1 can only use information from V4 and V2, V2 from V1 and V3, V3 from V2 and V4, and V4 from V3 and V1. We notice also that players on diagonally opposite corner of the square have the same information to work with.

We will define strategies for the player as a function of the other players that they can see: ie S(V1) = f(V4,V2), S(V2) = g(V1,V3), S(V3) = h(V2,V4), S(V4) = i(V3,V1). Note that the arguments are ordered clockwise around the square, with the trailing vertex first in the argument list.

Now, there are a lot of possible functions out there. First we will try something simple: f(Vn,Vm) = [ (+/-) Vn (+/-) Vm] %3, where the (+/-) terms can take either + or – values. This has the advantages of 1) symmetrically weighting the players 2) the 3-color modulo guarantees a mapping to a possible color 3) some history of success in hat problem land!

We code up some Python to try all combinations of (+/-) (256) acrosss all possible games (91). We do not attempt to reduce the dimensionality as the problem is still small enough to do an exhaustive search:

We find two possible, very similar, distinct strategies (adjusting for rotationally identical ones). Note we have labeled colors [0,1,2]. There are 9 game variants where all the players guess correctly, but in 72 cases only one player guesses correctly:

Successful Strategy #1 for 3-Color Square

Successful Strategy #2 for 3-Color Square

Solutions for Other Values of N

We searched for solutions for other values of n = (3,5,6,7,8,9) using this simple functional form and had no luck. We upgraded the code to allow strategy functions of the form: f(Vn,Vm) = [ (+/-) Vn (+/-) Vm (+/-) offset] %3, where the offset term can be k or 0.

Setting the offset term to 1 or 0 we find many solutions to the n=3 problem with one correct player guess per game, which is of course enough to win. This sample is typical:

Random Triangles – II

October 31, 2021November 11, 2021 OverseerLeave a comment

Last week’s Riddler from Allen Gu was about determining the probability of a random triangle T inscribed in an equilateral triangle containing the centroid point C of the main triangle. The result as determined by multiple solvers was:

$P(C \in T) = \frac{1}{3} ln(4)$

You can see our solution to the equilateral problem in the post previous to this.

As a follow up we looked at how this probability changes as the shape of the main triangle was allowed to change. The surprising (?) result is that it does not change, and is independent of the main triangle shape.

To set this up, we fix the base of the main triangle on the x-axis with one vertex on the origin, and allow the other two sides to be determined by an arbitrary point P with coordindates (Px, Py). The centroid of the traingle is C= ((L1+Px)/3,Py3). The sides of the triangle now have lengths L1, L2, L3 consistent with forming the triangle established by the base length L1 and arbitrary point P.

We see that the probability set up is identical to the equilateral case with a few modifications to normalize the probability distributions for sides that have lengths not necessarily equal to 1.0 :

$P = 1-\frac{1}{L1\cdot\,L2} \int_{L1/2}^{L1} d2(x1) dx1 -\frac{1}{L2\cdot\,L3} \int_{L2/2}^{L2} d3(x2) dx2 - \frac{1}{L1\cdot\,L3} \int_{L3/2}^{L3} d1(x3) dx3$

We will evaluate the first integral in the above expression. Using equations for the intersection of the dotted line L4 in the picture and L2 we find:

$Qx = \frac{x1}{3x1-L1} Px$

We then calculate the distance d2(x1) from point P to point Q and find:

$d2(x1) = [(Px-\frac{Px\cdot\,x1}{3x1-L1})^2 - (Py-\frac{Py\cdot\,x1}{3x1-L1})^2 ]^\frac{1}{2}$

$d2(x1) = \frac {2x1-L1}{3x1-L1} L2$

And evaluating the first integral we see a familiar result from the original problem:

$\frac{1}{L1\cdot\,L2} \int_{L1/2}^{L1} \frac {2x1-1}{3x1-1} L2 \cdot \,dx1 = \frac{3-ln(4)}{9}$

We can rotate the triangle and set up the other integrals similarly and will obtain the same result. Therefore the total probability is identical to the original problem:

$P(C \in T) = \frac{1}{3} ln(4)$

It is somewhat surprising that the result does not depend on the triangle shape at all and is therefore identical to the result from the original problem. Additionally surprising is that the contribution to the probability is the same for each integral term. Some intuitions behind this are that the integration limits along sides are always over half of each side due the centroid constraint and the probability mapping of x to d is independent of the side lengths due to the ratiometric, and eventually logarithmic, nature of the integrals.

Odd Man Out

October 24, 2021October 25, 2021 OverseerLeave a comment

This week’s Classic asks about the probability of a triangle constructed with vertices randomly located on each side of an equilateral triangle containing the center point (centroid). Below is an example of one good and one bad triangle:

Looking at the figure we see that one line of the red triangle creates a boundary excluding the center point, placing it in one of the three regions of the equilateral triangle not inside the red triangle. We can see that the probablity of a random triangle including the center point will be 1 minus the probability of any of the 3 sides of a random triangle excluding the center point. Since only one side of a particular random triangle can create a region excluding the center point, the probabilities of each side doing so are independent and also by symmetry equal. Therefore:

$P(C \in T) = 1- 3*P(C \in R)$

Where C is the center point, T is any random triangle, and R is the region outside the random triangle created by one of of its sides. We set up the problem for calculating the probability of exclusion for one side of the random triangle created by points on the left and bottom sides of the equilateral triangle:

Given the above set up, we note that the center point can only be excluded if x > 0 . Possible ranges for the point on the opposite side are in the range of ‘d’. Valid extrema for the sides for this x point that exclude the center point are shown in green. Noting that the probability distributions for the location of the vertices on all the equilateral sides are uniform, the probability of the center point being included becomes:

$P(C \in T) = 1-3* \int_{0}^{1/2} d \cdot \, dx$

Using similar triangles in the above diagram and the geometry of the equilateral triangle we see that:

$i+j = 1/ \sqrt{3}, \hspace{.5cm} h/j = 2\sqrt{3}x,\hspace{.5cm} i = \sqrt{3}h , \hspace{.5cm} d = 2h$

And therefore:

$d = \frac{4x}{6x+1}$

So our answer becomes:

$P(C \in T) = 1-3* \int_{0}^{1/2} \frac{4x}{6x+1} \, dx$

Using a trip to the integral tables, and with a small amount of algebra we see:

$P(C \in T) = 1-\frac{1}{3}\Bigl|_{0}^{1/2} [6x-ln(6x+1)+1]$

$P(C \in T) = \frac {1}{3}ln(4)$

Or about 46.2%.

The Biggest Winner

September 27, 2021September 30, 2021 OverseerLeave a comment

In this week’s Riddler Classic we are asked to find the highest posssible score (where high is bad) in a 3 part climbing competition that could conceivably result in a win or overall tie. There are 8 contestants and no ties in the 3 individual events. Scoring is based on the the product of the finishes in the 3 individual events.

We could easily simulate this but look for a heuristic approach instead. We note that:

The worst possible score for any of the three different contest winners is (1,7,8) = 56. Therefore our highest possible winning answer can be no higher than 56.
If we look at possible scores from 56 down we see the first few are: 56 = [(1,7,8), (2,4,7)], 50 = (2,5,5), 49= [1,7,7], 48 = [(3,4,4), (2,3,8), (2,4,6), (1,6,8)].
For 56 if we use 3 (1,7,8) triplets for the individual contest winners then the remaining possible allocation for the second place finishes is (2,5,6) = 60 which we need to use three times to stay >= 56. That leaves us with three 3’s and three 4’s to allocate among two remaining contestants, and there is no way to do that and remain above 56. If we use (2,4,7) then we are left with a maximum for one of the winners of (1,6,8) = 48 and so 56 is out.

Continuing on in similar fashion we see that constraints on the 1’s and 2’s pretty much determine the story:

So the answer to the Classic is 48, with four different possibilities for one player acheiving 48 and examples above (not unique) for how the other players could score to make it work.

A Case of Unmistaken Identities

September 18, 2021September 21, 2021 OverseerLeave a comment

This week’s Riddler Classic from Rushabh Mehta asks about the product of the lengths of line segments of a diagonal or altitude of regular polygons formed by the intersections with all the perpendicular diagonals.

Riddler Classic

Here we will solve the problem in general and then show that for a side length of 2 and an even number of sides the product is independent of the number of sides.

The length of the diagonal connecting two opposite vertices for an even N-sided polygon is twice the major radius R the circumscribed circle.

[The length of the diagonal connecting a vertex to the midpoint of the opposite side for odd N is r+R (odd case shown here)]

The length of the major and minor radii for an N-sided polygon of side length S are:

$r = \frac{S}{2}*cot(\frac{\pi}{N}), \quad R = \frac{S}{2}*csc(\frac{\pi}{N})$

For the case of even number of sides, we will put a vertex on the point (R,0) and the coordinates of the N vertices are:

$x_{k}=R*cos(\frac{2k\pi}{N}), \quad y_{k}=R*sin(\frac{2k\pi}{N}), \quad k = [0,N-1]$

The lengths of the diagonal segments created by the perpendicular diagonals is the difference in the x-coordinates of N/2 pairs of adjacent vertices. And the product is:

$P = \prod\limits_{k=1}^{N/2}R*(cos(\frac{2\pi*(k-1)}{N})-cos(\frac{2\pi*k}{N}))$

We can use a trig identity…

$cos(A)-cos(B) = -2sin(\frac{A+B}{2})* sin(\frac{A-B}{2})$

…and the expression for R above, to rewrite the expression as follows:

$P = S^\frac{N}{2}\prod\limits_{k=1}^{N/2}sin(\frac{(2k-1)\pi}{N})$

Substituting N’=N/2:

$P = S^\frac{N}{2}\prod\limits_{k=1}^{N'}sin(\frac{(2k-1)\pi}{2N'})$

Now we will use a very useful product of sines identity……:

$I(n)= \prod\limits_{k=1}^{n-1}sin(\frac{k\pi}{n}) = \frac{n}{2^{n-1}}$

…in a way described here:

https://math.stackexchange.com/questions/1632023/evaluation-of-prodn-r-1-sin-left-frac2r-1-pi2n-right?noredirect=1&lq=1

To use this identity we rewrite the the last espression for P this way, where the appropriate terms on the top and the bottom cancel to make the result identical:

$P = S^\frac{N}{2}\frac{\prod\limits_{k=1}^{2N'-1}sin(\frac{k\pi}{N'})}{\prod\limits_{j=1}^{N'-1}sin(\frac{2j\pi}{2N'})}$

This simplifies to:

$P = (\frac{S}{2})^\frac{N-1}{2} *2.0$

And for the given case of S=2 we see that the product of the line segments along the diagonal = 2.0 and is independent of N:

$P = 2.0$

Extra Credit

For the extra credit we have a 1001 sided (odd number) polygon. We will solve for general odd N. The lengths of the altitude (R+r) segments created by the perpendicular diagonals is the difference in the x-coordinates of (N-1)/2 pairs of adjacent vertices. And the product is:

$P = \prod\limits_{k=1}^{(N-1)/2}R*(cos(\frac{2\pi*(k-1)}{N})-cos(\frac{2\pi*k}{N}))$

We can proceed as above in the Classic up to this point:

$P = S^\frac{N-1}{2}\prod\limits_{k=1}^\frac{N-1}{2}sin(\frac{(2k-1)\pi}{N})$

Interestingly this product is equal to:

$P = S^\frac{N-1}{2}\prod\limits_{k=1}^\frac{N-1}{2}sin(\frac{k\pi}{N})$

To see why the last two expressions are equal, let’s look at the case where N= 17. We notice that both expressions contain k and (2k-1) values of [1,3,5,7] so those terms are the same. The remaining indexed (2k-1) values in Expression 1 are [9,11,13,15] and the remaining indexed k values in Expression 2 are [2,4,6,8]. When we pair these terms such that k+ (2k-1) = N, they are equal. IE [(9,8), (11,6), (13,4), (15,2)]. To see why, it is easy to show that: