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+cdF(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,dLet's calculate F on these coordinates

F(Xa,b/X,c,d)= XNow, 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^{2}a^{2}+ b^{2}/X^{2}+ c^{2}+ d^{2}+ Xab/X + Xac + Xad + bc/X + bd/X + cd F(a,b,c,d)= a^{2}+ b^{2}+ c^{2}+ d^{2}+ab+ ac+ ad+ bc+ bd+ cd M= F(Xa,b/X,c,d) - F(a,b,c,d)= (X^{2}-1)a^{2}+ (1/X^{2}-1)b^{2}+ (Xa-a)(c+d) (b/X-b)(c+d) = (X^{2}-1)a^{2}- (1-1/X^{2})b^{2}+ (c+d)a(X-1) + (c+d)b(1/X-1) = (X^{2}-1)a^{2}- (X^{2}-1)/X^{2}b^{2}+ (c+d)[ a(X-1) - b(X-1)/X ] = (X^{2}-1) (a^{2}- b^{2}/X^{2}) + (c+d)(X-1)(a-b/X) = (X-1)(a-b/X)[ (X+1)(a+b/X) + (c+d) ]

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:

- X ≥ 1
- X ≥ b/a

Now, we're left with three cases

- One coordinate is greater than or equal to 1: a ≥ 1 > b,c,d > 0
- Two coordinates are greater than or equal to 1 : a,b ≥ 1 > c,d > 0
- Three coordinates are greater than or equal to 1 : a,b,c ≥ 1 > d > 0

Position | Result | |||||||||

C_{a} |
C_{b} |
C_{c} |
C_{d} |
X | X≥1? | X≥green/red? | C_{a} |
C_{b} |
C_{c} |
C_{d} |

1 | 1 | 1 | 1 | a | a≥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 |

- [1] ab ≥ 1/A ; ab ≥ a ; b ≥ 1
- [2] abc ≥ 1/AB ; abc ≥ ab ; c ≥ 1

Position | Result | |||||||||

C_{a} |
C_{b} |
C_{c} |
C_{d} |
X | X≥1? | X≥green/red? | C_{a} |
C_{b} |
C_{c} |
C_{d} |

ad | b | c | 1 | D | D≥1 | [3] | a | b | c | d |

- [3] D ≥ 1/ad ; D≥ AD ; 1≥A

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*).

k | |||||

1 | a | ||||

2 | a^{2} |
a^{2} |
|||

3 | a^{3} |
a^{3} |
a^{3} |
||

.. | .. | ||||

n | a^{n} |
a^{n} |
a^{n} |
.. | a^{n} |

k.j | 1 | 2 | 3 | .. | n |

1 | a | ||||

2 | a^{2} |
a^{2} |
|||

3 | a^{3} |
a^{3} |
a^{3} |
||

.. | .. | ||||

n | a^{n} |
a^{n} |
a^{n} |
.. | a^{n} |

$S=\sum _{j=1}^{\mathrm{n}}\sum _{k=j}^{n}{a}^{k}$

$\sum _{k=j}^{n}{a}^{k}=\frac{{a}^{n+1}-{a}^{j}}{a-1}$

$S=\sum _{j=1}^{\mathrm{n}}\frac{{a}^{n+1}-{a}^{j}}{a-1}=\frac{1}{a-1}\sum _{j=1}^{\mathrm{n}}{a}^{n+1}-\frac{1}{a-1}\sum _{j=1}^{\mathrm{n}}{a}^{j}$

$(a-1)S=n{a}^{n+1}-\frac{{a}^{n+1}-a}{a-1}$

(a->b) & (b->c) -> (a->c)We have:

(a->b) == a'+bLet'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'+cWe 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.

(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 + cJust 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.

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-1It's sufficient to prove:

P(n) -> P(n+1) or P(n+2) .. ST-2Since 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) = nI 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 + 2I'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-1Let'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 - 9zIt 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-1Since L(9z-1) is true, one of the following is true:

- F(u) = 9z-1 for some u
- F(u) = 9z for some u

F(u)= 9z + j, j in {0,-1} .. EQ-4I'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 digitsThe 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 +1So, 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

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 4In any case, we will end up with a string like this:

1 2 3 ... k k ... N-1When 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 -

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) = SUMThe lemma holds for the following numbers:_{i}L(X_{i}), over Xi ∈ X

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 |

XGiven n and X, we will compute Y for (n+1)._{i}> X_{j},if i > j

n = SUMLet a be the highest number in X, where a-1 is also an element of X._{i}L(X_{i}), where Xi ∈ X n+1 = SUM_{i}L(Y_{i}), where Yi ∈ Y

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 + 1If 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 XWe 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 + 1The 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.

n= SUM DWe want to prove that:_{i}*L(i), 0 <= i <= N , Di ∈ { 0, 1 } n= BL( D_{N}D_{N-1}... D_{1}D_{0})

for any positive integer n, there is a sequence x0, x1, ..., xk such that:This translates to our notation as follows:

- SUM L(x
_{i}) = n- x
_{0}< x_{1}< ... < x_{k}.- If x
_{0}= 0, then x_{1}= 1.- For any i > 0, x
_{i}+ 1 < x_{i+1}

Any positive integer can be written as a binary-leonardo string of the form:Now, let us construct the binary-leonardo strings for the first few numbers:Where P and R don't contain the substring 11 and M >= 0.

- R 010 0
^{M}, or- P 011 0
^{M}

n | string | sum |
---|---|---|

1 | 10 | 1 |

2 | 11 | 1+1 |

3 | 100 | 3 |

4 | 110 | 3+1 |

5 | 1000 | 5 |

6 | 1010 | 5+1 |

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 0Here, if M is 0 or 1, then we end up with a string of the second form:^{M}) + 1 , M >= 0 n + 1 = BL( R 01 0^{M+1}) + 1 L(0)= 1 n + 1 = BL( R 01 0^{M+1}) + L(0) n + 1 = BL( R 01 0^{M}1 ) G = R 01 0^{M}1 , M >= 0

M= 0 G= R 01 1 M= 1 G= R 01 0 1 exchange GIf M is 2 or more, we have:_{0}and G_{1}G'= R 0 1 1 0

0which is of the first form.^{M}= 0^{K}0 0 , K = M-2 >= 0 G = R 01 0^{K}0 0 1 exchange G_{0}and G_{1}G' = R 01 0^{K}0 1 0 , K = M-2 >= 0

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

D= P 011 0When we add 1 to this number, the substring 011 above gets replaced by 100 because of the definition of the Leonardo numbers:^{M}, P doesn't contain substring 11, M >= 0

n = BL( P 011 0Since P doesn't contain the substring 11, it can only end with 00, 01 or 10.^{M}) n = BL( P 000 0^{M}) + BL( 011 0^{M}) n = BL( P 000 0^{M}) + L(M+1) + L(M) n+1 = BL( P 000 0^{M}) + L(M+1) + L(M) + 1 n+1 = BL( P 000 0^{M}) + L(M+2) n+1 = BL( P 000 0^{M}) + BL( 100 0^{M}) n+1 = BL( P 100 0^{M}) G = P 1 0^{M+2}, M >= 0

P= Y P_{1}P_{0}G= Y P_{1}P_{0}1 0^{M+2}P_{0}= 0 G= Y P_{1}0 1 0^{M+2}= Y P_{1}010 0^{M+1}G is of the first form P_{1}P_{0}= 01 G= Y 0 1 1 0^{M+2}G is of the second form

For P_{0}=0 case, since P doesn't contain the substring 11, neither
does YP_{1}.

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.

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 ≥ 2We 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 ≥ 2Before 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 > 2So, we have banned

- all numbers greater than 4 due to the above splitting technique.
- number 4 for convenience.
- number 1 since it doesn't contribute anything to the total power.

We already know that no more than two dragons can have 2 heads. Let's consider the cases.

2-headed | 3-headed | Total | Power | Power/3^332 |

0 | 333 | 999 | 3^333 | 3 |

1 | 332 | 998 | 2*3^332 | 2 |

2 | 332 | 1000 | 2^2*3^332 | 4 |

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:

N | 2-headed | 3-headed | Power |

3k | 0 | k | 3^k |

3k+1 | 2 | k-1 | 4*3^(k-1) |

3k+2 | 1 | k | 2*3^k |

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 x^{2} since 2^{4}-3^{3} is -11.

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

- Case 1: x
^{2}+ 2^{3}= z^{4} - Case 2: 2
^{2}+ y^{3}= z^{4}

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

- 2.A y ≡ 0 (mod 3)
- 2.B y ≡ 1 (mod 3)
- 2.C y ≡ 2 (mod 3)

If case 2.B is true, then we get the equation:

4 + 1^{2} ≡ z^{4} (mod 3)

1 + 1 ≡ z^{4} (mod 3)

2 ≡ z^{4} (mod 3)

Let's have a look at the powers of numbers in mod3.

z | z^{2} |
z^{3} |
z^{4} |

0 | 0 | 0 | 0 |

1 | 1 | 1 | 1 |

2 | 1 | 2 | 1 |

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

4+ 2However, this doesn't work either:^{3}≡ z^{4}(mod 3) 1 + 2 ≡ z^{4}(mod 3) 0 ≡ z^{4}(mod 3) 0 ≡ z (mod 3) z= 3. (since z is a prime)

4 + yThis doesn't have an integer solution.^{3}= 3^{4}4 + y^{3}= 81 y^{3}= 77

- 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