Math and Logic Puzzles: Redux

[Scigatt]

In honour of J.H. Conway.

Given any triangle ABC, extend its sides so they are lines. For each of the rays extending from each vertex, mark off a point at a distance equal to the opposite side, producing six new points, as shown below.

Prove that these six points lie on a single circle.

[Scigatt]

I think I got it...

Spoiler:

Let's call the vertices of the triangle A, B, and C. And we'll call four of the extended points D, E, F, and G. I've also labeled the measures of the angles of the triangle: M_a, M_b, and M_c.

Notice that CD and EC have the same total length. This means that triangle CED is an isosceles triangle and angles CDE and DEC are equal to each other (as marked in the diagram). But we also know that the sum of the angles of triangle CED is 180 degrees. So:
180 = <DCE + <DEC + <CDE
180 = M_c + 2*<DEC
<DEC = <CDE = 90 - 0.5*M_c

Similarly, we can find that:
<BFG = <BGF = 90 - 0.5*M_b

Next, notice that triangle ADG is also isosceles, so <ADG = <AGD. Also we can see that <DAG and <BAC are equivalent angles. So <DAG = M_a and that means:
<ADG = <AGD = 90 - 0.5*M_a

Finally, calculate the sum of <FGD + <BED:
[<FGD] + [<BED]
= [(<BGF) + (<AGD)] + [<CED]
= [(90 - 0.5*M_b) + (90 - 0.5*M_a)] + [90 - 0.5*M_c]
= 270 - 0.5*M_a - 0.5*M_b - 0.5*Mc
= 270 - 0.5*(M_a + M_b + M_c)
= 270 - 0.5*180 = 270 - 90 = 180

So <FGD + <BED = 180 and it can be similarly shown that <EDG + <CFG = 180 as well. This means that quadrilateral DEFG is cyclic, so it's vertices must all fall on the same circle.

And this same method can be used to show that the other two extended points fall on the same circle as well.

I had a completely different proof:

Spoiler:

Let's label up.


First, if the hypothesis is true, where would the centre of the circle have to be? Since UW, VY, and XZ have the same length, their closest points to the centre are equidistant. Therefore, you can draw a smaller concentric circle tangent to all three chords, and the centre must be the triangle's incentre.

With that, we go back to the triangle ABC. We find the incentre and we draw a circle so that the sides extended to chords have length equal to the perimeter of the triangle. Labeled up, we get this:

Let BC = a, CA = b, and AB = c

Since the (in)centre lies on the angle bisectors of <CAB, <ABC, and <BCA, then by a symmetry argument:

AY = AZ = a'
BW = BX = b'
CU = CV = c'

Now all we need to prove is that a = a', b = b', and c = c'. This can easily be done using the equations below:

a + b' + c' = 2s(WU)
a' + b + c' = 2s(VY)
a' + b' + c = 2s(XZ)
a + b + c = 2s(definition of s)

[Scigatt]

Spoiler: @Scigatt

I don't think your proof works. You appear to be proving some kind of converse to the statement? You end up with the assertion that the lines drawn are of equal length, but that's given by the problem statement.

Spoiler:

I prove that that particular circle crosses the extended sides at the right places to recreate the original setup. Therefore, when I have the original setup, we know that circle satisfies the requirements.

[Scigatt]

Making a few assumptions about the relevant probability distribution, I get P = arctan(sqrt(2))/pi ~= 30.4%. Those assumptions could very easily be wrong though.

[Scigatt]

I believe that a more rigorous approximation for P is the following:



I think from this the limit value of arctan(sqrt(2))/pi follows easily.

[Scigatt]

The ye^{(-y^2)} term integrates to zero. Using integration by parts with u = y and dv = ye^{(-y^2)} dy, the y²e^{(-y^2)} integral reduces to the standard normal integral, which is 1.

Here's something simple: Prove that every finite field has a quadratic extension.

[Scigatt]

You should prove the standard normal integral is 1 as well if you are going to use that argument. (Yes, it is a probability density function, so it equals 1, but the solution should be understandable by someone who has only taken math through multivariable calculus. This makes the problem more interesting.)

Square the standard integral, change the variable of one to get the 2D version, recast to polar co-ords and then integrate by substitution to 1.

If the field has odd characteristic:
For any nonzero x, x and -x are distinct and square to the same value. Thus there are (|F|-1)/2 nonzero squares so there must be (|F|-1)/2 nonzero nonsquares, so let c be a no square then x^2-c is irreducible and thus extending by the root of that is a quadratic extension.

If the field is characteristic 2:
Apply the same argument but instead of x and -x take x and x+1, and instead of both have the same square we have that both have the same x(x+1). Thus there’s some c which is not of the form x(x+1), and we have that x(x+1)+c is irreducible.

I had another solution in mind.

The number of reducible monic quadratic polynomials in GF(q) is q + (q*(q-1))/2 = (q*(q+1))/2 , while there are q^2 total monic quadratic polynomials. Since q > 1, then there exists an irreducible quadratic which can be used to generate an extension.

[Scigatt]

Let's get this this started again.

Enter a positive rational number and I'll give you a response. Figure out the rule I'm using.

[Scigatt]

47.

47

[Scigatt]

2/3

3/2

10^27

10^27

6/9

3/2

337500/234966429149994773

147359109017027496/87607320133304777

probably

a/b where and b are integers and b does not equal 0

For one, variable inputs aren't accepted. Secondly, even if I did accept variable inputs, you're still giving me some invalid ones.

[Scigatt]

1/72
100/1001

1/72
1090/11

[Scigatt]

101 / 1001
100 / 1003

491/611
364/739

2 / 71

37/36

[Scigatt]

3.14159.

100388/313771

[Scigatt]

100388/313771.

314159/100000

3 / 71

25/49

1

1

1/2^27

6/35

1/2^27
7/34

1/2
1/3

1/2
1/3

[Scigatt]

1/4
1/5
1/6

1/4
1/5
1/6

Spoiler: Answer

p/q in lowest terms is sent to a/b such that a*p = 1 mod (p + q) and a + b = p + q.

In other words, find p's multiplicative inverse in the ring of integers mod p + q (which must exist uniquely since p and q (and thus p and p + q) are relatively prime with p/q in lowest terms). Set the numerator to that value, and set the denominator such that the sum of the numerator and denominator is preserved.

Spoiler: Response

This answer has no actual resemblance to how I'm actually implementing the function. I think it's possible that the the two methods are equivalent. Proving that they are seems to be quite the task. I'll get to working on it. PM me if you want my implementation.

[Scigatt]

3/4
2/5
3/5
4/5

5/2
4/3
3/5
7/2

[Scigatt]

0.99999

199997/2

[Scigatt]

implosion's answer was basically correct, though my implementation was dissimilar enough that only now can I prove the equivalence.

Spoiler: Explanation of my procedure and proof

What I did with a given input essentially was to find it on the Stern-Brocot tree, making note of the sequence of turns. I then reversed this sequence, and used that to traverse the tree to get the output.

To traverse the Stern-Brocot tree easily, you need to have a left and right 'ancestor' and their 'descendant', which is their mediant. It is possible to calculate the ancestors from the descendant, but it's much easier to just keep track of the ancestors. To go 'left' on the tree, the mediant of the left ancestor and the descendant becomes the new descendant, and the old descendant becomes the right ancestor. To go to the right the process is analogous.

By convention, the left ancestor is taken as smaller than the right. It is more convenient, however, for this proof to reverse this convention.

Since all iterated descendants of two given ancestors are between them, to capture all positive rationals we need to start with 1/0 as the left ancestor and 0/1 as the right ancestor. Also, it will be helpful to keep track of the numerators and denominators of the ancestors in matrix form(numerator on top). Thus the starting point of the tree is:

Code: Select all

[1 0]
[0 1]

The following matrices then represent going left and right on the tree respectively, if we multiply them in on the right:

Code: Select all

[1 1]  [1 0]
[0 1]  [1 1]

Note all the previous matrices have determinant 1, therefore so does the matrix of any path down the tree. Also, the elements of each path matrix are all integers.
The crux of the proof comes down to two lemmas.

Lemma 1:

From path matrix M get M' by path reversal. Then M' is the 'anti-transpose' on M where m'_ij = m_{(n-j+1)(n-i+1)}, assuming 1-indexing.

This can be proven by induction.

Lemma 2:

Given a 2x2 matrix A, let s be the sum of all elements and r_i, k_j represent row and column sums respectively. The following equation holds:
r_ik_j = a_ijs - det(A)*(-1^(ij))

This can be proven directly.

These two lemmas along with some facts we observed earlier, immediately imply that implosion's method is equivalent to to the path reversal method.