Three angles

A puzzle recently posted in Enigmatic Code,  Enigma 1329: Height of ignorance, reminded me of a related puzzle:  For three squares laid side by side as shown in the diagram, prove that  α = β + γ

Clearly  α = 45⁰. The obvious approach is to use multiple angle formulae, but there is a more elegant geometrical solution.

Click here to see the geometrical solution
The solution of this puzzle can be used to solve Enigma 1329.

There is also a simple solution using complex numbers which consists of 17 symbols: 

$(3+i)(2+i) = 5(1+i)$

Does this count as a haiku?

Countdown Numbers Game

Several people have already written programs based on the Numbers Game from the TV program Countdown, but anyway here is another one, written in Python.

As has been noted elsewhere, a set of 2 large + 4 small or 1 large + 5 small typically covers a large proportion of  target numbers (101 to 999), and there are typically many ways of expressing each target using some or all of the 6 numbers.

These sets each cover all targets from 101 to 999. The lists of solutions () contain all targets from 0 until a gap above 999 is reached:

 5   6   7   8   9   75  (five consecutive numbers) 

 2   5   7   8   9   10  (six small numbers) 

 4   7   7   10   25  100  (a repeated number) 

 6   7   7   9   9  100  is perhaps more noteworthy,  covering every target number except the number 367 

 8   9   25   50   75  100  is the best set containing all four large numbers, covering 885 targets  


The code constructs solutions for a few games that have appeared on the TV show:

•  3   6   25   50   75  100 with a target of  952 , the James Martin 952 game, which has 2 solutions, (3×75×(6+100)-50)÷25 which was found by the contestant, and 25+(6×75×(3+100))÷50.
  
•  1   4   8   9   10   50  with a target of  500  ,possibly the easiset game ever?  for which my program finds 21 distinct solutions .
  
•  Some games solved by George Ford , one of the best countdown contestants.

Most of the complexity of the program is to do with minimising brackets,
e.g. (((((6)+(7))-(9))×(7))×(9))-(100)=(6+7-9)×7×9-100
and avoiding solutions that are essentially the same, e.g. 152=(6+7-9)×7×9-100=7×(7-9+6)×9-100.

The program also excludes "frivolous" solutions that contain an expression that equates to zero, e.g. 500 = (9-8-1)×4+50×100, solutions that involve multiplying or dividing by 1, e.g. 500 = (9-8)×50×100 or 500 = 50×100÷1 and solutions that have other redundancies, e.g. 500 = 9+10×50-1-8. 

# -*- coding: cp1252 -*-
from itertools import combinations

def wrap(t, condition=True):
    return ''.join(["(",t,")"]) if condition else t

def expressions( A, processed=set() ):
  """ initially, A is an array of numbers

   In recursive calls, A is an array of tuples (n,t,o,x,y,h) where
   n is a number,
   t is a text expression of n,
   o is the last operation applied to x,y to produce n = xoy
   h is the history of the expression, containing all the numbers produced in the construction
     of the expression
  """
  if type(A[0])==int: # inital call, so convert to array of tuples
    A = [ (A[i],str(A[i]),"",0,0, frozenset((A[i],)) ) for i in xrange(len(A))]
    processed=set()
  else: # recursive call, so return the expression formed in the parent
    n,t,o,x,y,h = A[0]
    if (n,t) not in processed:
      yield A[0]
      processed.add( (n,t) )

Contest Center

Due to a prolonged spell of wet weather in the UK, and the demise of New Scientist Enigma, I have recently turned my attention to the Contest Center, which has a lot of interesting maths puzzles.

I concentrated on problems that did not yet have any solvers, and managed to solve a few of them. (hints under plain cover to genuine puzzle enthusiasts only)

Point on Circumcircle (contributed by Fotos Fotiadis) 
 ABC is a triangle whose smallest angle is A. K is a point on the arc BC of the circumcircle. The perpendicular bisectors of AB and AC intersect the line AK at L and M, respectively. The lines BL and CM intersect at T. Prove that BT+CT=AK. 

Greatest Divisor (contributed by Paul Cleary) 
When n=8, the expression ab(aⁿ-bⁿ) is divisible by 30 for all positive integers a and b, and 30 is the greatest such divisor. Find a positive integer n such that the greatest common divisor of ab(aⁿ-bⁿ) for all positive integers a and b is n. 

26 Numbers (Contributed by Paul Cleary) 
There are infinitely many sets of 26 real numbers where their sum is 200 and the sum of their squares is S. The difference between the smallest and largest of the numbers in these sets is 60/13. What is the value of S? 

Sums of Polynomials 
Let p_i(x) = x²+m_ix+n_i for i=1,2,3,4 be four given polynomials with m_i and n_i integers, and m₁ through m₄ not all odd. Show that there is an integer N such that any integer n > N can be expressed as the sum p₁(a₁)+p₂(a₂)+p₃(a₃)+p₄(a₄) for some integers a₁ through a₄. 

Rational Powers (contributing the criterion gcd(a,b,c)=1)
 Let x be a rational number x=p/q with q>1 and gcd(p,q)=1. Let a, b and c be positive integers, with a^x+b^x=c^x and gcd(a,b,c)=1. Prove that a, b and c must be q-th powers, or find a counterexample. 


Repeated Digits  (not a first to solve, but most solutions found to date)
The square of 88 is 7744, where each digit of the square is repeated. Find additional squares (not ending with 0) where every digit is part of a repeated sequence, such as 11000555544. We will list the number of squares found by each solver. The notation +F indicates that the solver also found an infinite family of solutions. 

Update June 2014:
Square Heronian (contributed by Lee Morgenstern) 
A Heronian triangle has integer sides and integer area. Find a Heronian triangles where all 3 sides are squares. [Only one solution is known. Extra credit for anyone who finds a second solution.] 

Update September 2014:
** Square Rearranger 
Find the smallest three distinct whole numbers A, B and C such that you can rearrange the digits of A and B to get C², the digits of A and C to get B², and the digits of B and C to get A². [Leading zeroes are not allowed.] 

New Scientist Enigma 1354: Sound idea

     Here is a solution to Enigma 1354 which appeared recently in Enigmatic Code

The problem is this:

Joe’s daughter has been asking him for weeks to make a wind chime. So this week Joe cut a length of stainless steel tubing into 10 lengths from 1 cm to 10 cm in steps of 1 cm. He also cut out a disc from a sheet of stainless steel and drilled 10 evenly spaced holes round the perimeter and one in the centre.

Joe hung one tube from each hole and hung the disc up by a thread from its centre. That was a big mistake as the disc tilted right over.

So Joe rearranged the tubes until the disc balanced perfectly. In making a note of the lengths of the tubes in order round the disc the result was an 11-digit number.

What is the smallest of all the 11-digit numbers Joe could have written down?

In order for the wind chime to balance, moments about the axis af must balance

$ (b+e-g-j)sin(\frac{π}{5}) + (c+d-h-i)sin(\frac{2π}{5}) = 0 $ ..................... (1)

Noting that $sin( \frac{2π}{5}) = 2 sin(\frac{π}{5}) cos(\frac{π}{5})$ , dividing (1) through by $sin(\frac{π}{5})$

$ (b+e-g-j) +2 (c+d-h-i)cos(\frac{π}{5}) = 0 $ ..................... (2)

Substituting $ cos(\frac{π}{5}) = \frac{(1+\sqrt{5})}{4} $ into (2)

$ b+e-g-j +\frac{c+d-h-i}{2} +\frac{(c+d-h-i)\sqrt{5}}{2} = 0$

As a,b,...,i,j are all integers,$ c+d-h-i = 0$ and $b+e-g-j +\frac{c+d-h-i}{2}     =0$

So $c+d=h+i$ and $b+e=g+j$

So knowing five adjacent values, say, a,b,c,d,e, allows the other five to be deduced:

$f = 55 - a - (b+c+d+e) - (g+h+i+j) = 55-a-2(b+c+d+e)$

And so on round the circle.

So, some code:

from itertools import permutations as perm

a=10
onetoten=frozenset(range(1,11))

for b,c,d,e in perm(range(1,10),4):
  f=55-a-2*(b+c+d+e)
  g=55-b-2*(c+d+e+f)
  h=55-c-2*(d+e+f+g)
  i=55-d-2*(e+f+g+h)
  j=55-e-2*(f+g+h+i)

  s=(a,b,c,d,e,f,g,h,i,j)
  if set(s)==onetoten:

    # sanity check
    if all( sum(s[i%10] for i in xrange(m,m+4))
            ==sum(s[i%10] for i in xrange(m+5,m+9))
            for m in xrange(10)):
      print "solution", a,b,c,d,e,f,g,h,i,j
      break

New Scientist Enigma 152: The highways of Genoland revisited

Following my post on The highways of Genoland, Jim Randell pointed out that the original puzzle had missed a round trip, and that there are actually four round trips. The missing round trip uses highways 1,2,3,4,D (not necessarily in that order).

I wondered what a solution would look like if the fourth round trip had been included in the original puzzle:

As before, no pair of cities is connected by both a national and provincial highway. There are two possible configurations of connections that have eight connectors connecting five nodes:

Configuration A does not provide four round trips, so the five cities are connected in configuration B. We can immediately deduce which city is Geno:

The four  round trips 1,3,4,B,C;   1,2,A,C,D;   2,3,A,B,C;   1,2,3,4,D are in some order: 

Highways 1,2,3,C appear in three round trips (green). 4,A,B,D appear in two round trips (orange)

Geno is reached by the highways that appear in two round trips, namely 4,A,B,D

New Scientist Enigma 152: The highways of Genoland

This was a particularly tricky puzzle to solve with a computer algorithm, as demonstrated by Jim Randell's solution, so here is a manual solution.

The problem statement is:

The five cities of Genoland are interconnected by four national highways A, B, C and D. They are also independently linked by four provincial highways 1, 2, 3 and 4. Each highway connects two cities and Geno is the only city which can be directly reached from every other city. A round trip of the five cities involves the five highways 1, 3, 4, B and C or 1, 2, A, C and D or 2, 3, A, B and C (not necessarily in the order given).

Which of the highways reach Geno?

No pair of cities is connected by both a national and provincial highway (this can be deduced from the round trips). There are two possible configurations that have eight highways connecting five cities:

Configuration A does not provide three round trips, so the five cities are connected in configuration B. We can immediately deduce which city is Geno:

The three round trips are:  

Highway C appears in all three round trips, so we can deduce which highway is C. Highways D and 4 appear in only one round trip each, so we can also deduce 4 and D (national highways are blue, provincial are red)

Highway 1 is in the same round trips as highways 4 and D, so we can deduce highway 1:

As all cities are connected via provincial highways, the remaining highway from the top city must be a provincial. Similarly, as all cities are connected via national highways the remaining highway connecting the bottom right city must be a national:

The round trip using highway 4 uses highways 1,3,4,B,C, so we can deduce which highways are B and 3 :

Similarly, the round trip using highway D uses highways 1,2,A,C,D so we can deduce which highways are A and 2 :

So Geno is reached by highways A,B,D,4

Hamiltonian Cycles on a Square Grid, part 2

The algorithm in my first post on this topic used some of the ideas in  R. Stoyan and V. Strehl: Enumeration of Hamiltonian Circuits in Rectangular Grids. Journal of Combinatorial Mathematics and Combin.Computing 21 (1996), 197-127, but did not employ the construction technique suggested in their paper.

Here is a modified algorithm, with vastly improved performance, using most of the construction method suggested by Stoyan and Strehl.

The algorithm constructs all 1,072 Hamiltonian cycles on a 6 by 6 grid in about 100ms, and all 4,638,576 Hamiltonian cycles on an 8 by 8 grid in about 20 minutes. 

Here, the algorithm runs out of steam, as a 10 by 10 grid has 467,260,456,608 cycles (Sloane A003763)



To construct N by N Hamiltonian cycles, the algorithm builds up  "induced subgraphs" (see diagram at left) of an (N-1) by (N-1) square graph one cell at a time, starting with the top row and working across each row in turn.










The top row is constructed by observing that the corner cells have to be inside the Hamiltonian Cycle, and that no two outside cells can be adjacent.

From then on, cells are added by testing whether a cell can be inside or outside (or both or neither) according to the rule that no 2 by 2 block can be any of these patterns:

A 2 by 2 block $a,b,c,d$ will match one of the four patterns iff $a=d$ and $b=c$




Additional tests check that:

• no 2 adjacent cells on the perimeter can be outside
• the total number of inside and outside cells does not exceed   $\frac{N^2-2}{2}$ and $\frac{(N-2)^2}{2}$ respectively
• After the completion of a row, all inside cells are connected to the row just completed.

Python implementation

Here is the Python code for the algorithm. 

Hamiltonians(N) yields all the Hamiltonian cycles for an N by N grid.