Mathematical Circles
Art Credit: BLEACH Manga Edit by Soleim (Link)
Embedded Files
**Note: The contents of this page - except the formatting - are from when I first made this website before I started college. I have decided not to update the pictures with LaTeX documents in order to preserve my work and keep it authentic.**
What is it?
What is it?
Mathematical Circles (Russian Experience) by Dmitri Fomin, Sergey Genkin, Ilia Itenberg cultivates a mathematical spirit. The book was written for all age groups, regardless of their mathematical ability and/or interest.
In this section, I delve into certain problems in each chapter of the book that made me approach problems differently or taught me a valuable concept
Chapter 1 - Parity
Chapter 1 - Parity
Problem 2) On a chessboard, a knight starts from square a1, and returns there after making several moves. Show that the knight makes an even number of moves.
Problem 2) On a chessboard, a knight starts from square a1, and returns there after making several moves. Show that the knight makes an even number of moves.
The a1 square is black. Note, a knight moves in L-shapes that alternate in color. Thus, the knight's position alternates between black and white.
If the knight moves back to its original square (a black square), then it must make an even number of moves because odd moves correspond to white squares.
Problem 21) A grasshopper jumps along a line. His first jump takes him 1 cm, his second 2 cm, and so on. Each jump can take him to the right or to the left. Show that after 1985 jumps the grasshopper cannot return to the point at which he started.
Problem 21) A grasshopper jumps along a line. His first jump takes him 1 cm, his second 2 cm, and so on. Each jump can take him to the right or to the left. Show that after 1985 jumps the grasshopper cannot return to the point at which he started.
This problem is of the form 1 +/- 2 +/- 3 +/- ... +/- 1985.
Let's first start with 1 + 2 + 3 + ... + 1985. The sum of this is 1985(1986)/2, which is a odd number (due to 1986 = 2 mod 4).
When we convert this sum to the original expression, we subtract out 2*n (e.g. 15 - 2(15) = -15). Thus, we always subtract out even numbers from our odd expression. This would make an overall odd expression, regardless of how many numbers you subtract.
Since our origin position is 0 (even), we will never reach it with 1985 jumps.
Problem 24) A 17-digit number is chosen, and its digits are reversed, forming a new number. These two numbers are added together. Show that their sum contains at least one even digit.
Problem 24) A 17-digit number is chosen, and its digits are reversed, forming a new number. These two numbers are added together. Show that their sum contains at least one even digit.
Let's first assume all of its digits are odd (proof by contradiction). When two numbers are added together, the only way to get an odd number is that one is odd and one is even.
Note that the 9th digit adds onto itself, making it even. However, if a 1 is carried on to the 9th digits' sum, then the same will happen to the 11th column from the 10th one (because columns 10 and 8 are identical).
If we keep getting a carry from the first column to make it odd, then all columns except the first one will have to be even (because it cannot get a carry). This means that there must be an even digit.
All gears must have the same parity of teeth (odd or even) for a gear system to work. Credit: Google Images.
Chapter 2 - Combinatorics-I
Chapter 2 - Combinatorics-I
Problem 24) A "necklace" is a circular string with several beads on it. It is allowed to rotate a necklace but not to turn it over. How many different necklaces can be made using 13 different beads?
Problem 24) A "necklace" is a circular string with several beads on it. It is allowed to rotate a necklace but not to turn it over. How many different necklaces can be made using 13 different beads?
Without the rotation aspect, there are clearly 13! different necklaces (due to the formula for the permutations of an object).
However, with rotation, there is no start or end point. With rotation, there are 12 more start points so we need get rid of 13 possible types of necklaces per case.
Thus, our answer is 13!/13 = 12!
Problem 26) How many six-digit numbers have at least one even digit?
Problem 26) How many six-digit numbers have at least one even digit?
Lets subtract the numbers that have only odd digits from all of the six-digit numbers.
The total number of six-digit numbers is 900000 (100,000 to 999,999).
For the odd digit numbers, each digit has 5 options. Thus, the total number of all odd six-digit numbers is 5^6.
Thus, the total number of six-digit numbers that have at least one digit is 900000 - 15625 = 884375.
Problem 41) There are three rooms in a dormitory: one single, one double, and one for four students. How many ways are there to house seven students in these rooms?
Problem 41) There are three rooms in a dormitory: one single, one double, and one for four students. How many ways are there to house seven students in these rooms?
For this problem, we can use the choose, function (the general formula is below).
For the single room, we have 7 choose 1. For the double, we have 6 choose 2 (because we have one less student). For the final four, we have 4 choose 4.
This comes down to 7*15*1 = 105.
An alternate way is 7!/(1!*2!*4!) = 7*3*5 = 105.
This is a necklace similar to problem 24 from above. Credit: Google Images.
Chapter 3 - Divisibility and Reminders
Chapter 3 - Divisibility and Reminders
Problem 6: How many zeroes are at the end of the decimal representation of the number 100! ?
Problem 6: How many zeroes are at the end of the decimal representation of the number 100! ?
First, 100! = 100*99*98*...*1. Second, trailing zeroes are just how many powers of 10 exist in the number (i.e. what is the largest value of n such that 100! can be written as m*10^n, where m is an integer).
We need to find the least common multiple of the powers of 2 and 5 in this huge number.
Since there are so many more 2 and its multiples in 100!, lets look at 5 to make our life easier. 5's multiple exists 20 times in 100! (100/5) so we have 5^20. However, we have to add 4 to the 20 because 25, 50, 75, and 100 are multiples of 5^2. Thus, 5^24 divides 100!.
Since there are clearly more than 24 even numbers from 1 to 100, 2^24 also exists in 100!. Thus, largest n is 24 (i.e. m*10^24 = 100!).
Thus, 100! has 24 trailing zeroes.
Problem 20: Prove that n^3 - n is divisible by 24 for any odd n.
Problem 20: Prove that n^3 - n is divisible by 24 for any odd n.
To prove that n^3 - n is divisible by 24, all we have to do is prove the expression is divisible by 3 and 8 (because they are coprime).
First, n^3 - n = n(n^2 - 1) = n(n+1)(n-1)
To prove its divisibility by 3:
Note (n-1)(n)(n+1) is the product of three consecutive integers. Thus, by the pigeon hole principle, one of these 3 must be a multiple of 3, meaning the product is too.
To prove its divisibility by 8:
Since n is odd, n-1 and n+1 are even (that is, each are divisible by 2). This means they are divisible by 4 together. However, we need to prove that it is also divisible by 8.
By the pigeon hole principle, since n+1 and n-1 have a difference of 2, one must have a 0 when divided by 4 and the other a remainder of 2. Thus, since one of the two even numbers is purely divisible by 2 and the other by 4, it is divisible by 8 altogether.
Thus, n^3 - n is divisible by 24 for any odd n.
Problem 38: Given natural numbers x, y, and z such that x^2 + y^2 = z^2, prove that x*y is divisible by 12.
Problem 38: Given natural numbers x, y, and z such that x^2 + y^2 = z^2, prove that x*y is divisible by 12.
We have to prove that x*y is divisible by 3 and 4.
Any perfect square when divided by 3 or 4 only yield remainders of 0 or 1.
Also note, that when a is 0 or 1 mod 3 or 4, a^2 will be the same.
For 3:
The only possible cases are:
x = y = 0 mod 3 (so z = 0 mod 3)
WLOG, x = 0 mod 3 and y = 1 mod 3 (so z = 1 mod 3)
Note, in both cases, x*y mod 3 will be 0, meaning x*y is divisible by 3.
For 4:
We have the same cases as before (since if both x = y = 1 mod 3, then z = 2 mod 4, which is impossible).
Thus, x*y = 0 mod 4 so the product is divisible by 4.
Therefore, x*y is divisible by 12 if x^2 + y^2 = z^2.
Problem 53: Prove that there are infinitely many prime numbers.
Problem 53: Prove that there are infinitely many prime numbers.
Let's assume there does is a finite amount of prime numbers (so we are going to use a proof by contradiction). Let's say the prime numbers are p1, p2,..., pn.
Now note that p1*p2*p3*p4*...*pn + 1 is not divisible by any of these prime numbers. Thus, its prime factorization is itself and 1. Therefore, this new number is also prime (by definition of a prime number). This contradicts our original claim, meaning there are infinitely many prime numbers.
Problem 54: Prove that the fraction (12n + 1)/(30n + 2) cannot be reduced for any natural number n.
Problem 54: Prove that the fraction (12n + 1)/(30n + 2) cannot be reduced for any natural number n.
By Euclid's algorithm, the gcd(a, b) = gcd(a-b, b).
In this case, we can say:
gcd(12n+1, 30n+2) = gcd(12n+1, 18n+1)
= gcd(12n+1, 6n)
= gcd(6n+1, 6n)
= gcd(1, 6n).
Thus, the numerator and denominator are coprime (they share no factors other than 1) so the fraction cannot be reduced for any natural number n.
The man pictured above is Euclid of Alexandria. He is known as the father of geometry for coming up with the axioms that make up non-relativistic geometry. In addition, he came up with Euclid's method, which is how we solved Problem 54 above. Credit: Google Images.
Chapter 4 - Pigeon Hole Principle
Chapter 4 - Pigeon Hole Principle
Problem 14: Show that an equilateral triangle cannot be covered completely by two smaller equilateral triangles.
Problem 14: Show that an equilateral triangle cannot be covered completely by two smaller equilateral triangles.
This problem seems very obvious, but for me, it was difficult to put into words.
However, I realized that I overcomplicated this and simply pointing out that a smaller equilateral triangle can only occupy one vertex (so two occupy two vertices).
And so, two equilateral triangles cannot completely cover a bigger equilateral triangle.
Problem 18: On a certain planet in the solar system Tau Cetus, more than half of the surface of the planet is dry land. Show that the Tau Cetans can dig a tunnel straight through the center of their planet, beginning and ending on dry land (assume that their technology is sufficiently developed).
Problem 18: On a certain planet in the solar system Tau Cetus, more than half of the surface of the planet is dry land. Show that the Tau Cetans can dig a tunnel straight through the center of their planet, beginning and ending on dry land (assume that their technology is sufficiently developed).
Let's first color the non-dry land red and the dry land blue. If we assume the planet is spherical and look at it in 2-D, we see that it is a circle. This now comes down to whether a diameter exists on this circle such that its endpoints are blue.
By contradiction, let us say no such diameter exists. This means diameters with a red and blue endpoint and/or red endpoints exist.
If it's only the former case, then the red land and blue land will be equal. But this is not the case. Thus, then 2nd case has to be true for all such possibilities. However, if we pool the red land and the blue land separately on the circle, we actually see that no such diameter exists in this case, since the red land is in the minority.
Thus, our original claim is true.
Problem 19: Prove that there exists two powers of two which differ by a multiple of 1987.
Problem 19: Prove that there exists two powers of two which differ by a multiple of 1987.
There are an infinite amount of powers of two. There are 1987 different remainders when an integer is divided by 1987. Thus, the modulus of an integer with base 1987 has 1987 possibilities.
Since we have infinite pigeons and 1987 pigeon holes, we have at least two powers of two with the same moduli in base 1987. Let these be 2^m and 2^n.
Thus, when we subtract one from the other, we see that this new expression has a remainder of 0 when divided by 1987.
The pigeon hole principle used in number theory for remainders make such bizarre claims extremely easy to solve.
By the Pigeon Hole Principle, when there are 10 pigeons and 9 pigeon holes, one hole must contain two pigeons. This is seen in the top left hole. Credit: Google Images.
Chapter 5 - Graph Theory
Chapter 5 - Graph Theory
Problem 15: In the country of Seven, there are 15 towns, each of which is connected to at least 7 others. Prove that one can travel from any town to any other town, possibly passing through some towns in between.
Problem 15: In the country of Seven, there are 15 towns, each of which is connected to at least 7 others. Prove that one can travel from any town to any other town, possibly passing through some towns in between.
Let's do a proof by contradiction. Let's assume there are two towns that cannot reach other at all (aka two connected components).
Both towns connect to seven towns, but these seven are distinct for each because if they weren't, they would be connected.
That means, we would need a minimum of 7+7+1+1 = 16 towns, which contradicts our given information.
Problem 17: In Never-Never-Land, there is only one means of transportation: magic carpet. Twenty-one carpet lines serve the capital. A single line flies to Farville, and every other country is served with exactly 20 carpet lines. Show that it is possible to travel by magic carpet from the capital to Farville (perhaps by transferring from one carpet line to another).
Problem 17: In Never-Never-Land, there is only one means of transportation: magic carpet. Twenty-one carpet lines serve the capital. A single line flies to Farville, and every other country is served with exactly 20 carpet lines. Show that it is possible to travel by magic carpet from the capital to Farville (perhaps by transferring from one carpet line to another).
Let's again use proof by contradiction. Let us say that Farville is not part of the connected component in this land.
Note that there is exactly one area with 21 carpet lines (the capital). The countries all have 20 carpet lines.
Since we know that a graph must have even number of odd vertices, we know that the above information cannot be true. Thus, the capital and Farville are connected.
Problem 22: a) A piece of wire is 120 cm long. Can one use it to form the edges of a cube, each of whose edges is 10 cm?
Problem 22: a) A piece of wire is 120 cm long. Can one use it to form the edges of a cube, each of whose edges is 10 cm?
When I first came across this problem, my thought process was that a cube had 12 edges and 12*10 does indeed equal 120, so this could be possible. However, after further inspection, I realized my mistake.
The wire cannot be cut. It folds into edges of the cube. This means that to make a cube with side length 10 cm, a cube has to be an Eularian graph, which means it can only have 2 odd degreed vertices.
Since each vertex has 3 edges connected to it, there are 6 odd degreed vertices, which means we cannot form such a cube with our 120 cm of wire.
The man pictured above is Leonhard Euler, one of the best mathematicians in history. Euler significantly involved himself in most fields of mathematics. His contributions included Euler's identity, the solution to the Basel problem, and the Euler product-sum formula. Credit: Google Images.
Page updated
Google Sites
Report abuse