# 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.

# 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:

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.

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:

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.

# 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:

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.