viernes, 24 de marzo de 2017

1065. Staircase numbers

    Pepe Chapuzas was talking on powers of two... 

    Dear Taecher:
    a) Powers of two appear in the chessboard problem and the number of wheat grains. Do you remember?
2= 1
2= 2
2= 4
2= 8
2= 16
2= 32
2= 64
...

    b) With only two symbols we can write all the numbers! The binary (or base-two) numeral system is a positional notation as well as our decimal numeral system but with only two different bit figures (0 and 1) instead our ten digit figures. The bit 1 represents a power of two (1, 2, 4, 8, 16, 32, 64, ...) according to its position in the binary number, from the rightmost place to the leftmost place...

    c) For great powers of two we have some prefixes. Be careful because, strictly, 1 kibi > 1 kilo.


1 kibi = 210 = 1024   >   1 kilo = 103 = 1000
1 mebi = 220 = 1048576   >   1 mega = 106 = 1000000
1 gibi = 230 = 1073741824   >   1 giga = 109 = 1000000000

    d) A natural number can be written as a sum of two or more consecutive natural numbers if and only if it is not a power of two... These naturals are known as staircase numbers (also trapezoidal numbers or polite numbers). Powers of two were impolite!

    I interrupted Pepe. Item d) needed a detailed explanation... If that was true... what made powers of two so quirky? Pepe went on...

    Dear Teacher:
    There are two kinds of natural numbers: A natural can be either a power of two or a staircase number, but not both at the same time... So, 15 is not a power of two and it is a staircase number because it is a sum of consecutive naturals (and to top it off in two ways):


15  =  4 + 5 + 6  =  7 + 8

     Why 16 cannot be a staircase number? The answer is amazing: because 16 has no odd divisors! (We don't consider the number 1 as a divisor here now.) A natural number is a power of two if and only if has no odd divisors because the number 2 is the only even prime, is it not? I'll prove that powers of two cannot be staircase numbers by showing that every staircase number has at least one odd divisor...

    The staircase number  a+...+b  (a<b) is an arithmetic progression with  b–a+1  terms. So,


a+...+b = (a+b)·(b–a+1):2


    Hence either  a+b  or  b–a+1  is an odd divisor (and greater than 1).

    I'll prove now that if a natural number is not a power of two then it is a staircase number.

    If  n  is not a power of two, it has an odd divisor  k . Also  k2  is odd and there are two cases: either  k2 < 2n  or  k2 > 2n.

    If  k2 < 2n  then  n:k > k:2  and  n = a+...+b , with  a = n:k–k:2+1:2  and  b = n:k+k:21:2 , is a staircase number with  k  addends (steps).

b–a+1 = n:k+k:2–1:2–n:k+k:2–1:2+1 = k
(a+b)(b–a+1):2 = (n:k–k:2+1:2+n:k+k:2–1:2)·k:2 = n

    If  k2 > 2n  then  k:2 > n:k  and  n = a+...+b , with  a = k:2–n:k+1:2  and  b = k:2+n:k–1:2 , is a staircase number with  2n:k  addends (steps).


b–a+1 = k:2+n:k–1:2–k:2+n:k–1:2+1 = 2n:k
(a+b)(b–a+1):2 = (k:2–n:k+1:2+k:2+n:k–1:2)·2n:k:2 = n

    To finish I ordered to write 6464 as a staircase number. Nina Guindilla did it:

    Dear Teacher:
    Since  101= 10201  <  2·6464 = 13938 , then


a = 6464:101–101:2+1:2 = 14
b = 6464:101+101:2–1:2 = 114
and
6464 = 14+15+16+17+...+114

jueves, 16 de marzo de 2017

1411. Angles and fish.


    Which angle is the greatest one? I admit that my question had a certain amount of malice and was overcome by the subtleness of Nina Guindilla's response...

    Dear Teacher:
    The big fish eats the little fish but angles are not fish...
    The exercise on angles was easy:

    Nina Guindilla commented that it was very easy from the formulas for the angles outside and inside a circle.

alpha + beta  =  gamma/2 + delta/2 + gamma/2 – delta/2  =  gamma
alpha – beta  =  gamma/2 + delta/2 – gamma/2 + delta/2  =  delta

miércoles, 15 de marzo de 2017

1266. The mediant of two fractions

    A very common error with fractional sums is

    Although sometimes (or frequently) there are surprises: the mistake is not a mistake...

    We are talking about the mediant of two fractions... I'm using a heart to denote it:
   ( The mediant of  3/8  and  2/7  is  5/15 .)

    If the denominators are positive, the mediant of two fractions is between both of them on the real number line:

    The mediant of two fractions is a weighted arithmetic mean... The positive denominators are the weights...


a/b  ♡  c/d  =  (a+c) / (b+d)  =  (a/b · b + c/d · d) / (b+d)


    Mediants are related to the slope of the vector sum...
    Mediants appear in the Farey sequences... For each natural number  n  we have a Farey sequence consinsting of the irredutible fractions  p/q , such that  0pqn , arranged in order of increasing size. For  n = 6  the Farey sequence are


0/1    1/6    1/5    1/4    1/3    2/5    1/2    3/5    2/3    3/4    4/5    5/6    1/1

    It is easy to test that here every fraction (except the first one and the last one) is equivalent to the mediant of its neighbors. (This happens in all the Farey sequences.) In this, the mediant of the 8th fraction and the 10th fraction is equivalent to the 9th fraction:


3/5  ♡  3/4  =  6/9  =  2/3

    Mediants also appear with the Ford circles... Given an irreductible fraction  p/q , its Ford circle is on the fist quadrant, is tangent to the x-axis at the point  p/q , and its diameter measures  1/q. Two different Ford circles are either disjoint or tangent to each other. If three Ford circles are tangent to one another, and if the irreductible fractions associated to the two largest ones are  a/b  and  c/d , then the irreductible fraction associated to the smallest one is  a/b  ♡  c/d . (This is a beautiful exercise...)

    This last drawing reminded Nina Guindilla of the third Japanese theorem. (A theorem of Mikami and Kobayashi's. The first and the second Japanese theorems are very beautiful too...)

    Dear Teacher:

    If three circles and a straight line are tangent to one another and if the radii of the circles are  r ,  s  and  t  (r<st), then


1/r  =  1/s + 1/t

    Pepe Chapuzas gave a proof:

    Dear Teacher:
    We have three right angled triangles and Pythagoras' theorem.
    The three sides of the blue triangle are


t + s
t – s
√ [ (t+s)– (t–s)]  =  2√(ts)

    The three sides of the green triangle are


t + r
t – r
√ [ (t+r)– (t–r)2 ]  =  2√(tr)

    The three sides of the violet triangle are


s + r
s – r
[ (s+r)– (s–t)]  =  2√(sr)
    So,
 2√(ts)  =   2√(tr) + 2√(sr)
    And dividing by  2√(tsr)

1/r  =  1/s + 1/t    Q.E.D.

    (The proof is valid when  t = s .)
    Finally, Pepe also solved the exercise on the Ford circles...

    Dear Teacher:
    I may assume that b<d. (If you want, you may do it with b>d. It is not possible b=d, is it?)
    The diameters of the two largest circles are
2t  =  1/b2
2s  =  1/d2
    We just saw that
c/d – a/b  =  2√(ts)  =  √(2t·2s)  =  1/(bd)
    So, the determinant
bc – ad  =  1

    (If  bc – ad  =  0 , then the circles would be coincident.)
    (If  bc – ad  >  1 , then the circles would be disjoint.)

    We can do the determinant test with the mediant to prove the third circle to be tangent to the other two.

a(b+d) – b(a+c)  =  ab + ac – ba – bd  =  1
(a+c)d – (b+d)c  =  ad + cd – bc – dc  =  1

    So, the mediant  a/b  ♡  c/d  =  (a+c) / (b+d)  is an irreductible fraction. The diameter of its Ford circle must be
2r  =  1/(b+d)2

    This is true because according to the third Japanese theorem we'd have

1/√(2r)  =  1/√(2s) + 1/√(2t)  =  b + d

lunes, 13 de marzo de 2017

1420. A parabolic sieve

    Pepe Chapuzas was drawing the graph of the funcion  y = x2  with the following values:


    (Values for  x = –1  and  x = 1  were skipped.) First, Pepe drew the points (red dots), so he got a beautiful parabola... After this, he matched by straight lines the red points on the 1st quadrant with the red points on the 2nd quadrant... Every line crossed the parabola axis at a natural number. If we went on getting red points by giving integer values to  x  (different to –1 and 1), then all the natural numbers on the parabola axis would be crossed out by these lines except the primes. (Here, the number 1 would be included among the primes and wouldn't be crossed out.) This parabola worked as Eratosthenes' sieve!



    Dear Teacher:
    This is Matiyasevich and Stechkin's sieve. And it's easy to explain its functioning...
    For every  m  and every  n  (natural numbers greater than 1), the straight line passing through the points  N(–n, n2)  and  M(m, m2)  (points of the parabola on different quadrants) is


y  =  (m2–n2)/(m+n) · (x+n) + n2 
y  =  (m–n) · (x+n) + n2

    And the intersection point between the straight line and the parabola axis is 


x = 0
y =  (mn) · n + n2 = m·n

    But  y = m·n  is a natural number and is not a prime. So, all the natural numbers except the primes are crossed out and this parabola is an authentic sieve for the primes.

martes, 7 de marzo de 2017

1288. More about side midpoints

    Given a triangle, its inellipses are its inscribed ellipses, that is, the ellipses tangent to the three sides of the triangle. The Steiner inellipse of the triangle is the unique inellipse passing through the three side midpoints of the triangle, that is, the ellipse tangent to the three sides at their midpoints. (Furthermore, the Steiner inellipse has the largest area of any inellipse.)

    Imagine a triangle on the complex plane... Marden's theorem states that if the three vertices of that triangle are the zeroes of a cubic polynomial, then the zeroes of the derivative of the polynomial are the foci of the Steiner inellipse... 
    Assuming Marden's theorem, can you prove that the center  (k)  of the Steiner inellipse, the barycenter  (g)  of the given triangle and the zero  (h)  of the second derivative of the cubic polynomial are the same point? Pepe Chapuzas was able...

    Dear Teacher:
    How beautiful is this theorem!
    If  a, b, c  are the vertices of the triangle, then its barycenter is


g  =  (a+b+c) / 3

    And the cubic polynomial and its derivatives are

P (z)  =  (za)·(z–b)·(z–c) · d     with    d  0
P (z)  =  ( z– (a+b+c)·z+ (ab+ac+bc)·z – abc ) · d
P ' (z)  =  ( 3·z– 2·(a+b+c)·z + ab + ac + bc ) · d
P '' (z)  =  ( 6·z – 2·(a+b+c) ) · d


    According to Marden's theorem, the foci of the Steiner inellipse are the zeroes of  P ' (z) . If

3·z– 2·(a+b+c)·z + ab + ac + bc  =  0

and  Δ  is the discriminant of this equation, its zeroes (the foci) are

f1  =  ( 2·(a+b+c) Δ ) / 6
f2  =  ( 2·(a+b+c) – Δ ) / 6

    The center of the Steiner inellipse shall be the midpoint of the segment between the foci:


k  =  ( f1 + f2 ) / 2  =  (a+b+c) / 3


    Finally, if  h  is the zero of  P '' (z)  then...

P '' (h)  =  ( 6·h – 2·(a+b+c) ) · d  =  0
6·h – 2·(a+b+c)  =  0
h  =  (a+b+c) / 3 

g  =  k  =  h    Q.E.D.