Math Stuff

A Weird Sum

Again, same page,
Show that for positive a, b, c, end d, such that abcd=1, a^2 +b^2+c^2+d^2 + ab+ac+ad+bc+bd+cd is not smaller then 10.
Some notation is in order:
  F(a,b,c,d)= a^2+b^2+c^2+d^2+ab+ac+ad+bc+bd+cd
F(1,1,1,1) is 10. I'll try to show that we can move from (1,1,1,1) to any other coordinate and the value of the function will still be greater than 10. First of all, let's assume that we multiply one of the coordinates by X and one of the others by 1/X. The new coordinates will be:
  Xa, b/X, c,d
Let's calculate F on these coordinates
  F(Xa,b/X,c,d)= X2a2+ b2/X2+ c2+ d2 + 
                 Xab/X + Xac + Xad + 
                         bc/X + bd/X +
                                cd
  F(a,b,c,d)=   a2+ b2+ c2+ d2
                 +ab+ ac+ ad+
                      bc+ bd+
                          cd

  M= F(Xa,b/X,c,d) - F(a,b,c,d)= 
                (X2-1)a2 + (1/X2-1)b2 +
                         (Xa-a)(c+d)
                         (b/X-b)(c+d)

   = (X2-1)a2 - (1-1/X2)b2 +
                 (c+d)a(X-1) + 
                 (c+d)b(1/X-1)
   = (X2-1)a2 - (X2-1)/X2b2 +
                 (c+d)[ a(X-1) - b(X-1)/X ]

   = (X2-1) (a2 - b2/X2) + (c+d)(X-1)(a-b/X)              

   = (X-1)(a-b/X)[ (X+1)(a+b/X) + (c+d) ]
Now, we want M to be always non-negative. The part in square brackets is always positive, so it doesn't contribute a sign to M. We're left with
   U= (X-1)(a-b/X)
If our selection of X makes U non-negative, then F(Xa,b/X,c,d) will be at least 10. For selecting X, we now have two rules: Note that we can use any pair of coordinates instead of the first two, since the function is symmetric with respect to all axes. Also, the coordinates can be exchanged with each other without any change to the function value.

Now, we're left with three cases

The last case is the easiest, we move from (1,1,1,1) to any (a,b,c,d) where the latter conforms to the third form:
PositionResult
Ca Cb Cc Cd X X≥1? X≥green/red? Ca Cb Cc Cd
1 1 1 1 aa≥1 a≥1/1 a A 1 1
a A 1 1 ab ab≥1 [1] a b AB 1
a b AB 1 abc abc≥1 [2] a b c ABC
Here are the validation checks: The first and second case are actually identical, I'll show it for the second case and then show that it applies to the first one as well. Here a, b ≥ 1 and c,d ≤ 1. I choose a and such that ad ≥ 1. Our choices have put our coordinates into the third case. We can reach the point (ad,b,c,1) from (1,1,1,1) since the coordinates conform to the third case.
PositionResult
Ca Cb Cc Cd X X≥1? X≥green/red? Ca Cb Cc Cd
ad b c 1 DD≥1 [3] a b c d
Validation: The first case is done in the same way as above. For a ≥ 1 and b,c,d≤1, the coordinates (ad,b,c,1) conform to the second case. Again, d is chosen such that ad≥ 1.

I have shown that we can reach any point from (1,1,1,1) without violating our rules for the selection of X. Making such selections, we guaranteed to not reduce the value of F. F(1,1,1,1) is 10, so all values of F are at least 10.

Interestingly, the rules for choosing X don't depend on the number of variables. As long as you can show these movements, value of F will never go below F(1*).

A Geometric Sum

I was doing something else and I had to sum this series: Σ[k=1..n] k.ak. It's a basic series widely known and it was certainly on the internet but I wanted to do it myself. First, let's write down the terms in a table:
k
1a
2 a2 a2
3 a3 a3 a3
.. ..
n an an an .. an
Obviously, this table can be summed up by the columns as well:
k.j 1 2 3 .. n
1a
2 a2 a2
3 a3 a3 a3
.. ..
n an an an .. an
So we have a double sum:
S= j=1 n k=j n ak
k=j n ak = a n+1 - a j a-1
S= j=1 n a n+1 - a j a-1 = 1 a-1 j=1 n a n+1 - 1 a-1 j=1 n a j
(a-1)S= nan+1 - an+1 - a a-1

Transitivity of Implication

I'm getting rusty on the logical stuff. I haven't done it for like 20 years. Let's try:
(a->b) & (b->c) -> (a->c)
We have:
(a->b) == a'+b
Let's go:
   (a->b) &  (b->c)    -> (a->c)
  ((a->b) &  (b->c))'   + (a->c)
   (a->b)' + (b->c)'    + (a->c)
   (a'+b)' + (b'+c)'    + (a->c)
     ab'   +  bc'       +  a'+c
We can easily AND the complex terms with the value TRUE:
    ab' = ab'(c+c') =  ab'c+ ab'c'
    bc' = (a+a')bc' =  abc'+ a'bc'
So, the last form becomes:
     ab'   +  bc'       +  a'+c

  ab'c+ ab'c' +  abc'+ a'bc' + a' +c
                       ----    -
Factor by a':

  ab'c+ ab'c' + abc' + a'(bc'+1) + c
  ab'c+ ab'c' + abc' + a' + c
  ----                      -
Factor by c:
  ab'c' + abc' + a' + c(1+ab')
  ab'c' + abc' + a' + c
  ----    ---
Factor by ac':
  ac'(b'+b) + a' + c
  ac' + a' + c
Now, observe that   a'+c  = (ac')'

  ac' + (ac')'  = 1.

Logic 2: Removing Extra Term in Implication

Now, I'd like to do this:
    (a->b+c) -> ( a+b -> b+c )

    (a'+b+c) -> [ (a+b)' + b + c ]
    (a'+b+c) -> (  a'b'  + b + c )
    (a'+b+c)' +    a'b'  + b + c
     ab'c'    +    a'b'  + b + c
Just like above, let's AND a'b' with TRUE:
     ab'c'    +   a'b'      + b + c      // a'b'= a'b'c + a'b'c' 
     ab'c' + a'b'c + a'b'c' + b + c
                 -                -
Factor by c :
     ab'c' + a'b'c' + b + c(1+a'b')
     ab'c' + a'b'c' + b + c
      ---      ---
Factor by b'c' :
     b'c'(a+a') + b + c
     b'c'       + b + c
Again, we observe that  b+c = (b'c')'
     b'c' + (b'c')'  = 1.

Math Puzzle : Digits

On this page, I found a neat puzzle. Here it is:
Show that for any natural n, at least one of two numbers, n or n+1, can be represented in the following form: k + S(k) for a certain k, where S(k) is the sum of all digits in k. For instance, 21 = 15 + (5+1).
I'll try to solve it here. Let's first reformulate the problem:
   F(y)= y + S(y)
   P(n) iff F(k) = n for some k
   L(n) iff P(n) or P(n+1).
I already know that L(n) is true for small numbers 4=2+2, 6=3+3 etc. I need to show:
   L(n) -> L(n+1)
If I expand it:
   P(n) or P(n+1) -> P(n+1) or P(n+2)             .. ST-1
It's sufficient to prove:
   P(n) -> P(n+1) or P(n+2)                       .. ST-2
Since ST-1 is true whenever ST-2 is true (i.e. ST-2 implies ST-1). So, given P(n) if I can construct a valid P(n+1) or P(n+2), I'm done.

Let's assume P(n), ie. for some k, F(k) = n.

   F(k) =  k + S(k) =  n
I won't consider single-digit values for k, I can simply list the corresponding n-values for those and don't really need this proof for small numbers. Basicly, for k <= 9, n= 2*k. So we're concerned with n>18.

There are two cases here, either k ends with a 9 or not. The first case is easy:

    k =  B|a      , B= arbitrary string (not including null), 0<=a<9
  k+1 =  B|c      , c= a + 1
             The | symbol is the concatentation operator, a and c are
             digits.

  S(B|c) = S(B|a) + 1

  F(k+1)=  k + 1 + S(k+1)
        =  k + 1 + S(B|c)
        =  k + 1 + S(B|a) + 1
        =  k + S(B|a) + 2
        =  F(k) + 2
        =  n + 2
I've constructed k' = k+1 from k and reached at F(k')= n +2. For a given n, we find the corresponding k (which doesn't end with a 9) and then construct n+2 using that. So, the preposition now holds for n+1 if this is the case, since one of n+1 and n+2 can be written as F(k'). What happens if there is no such k, ie. k ends with a 9?
      k= B|a|9[z]     ,  B= arbitrary, a!=9, followed by z-9s, z>0

   S(k)= S(B|a|9[z])
       = S(B) + S(a) + 9z                   .. EQ-1
Let's look at what happens to F(k+1):
   k + 1 =  B|a|9[z] + 1
         =  B|c|0[z]        , c= a +1

   S(k+1)=  S(B|c|0[z])
         =  S(B) + S(c)
         =  S(B) + S(a) + 1      ,  S(c)= S(a) +1 
         =  S(k) - 9z + 1        ,  S(B)+S(a) is  S(k) - 9z , from EQ-1
                                           ..  EQ-3

   F(k+1)=  k+1  + S(k+1)
         =  k+1  + S(k) - 9z + 1
         =  k+S(k) + 2 - 9z
         =  F(k) + 2 - 9z
         =  n + 2 - 9z
It didn't quite work, but we have some clue. L(9z-1) should also be true since 9z-1 < n:
   n= F(k) = k + S(k)
   n > k               , S(k) >= 1 
   k = B*10^(z+1) + c*10^z + 9*10^(z-1) + 9*10^(z-2) .. 9*1
                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                               z terms, each not less than 9
   k >= 9z
   n > k > 9z-1
Since L(9z-1) is true, one of the following is true:
  1. F(u) = 9z-1 for some u
  2. F(u) = 9z for some u
In order to make life easier, let's collect them into one expression and be done with it:
    F(u)= 9z + j,   j in {0,-1}              .. EQ-4
I'll now construct a string from u by padding it to the left by zeroes so that its total length is z.
    u= Y
    V= 00..0|Y
       ^^^^^^^
      z digits 
The numerical value of V is simply u. I will use this string to construct a k' from a known k.
        k'= B|c|V
     F(k')= B|c|0[z] + u  + S(B|c|V) 
          = k+1  + u  + S(B|c|0[z]) + S(V)
          = k+1 + S(k+1)       + u + S(V)
          = k+1 + S(k) -9z +1  + u + S(V)       , from EQ-3
          = k+ S(k) + 2 - 9z + u + S(V)
          = n + 2 - 9z + F(u)
          = n + 2 - 9z + 9z + j                 , from EQ-4
          = n + 2 + j  ,  j in {0,-1}

 for j= 0,
       F(k') = n +2
 for j= -1
       F(k') = n +1
So, starting with n and k, I computed a k' which gives either F(k')= n+1 or F(k')=n+2. This is what I was looking for. In summary, given F(k)= n
   F(k+1) = n+2     if  k doesn't end with a 9.
    F(k') = n+2 or n+1
        k = Ba9[z]
        k'= Bc000..0Y
          where F(Y)= 9z or 9z-1

Math Puzzle: Party

From the same page as the previous one:
There is a group of people at a party. Show that you can introduce some of them to each other so that after the introduction, no more than two people in the group would have the same number of friends (initial configuration doesn't work because they all initially have 0 friends).
Let N be the number of people in the group and let's sort the people according to how many other people they know. We will get a string of numbers, where each number is between 1 and N-1. We don't consider the case where somebody doesn't know anyone because it's a party.

For small values of N, it's easy to make the arrangement.

   N     Arrangement
   -----------------
   2     1 1
   3     1 1 2
   4     1 2 2 3
   5     1 2 2 3 4
In any case, we will end up with a string like this:
   1 2 3 ... k k ... N-1
When someone comes to the party, we don't introduce him to the first k people in the sorted order. We introduce him to the remaining N-k people.
         Already There               New Guy
        ------------------------------------
Before:  1 2 3 ... k k ... N-1        0   
 After:  1 2 3 ... k k+1 ... N       N-k 
 
         Set k' = N-k

Sorted:  1 2 3 ... k' k' ... N        - 

Leonardo Numbers

Leonardo numbers are similar to Fibonacci numbers. They have a similar definition:
  L(0)=  1
  L(1)=  1
  L(n)=  L(n-1) + L(n-2) + 1

  L   =  1 1 3 5 9 15 25 41 67 109 ...
I saw this smoothsort algorithm on the Internet and on this page, there is some explanation of it. I couldn't understand the proof there, so I made my own. The lemma to be proved is:
Any positive integer can be written as the sum of O(lg n) distinct Leonardo numbers.
In the first part, I will show that a sum is possible, without looking at the number of Leonardo numbers used. In the second part, I will prove that this number is O(lg n).

Let's reformulate it as follows:

   n          = leo_sum(X)
   leo_sum(X) = SUMi L(Xi), over Xi ∈ X
The lemma holds for the following numbers:
n sequence sum
1 L(0)1
2 L(0)+L(1)1+1
3 L(2)3
4 L(1)+L(2)1+3
Let's assume that it holds for n, and we will construct a sequence for n+1. Without loss of generalization, we can assume Xi is sorted, i.e.
  Xi > Xj ,if i > j
Given n and X, we will compute Y for (n+1).
   n   =  SUMi L(Xi), where Xi ∈ X
   n+1 =  SUMi L(Yi), where Yi ∈ Y
Let a be the highest number in X, where a-1 is also an element of X.

If there is no such number, either 0 or 1 isn't an element of X. We simply add 0 or 1 to X in order to obtain Y.

   Y = X ∪ { 0 } ,  0 ∉ X, a doesn't exist
   Y = X ∪ { 1 } ,  1 ∉ X, a doesn't exist

   leo_sum(Y) = leo_sum(X) + 1 = n + 1
If there is such an a, then we remove a and a-1 from X and add a+1 to obtain Y.
   Y= X - { a-1 , a } ∪ { a+1 } ,  { a-1, a }  subsetorequal X
We know that the newly added element a+1 was not already in X because of the definition of a. If (a+1) was already in X, we would have chosen that value. By the definition of Leonardo numbers:
   L(a+1)     =  L(a) + L(a-1) + 1

   leo_sum(Y) =  leo_sum(X) - L(a-1) - L(a) + L(a+1)
              =  leo_sum(X) + 1
              =  n + 1
The second part is done clearly enough in the page I referenced, so I'm going to skip it.

This proof is sufficient, but it doesn't match the one in the referenced page and so doesn't help us with the smoothsort algorithm. I'll do another one.

Leonardo Numbers 2

Let us represent a number with a binary-leonardo string Di, read from right to left:
   n= SUM Di*L(i),   0 <= i <= N , Di ∈ { 0, 1 }

   n= BL( DN DN-1 ... D1 D0 )
We want to prove that:
for any positive integer n, there is a sequence x0, x1, ..., xk such that:
This translates to our notation as follows:
Any positive integer can be written as a binary-leonardo string of the form:
  1. R 010 0M, or
  2. P 011 0M
Where P and R don't contain the substring 11 and M >= 0.
Now, let us construct the binary-leonardo strings for the first few numbers:
n string sum
1 101
2 111+1
3 1003
4 1103+1
5 10005
6 10105+1
We have
  n = BL(D)
and we want to find G such that
  n + 1 = BL(G)
Both D and G are of the given forms [1] or [2].

Let us assume that D is of the first form. If we add the number 1 to D, we will have:

  n + 1 = BL( R 010 0M ) + 1      , M >= 0
  n + 1 = BL( R 01 0M+1 ) + 1     
    L(0)= 1
  n + 1 = BL( R 01 0M+1 ) + L(0)  
  n + 1 = BL( R 01 0M 1 )        
  G     = R 01 0M 1        , M >= 0
Here, if M is 0 or 1, then we end up with a string of the second form:
 M= 0
   G=  R 01 1
 M= 1
   G=  R 01 0 1
     exchange G0 and G1
   G'= R 0 1 1 0
If M is 2 or more, we have:
   0M = 0K 0 0         , K = M-2 >= 0
   G =  R 01 0K 0 0 1 
     exchange G0 and G1
   G' =  R 01 0K 0 1 0 , K = M-2 >= 0
which is of the first form.

Now let's handle the case where D is of the second form. i.e

   D=  P 011 0M  , P doesn't contain substring 11, M >= 0
When we add 1 to this number, the substring 011 above gets replaced by 100 because of the definition of the Leonardo numbers:
   n = BL( P 011 0M )
   n = BL( P 000 0M ) + BL( 011 0M )
   n = BL( P 000 0M ) + L(M+1) + L(M)
 n+1 = BL( P 000 0M ) + L(M+1) + L(M) + 1
 n+1 = BL( P 000 0M ) + L(M+2)
 n+1 = BL( P 000 0M ) + BL( 100 0M )
 n+1 = BL( P 100 0M ) 
   G = P 1 0M+2    , M >= 0
Since P doesn't contain the substring 11, it can only end with 00, 01 or 10.
   P= Y P1 P0
   G= Y P1 P0 1 0M+2

P0=  0
   G= Y P1 0 1 0M+2 
    = Y P1 010 0M+1           G is of the first form

P1P0=  01
   G= Y 0 1 1 0M+2           G is of the second form

For P0=0 case, since P doesn't contain the substring 11, neither does YP1.

So, for both forms of D for n, we computed G for n+1 and showed that this can be done according to the forms we have limited ourselves to.

Puzzle: Intellectual power of a dragon pack

This is a puzzle from the page I previously mentioned:
Dragons have to meet for a brainstorm in a convention center. The delegates have to be selected to provide the maximum efficiency of the brainstorm session. A dragon has any amount of heads, and for any N, any amount of N-headed dragons is available if needed. The problem is that the size of the convention center is limited so no more than 1000 heads can fit into the assembly hall. The intellectual power of a dragon pack is the product of head numbers of dragons in the pack. How should an optimum pack look like (the total number of dragons, the head number distribution)?
Obviously, no dragon should have just one head, such a dragon would eat up one head space from the total 1000 and not contribute any power at all.

Let's assume that 3 dragons have 2 heads in the pack. They total 2+2+2=6. 6 heads could better be redistributed as 3+3 heads which contributes 9 to the pack's power instead of 8. So, this case also doesn't occur in the optimum pack. It has at most 2 dragons with 2 heads.

Let's consider the number 4. If a dragon has 4 heads, it could be replaced by two dragons with 2 heads each. The sum is the same, the product is the same and there is no other way to improve the situation. For convenience, we can split all 4 headed dragons in this way without any change to the total pack power. I will do this and ban the number 4 from the pack.

How about numbers greater than 4? Let p > 4 be the head count of a dragon in the pack. If it's odd, this number can be written as:

  p= 2k + 1              for integer k ≥ 2
We see that, if we replace each such dragon with two dragons who have k and k+1 heads, we improve the product.
  p= 2k + 1

  p0= k  ,  p1= k+1

  p0*p1 = k^2 + k

  k^2 + k > 2k + 1
  
  k^2 > k + 1       since k ≥ 2
Before the split, the dragon contributed p amount of power to the pack. After the split, the two new dragons contribute p0*p1 amount of power, which is greater than p. So, no odd number greater than 4 can occur in the optimum pack.

Similar reasoning applies to even-headed dragons:

  p= 2k

  p0= k  ,  p1= k

  p0*p1= k^2

  k^2 > 2k        since k > 2
So, we have banned We are left with the numbers 2 and 3. A dragon with 3 heads can't be replaced with anything that improves the power contribution. You could split it up as 2+1 or 1+1+1, which decrease the power. Similarly, 2 can't be split either.

We already know that no more than two dragons can have 2 heads. Let's consider the cases.
2-headed3-headedTotalPowerPower/3^332
03339993^3333
13329982*3^3322
233210002^2*3^3324
So, the last case is the optimum distribution. 2 dragons with 2 heads each, and 332 dragons with 3 heads each.

Interestingly, we didn't use the number 1000 until the very end. All other arguments work for any arbitrary number of total heads. The following gives the formula for N total heads:
N2-headed3-headedPower
3k0k3^k
3k+12k-14*3^(k-1)
3k+21k2*3^k

Toy Fermat

Heh, I like solving these puzzles. Here is another one:
Does the equation, x^2 + y^3 = z^4 have solutions in prime numbers? Find at least one if yes, give a nonexistence proof otherwise.
Now, let's think about whether x,y,z are odd numbers or not. The parity of the left side must be the same as the right side of the equation. If all of them are odd numbers, the equation doesn't work. Left side becomes even and the right side is still odd. So, at least one of them is 2, the only even prime.

x and y can't be both 2. The left side then becomes 12, which isn't the fourth power of any integer.

x and y can't be both odd primes. In that case, the left side becomes even. This necessiates that z is 2. However, that's impossible. The smallest value for y is 3. When we put that into the sum, we get a negative number for x2 since 24-33 is -11.

So, z isn't 2 and exactly one of x and y is 2. We have two cases:

Case 1 is quite easy. We see that, for any odd prime x, x2+8 is never a perfect odd square. For x>=3, the smallest odd square after x2 is (x+2)2. The difference between the two is 4x+4, which is always larger than 8.

Case 2 is also easy when think of the equation in mod 3 arithmetic. We have three cases:

If case 2.A is true, then y must be 3 since it's a prime. This results in a value of 22+33= 31, which isn't a fourth power of an integer.

If case 2.B is true, then we get the equation:
4 + 12 ≡ z4 (mod 3)
1 + 1 ≡ z4 (mod 3)
2 ≡ z4 (mod 3)
Let's have a look at the powers of numbers in mod3.
z z2 z3 z4
0 0 0 0
1 1 1 1
2 1 2 1
We see that z4 ≡ 2 (mod 3) doesn't hold for any z. So, 2.B can't be true either.

Case 2.C is rather trivial: if y ≡ 2 (mod 3), then the equation becomes:

  4+ 23 ≡ z4 (mod 3) 
  1 + 2 ≡ z4 (mod 3) 
  0 ≡ z4 (mod 3) 
  0 ≡ z  (mod 3) 
      z= 3.      (since z is a prime)
However, this doesn't work either:
  4 + y3 = 34 
  4 + y3 = 81 
   y3 = 77 
This doesn't have an integer solution.

Links

Math puzzles
mathematical puzzles
The Ultimate Puzzle Site - Mathematical Problems
Nick's Mathematical Puzzles: 1 to 10
Mathematical puzzles, with hints, full solutions, and links to related math topics. Puzzles 1 to 10.
Erich's Math Puzzles
Math Forum - Ask Dr. Math
How can you find the center of a circle using a ruler and compass?
Ptolemy's Inequality - AoPSWiki
Mathematical Illustrations
Rotation Matrix -- from Wolfram MathWorld
Plus Magazine
Plus Online Maths Magazine
ASCIIMathML.js demo
On what day of the week were you born? | plus.maths.org
Calculate duration between two dates – results
Results page for date calculator, showing days between two dates.
Stern-Brocot tree - Wikipedia, the free encyclopedia
5 Ways to Solve Recurrence Relations - wikiHow
How to Solve Recurrence Relations. In trying to find a formula for some mathematical sequence, a common intermediate step is to find the nth term, not as a function of n, but in terms of earlier terms of the sequence. For example, while...
Guided exercises [new thread] (Page 1) / Exercises / Math Is Fun Forum
Puzzles and Games (Page 1) / Math Is Fun Forum