Another easy exercise to coloring proofs

Today i will post another easy coloring proof:

Problem:
Can you completely cover a 10×10 chess board with 4×1 bricks.

Sollution:
We colour the board, so that we have a 5×5 chessboard in which each tile consists of 4 of the 10×10 board tiles.
Then every 4×1 Brick touches 2 black and 2 white tiles. (The 10×10 board tiles) but their are more tiles of one colour than the other.  This is a contradiction.

Constructing the Japanese problem figure

In this post we will construct the figure of the last post. I will leave the proof open. But i will post it if i get asked.

Problem:
Let a square abcd be given. A semicircle k in the square with the diameter ab is given. Construct a circle in the square, which touches k , cb and dc.

Solution:

First we construct the line through a and c.  We extend the side cb to a point e so that cb=be. Then we construct the tangent line to the semicircle k. Let the point on which the tangent line touches k be denoted as x. We construct a perpendicular line to the tangent line through x. The point where this line crosses the line ac ,we denote as n.
Then n is the center of the circle and nx is the radius of the circle we were searching for.

image

A Japanese problem

Today I will introduce a Japanese problem. In Japan problems like this are called a sangaku. Monks used to write sangaku’s on wood plates, which then would be sold to samurai for them to solve. In this post I will solve the problem and in the next one, I will construct the figure which will be presented.

The Problem:
Let abcd be a square. We construct a semicircle over ad with the radius of half the side length of the square. Let K be a circle which touches the semicircle and bc and cd. As the picture below shows:

image

Solution:
We construct a parallel line through the middle point of ad parallel to ab. Also we construct a parallel line parallel to ad through the middle point of K. Let the interception point be denoted as y. Last we construct the line from the middle point of ad and the center of K.
This forms a rightangeled triangle y and the center points of the two circles.

image

We denote the radius of K as r and the radius of the semicircle as a/2.
The sides of the triangle which we constructed are:
r+a/2 , a/2-r and a-r.
After the pythagorean theorem we have the following equlity.
(r+a/2)^2=(a/2-r)^2+(a-r)^2.
Solving the equality offers
r=(2-sqr (3))a.

Calculating the Incircle Radius

In this post we will calculate the incircle radius of a triangle given only the sides. For this we need heron’s formula which says, that when the sides of a triangle are a,b,c that then:
Let s=(a+b+c)/2.
Then the area is the square root of s*(s-a)*(s-b)*(d-c). This can easily be proven with the pythagorean theorem.

We connect the incircle center with the corners of the triangle:

image

The triangle is now devided into 3 triangles. The small triangles have the base sides of lengths a,b and c. The hight is always the incircle radius which we denote r. So the Area A of the big triangle is equal to a*r/2+b*r/2+c*r/2. This equals (a+b+c)*r/2. We have A=(a+b+c)*r/2. We devide by (a+b+c)/2 and get 2A/ (a+b+c)=r.
The formula for the incircle radius is two times the area devided by the circumference.

Colouring Proofs

Today i will introduce colouring proofs. For this i will give the classic example.

Problem:
Let a chessboard be given. The two black corners are cut off. Is it possible to completely cover the board with domino bricks.

Sollution:
No. A domino brick on the board always  covers one black and one white tile. Since there are more white tiles than black tiles, it is impossible to completely cover the board with dominoes.

One Line through two Points

This Problem was set up by Silvester in 1893. The solution that I will show you was found by L. M. Kelly in 1948. Paul Erdős said, that this is an example from the book. Paul Erdős often spoke about a book belonging to god which notes the best proofs of every theorem.

The Problem:

Let A be a finite amount of points in a plane, which don’t all lie on one line. Show that there exists one line, which goes through exactly two points.

The Solution (of L. M. Kelly) :

Lets assume, that there exists no such line. We pick a line L, that holds at least 3 points, so that there exists one point X which is not on the line, for which the distance between X and L is minimal. We denote the line, that goes through L and X and which is perpendicular to L with S. Since the line L holds at least 3 points, there exist at least 2 points R and Z on one side S.

Screen Shot 2014-12-22 at 2.20.16 PM

Now we assume, that R is the point further away form S. Then the distance between Z and the Line Through R and X is smaller, than the distance between X and L. This is a contradiction, which completes the proof.

Fermat’s little Theorem

Fermat’s little theorem: Let p be a prime. Then a^p-a is a multiple of p. In other words a^p is congruent to a mod p.

Proof: We will use Induction. For a=1 we have a^p-a=1^p-1=1-1=0. 0 is a multiple of p.

Now we assume, that the theorem works for a.

Last but not least, we have to show that a+1 works.  We have  (a+1)^p-(a+1)=(a+1)^p-a-1. Now we use the binomial theorem:

Screen Shot 2014-12-20 at 11.52.24 AM

We know that a^p-a is a multiple of p. Every summand of the sum is a multiple of p as well. It follows, that the theorem works for a+1 as well.

This proves the theorem.

Wilsons Theorem

Wilsons Theorem says, that p is prime if and only if (p-1)!+1 is a multiple of p.

To prove this, we must show, that if (p-1)!+1 is a multiple of p, that then p is prime and that if p is prime, that then (p-1)!+1 is a multiple of p.

First we will show, that p must be prime so that  (p-1)!+1 is a multiple of p. To do this we first assume, that p is not prime and that (p-1)!+1 is a multible of p. Then p can be written as x*y with x and y < p. It follows, that (p-1)! is a multible of x and y. Now we can say, that (p-1)!+1 is not a multible of x or y. It follows, that (p-1)!+1 is not a multiple of p. We also need to consider the case that x=y. It does not work for x=y=2. For all cases wit x bigger than 2, 2x will also be a factor in (p-1)!. It follows, that (p-1)!+1 is not a multiple of p. This is a contradiction which tells us, that p has to be prime.

Now we have to show the other part of the theorem. It says, that (p-1)!+1 is a multible of p for every prime p . Considering that p is prime, for every remainder modulo p there exists a unique inverse remainder, so that the product of the two remainders is 1 modulo p. The only two remainders that have them selves as a inverse are 1 and -1. The factors of (p-1)! are all possible remainders of p. It follows, that for every factor other than 1 and p-1 there exists a second factor so that when multiplied the product is congruent to 1 modulo p. The two numbers that are left multiplied together equal -1 modulo p. It follows, that (p-1)! is congruent to -1 modulo p and therefore (p-1)!+1 a multiple of p.

This proves Wilsons theorem.

Paul Erdős’ favorite Problem

It is said, that the following problem was Paul Erdős’ favorite problem.
The Problem:
Let n be any positiv whole number. Let n+1 numbers randomly be taken from the numbers 1 to 2n. Show that there will always exist two numbers x and y which are in the n+1 chosen numbers, so that x*z=y for some positive whole number z.

Solution:
It is possible to write every number in the form q*2^h for an uneven number q. If two numbers have the same q, one can always be devided by the other. It follows, that no two of the n+1 chosen numbers are allowed to have the same q. We know that there only exist n uneven numbers in the numbers from 1 to 2n. Since we need to choose n+1 numbers from this set, two numbers must have the same q when written in the form q*2^h.
This is a contradiction.
It follows that there will always be 2 numbers x and y with x*z=y for some positive whole z.

Napoleon’s Theorem

First I want to thank an anonymous Person who Formulated this Post for me.

Napoleon’s Theorem:

Let ABC be a triangle. Let equilateral triangles be constructed outward at each side of the triangle ABC. Then the midpoints of these equilateral triangles are the vertices of another equilateral triangle.

Screen Shot 2014-06-19 at 10.11.22 AM

Proof:

We use vector calculus. Let A, B, C denote the vectors pointing to the vertices.  By translating the tirangle so that the barycenter of it becomes the origin, we may assume that

(1)       A+B+C=0

Let R be a the linear map which turns each vector by 60 degrees to the right. Note that R^3 = -1and for every vector X we have the identity

(2)     R^2 X  = RX – X

The tip of the equilateral triangle above the side from A to B is

B+R(A-B)

The center of this equilateral triangle is then

(A+B+(B+R(A-B)))/3

Using (1), we may write this as

(3)    ((B-C)+ R(A-B))/3

By symmetry the centers of the other equilateral triangles are

(4)   ((C-A)+R(B-C))/3

(5)   ((A-B)+R(C-A))/3

We need to prove that these three points are permuted when we rotate by 120 degrees aound the origin, that is R^2. For simplicity we may multiply the three vectors by 3. Applying R^2 to 3 times expression (3) gives

R^2(B-C)+R^3(A-B)

Applying (2) and the fact R^3=-1 turns this into

R(B-C)-(B-C)-(A-B)=(C-A)+R(B-C)

This evidently is three times (4). By symmetry, the three points (3),(4),(5) are permuted when rotated by R^2, which proves that they form an equilateral triangle.