MathCircle sessions (2000)

Session N 13 (01/02/2000)

Session questions

1. There is a pawn standing in an upper left corner of a 5x8 board. It is permitted to move only one square at a time either to the right or in downward direction. How many ways are there for the pawn to get to the lower right corner of the board?

2. There are 10 coins lying in a row - all of them with their "head" side up. It is permitted to perform the following operation: take any four successive(!) coins and turn them over. Is it possible that after several such operations all the coins will be lying "tails up"?

3. a) Can a chess knight "traverse" a 3x3 board? By "traversing" we mean a sequence of knight's moves such that every square of the board is visited exactly once.
b) What if the board has dimensions 4x4?

Homework questions

1. Find all two-digit numbers AB such that AB = 2 BA - 1.

2. There are five coins and it is known that exactly two of them are counterfeit (they weigh the same but less than genuine coins; all genuine coins weigh the same). Using regular balance find both counterfeit coins with no more than three weighings.

3. A steamship takes 5 days to go from Nizhniy Novgorod (NN) to Astrakhan (A) (it is assumed that Volga's current's velocity is constant) and 7 days from A to NN. How long will it take to swim on a raft from NN to A?

4. Is it possible for a chess knight to "traverse" an 8x8 chessboard starting at square a1 and ending at h8?

Session N 14 (01/09/2000)

Session questions

1. Is it possible for a chess knight to traverse a 3 x 7 board?

2. Prove that GCD(a, b) = GCD(a, a-b) = GCD(b, a-b) = CGD(a, a+b) = GCD(b, a+b).

Homework questions

1. Given a natural number n, prove that n(n+1)(n+2)(n+3) is not a perfect square.

2. There are 5 points inside a 2 x 2 square. Prove that distance between some two of them is not greater than square root of 2.

3. Nine different natural numbers are divided into three groups with three numbers in each of them. Prove that the product of the numbers within one of the groups is greater than or equal to 72.

4. Ten integers whose sum equals 1 are arranged around a circle. We will call any subset of consecutive (that is forming a contiguous sequence) numbers a "chain". Find number of chains whose members' sum is positive.

Session N 15 (01/16/2000)

Session questions

1. In HW Question 4 (previous session) how many "chains" are there overall?

2. Main Theorem of Arithmetics:

• Euclid's algorithm for calculating GCD.
• Lemma: if ab is divisible by c, and GCD(a,c)=1 then b is divisible by c.
• Proof of MTA.

Homework questions

1. Natural number written by digits a, b, c, d, e, f (in the order listed) is divisible by 37. Prove that digits b, c, d, e, f, a form the number which is also divisible by 37.

2. Could there be a finite set of numbers whose sum is 1 but the sum of their squares is less than 0.001?

3. There are 28 domino tiles in a regular game set. Twenty-six of them are arranged into a chain according to the rules of the game so that no one of the remaining tiles can be added to the chain. Prove that both remaining tiles are doubles.

4. Prove that 4 x N board cannot be traversed in a closed cycle by a chess knight.

Session N 16 (01/23/2000)

Session questions

1. Find a non-closed traversal of a 4 x 8 board by a chess knight.

2. Find a formula for the sum 1 + 2 + ... + n.

3. Find a formula for the sum 1 + 2 + 4 + .. + 2n.

Homework questions

1. Find a formula for the sum 1/1x2 + 1/2x3 + ... + 1/(n-1)n.

2. It is known that x + 1/x is an integer. Prove that x2 + 1/x2 and x3 + 1/x3 are integers as well.

3. Prove that at least one of the last two digits of a perfect square is even.

4. There are N cities and N-1 roads in a country. Given that every city can be reached from any other one using the roads prove that there exists a city with exactly one road going out of it.

Session N 17 (01/30/2000)

Session questions

1. Prove that in a tree E = V-1 (tree is a connected graph without cycles; E = number of edges, V = number of vertices).

2. Prove that in any connected graph E >= V-1.

3. Prove the formula from Session 16 HW Question 1 using mathematical induction.

4. There are N straight lines in the plane such that no two of them are parallel and no three intersect at one point. Find the formula for the number of parts they divide the plane into, and prove it (using mathematical induction).

Homework questions

1. One box is cut out from a 16 x 16 board. Prove that the rest of the board can be cut into "corner" triminos.

2. One hundred coins are arranged in a row such that the sequence of their upper sides is HTHTHT.. HT (that is, head-tail-head-tail... etc.). In one operation you are allowed to turn over any number of consecutively lying coins. What is the minimum possible number of such operations necessary to make all the coins lie heads up?

3. There are five points in the plane such that no three of them lie on the same straight line. Prove that some four of these points form a convex quadrangle.

4. Every one of the great king Arthur's progeny had either two or zero children. It is also known that Arthur's blood line is currently extinct. Given that the number of all Arthur's descendants who'd had children is 1000 find the number of all Arthur's descendants.

Session N 18 (02/06/2000)

Session questions

1. There are 100 candies in a box. Pete can eat either one or two candies in one gulp which takes him at least one second. What is the fastest he can eat the entire box?

2. Given n straight lines from Session 17 SQ 4 prove that one can color the parts of the plane into black and white so that any two parts sharing common boundary are colored differently.

Homework questions

1. Prove that natural number written by 729 ones is divisible by 729 = 36.

2. There are 2000 points on the plane such that no three of them belong to a straight line. Prove that there exists a straight line such that exactly 1000 points of the given set lie on either side of it.

3. Construct planar graphs with constant vertex degree equal to k = 1, 2, 3, 4, 5.

4. An 8 x 8 board is covered by dominoes without overlapping. Prove that some two dominoes form a 2 x 2 square.

Session N 19 (02/13/2000)

Session questions

1. Prove Session 18 HW 1 in general form: that is, for any 3n.

2. Find a natural number whose sum of digits is divisble by 27 but the number itself is not.

Homework questions

1. Prove (using induction) that if x + 1/x is an integer then for any natural n xn + 1/xn is also an integer.

2. How many 5-digit numbers have digit 5 in their decimal representation?

3. Find all prime numbers p such that p4-6 is also a prime.

4. Twenty-five boys and twenty-five girls are sitting at a round table. Prove that for somebody both of his/her neighbors are boys.

Session N 20 (02/27/2000)

Session questions

1. In Session 19 HW 4: what if there are 24 boys and 24 girls - does there exist a seating such that no one has boys as both neighbors? If yes, list all such seatings.

2. In the language of a newly discovered Mumbo-Jumbo tribe there are only two letters A and B and one can make the following substitutions in any word and the meaning of the word will not change:
(I) A <--> ABA ; (II) B <--> BBA ; (III) ABB <--> BAB .
It is known that two words have the same meaning if and only if one can be obtained from another by some sequence of transformations (I), (II) and (III).

• Are words A and AB synonims?
• Are words A and B synonims?

3. There are one hundred numbers, namely, one zero and 99 1's, written on a blackboard. One can erase any two equal numbers and write down a zero instead, or erase two different numbers and write down 1 instead. After 99 such operations only one number is left on the board. Which is it: 0 or 1?

4. There are one hundred 1's written on a blackboard. Once can erase any two numbers a and b and write down number a+b+1 instead. What number will be left on the blackboard after 99 such operations?

Homework questions

1. Number 111...11 (n ones) is a prime number. Prove that n is also prime.

2. There are twenty numbers 1 written on a blackboard. One can erase any two numbers a and b and write down number ab+a+b instead. What number will be left on the blackboard after 19 such operations?

3. Prove that a straight line cannot intersect all sides of a 101-gon on a plane without passing through any of its vertices.

4. There are 125 chips placed in the boxes of a 15 x 15 board. Given that the chips' arrangement is symmetric with respect to both of the diagonals of the board prove that the central box must be occupied by one of the chips.

Session N 21 (03/05/2000)

Session questions

1. Show that for any even n > 2 there is a n-gon such that some straight line intersects all of its sides without passing through any of its vertices.

2. (Euler Formula) Prove that for any planar connected graph V-E+F=1, where V is the number of the graph's vertices, E is the number of the graph's edges, and F is the number of the graph's faces not counting the infinite face.

3. Prove that for any planar connected graph E <= 3V-6. Use Euler formula and inequality 3(F+1) <= 2E.

Homework questions

1. Prove that for any planar connected graph whose faces must have at least 4 edges each the following inequality holds true: E <= 2V - 4.

2. There are 555 weights weighing 1g, 2g, 3g, ..., 555g respectively. Divide them into 3 piles of the same weight.

3. Boxes of a 10 x 10 board are colored black and white. It is allowed to take any three boxes forming 1 x 3 or 3 x 1 trimino and repaint all three of them into the color which was prevailing in that trio. Prove that using such operations you can repaint the entire board in one color.

4. How many ways are there to form words TEMA, MAMA and MATEMATUK using letters of the word MATEMATUKA?

Session N 22 (03/12/2000)

Session questions

1. Using the inequality from Session 21 HW Question 1 prove that the graph from "three houses and three wells" problem is not planar.

Homework questions

1. A and B are two natural numbers. How many numbers in the sequence A, 2A, 3A, ..., BA are divisible by B?

2. There is a sheet of graphed paper with the box side 1 cm long. Some three vertices of the grid form a triangle with area S. Prove that 2S is an integer.

Session N 23 (03/19/2000)

Session questions

1. Using Euler formula etc. find all regular polytopes.

2. What is the area of a regular triangle with side length a?

Homework questions

1. How many different natural divisors does the number 210311512 have?

2. Numbers 1 thru 8 are somehow positioned on the vertices of a cube. Prove that there are two neighboring numbers (that is, some edge connects their vertices) which differ by at least 4.

3. For any natural number n prove that n6 can have only reminders 0 or 1 modulo 7.

4. Prove that one cannot place a regular triangle on a graphed plane so that all three of its vertices coincide with the lattice's nodes.

Session N 24 (03/26/2000)

Session questions

1. Numbers p1, p2, ..., pk are different prime numbers, and numbers a1, a2, ..., ak are non-negative integers. How many natural divisors does the number p1a1p2a2...pkak have?

2. Prove that there are inifintely many prime numbers. Hint: if p1, p2, ..., pn constitute the entire set of prime numbers consider the number p1p2...pn+1.

3. Prove the Pick's Formula (Pick is the name of a mathematician not an English word): for any polygon with its vertices on the nodes of the unit lattice the following is true: its area S is equal to p+q/2-1, where p is the number of lattice nodes entirely inside the polygon, and q is the number of nodes on the contour of the polygon.
a) Prove the Pick's Formula for any rectangle with its sides lying on the grid lines.
b) Prove that if two polygons P and Q form another polygon R when taken together (they must have at least one common side) then if the Pick's formula holds true for some two of P, Q and R then it is true for the remaining third polygon.

Homework questions

1. Prove the Pick's formula for any triangle with its vertices on the lattice nodes. Hint: consider the rectangle which our triangle is "inscribed" into.

2. What is the maximum number of chess knights one can place on the chessboard in such a way that no one of them threatens another?

3. A teacher gave homework containing 20 math questions. For every right solution a student receives 8 merit points, for every wrong solution he/she receives (-5) points (non-submitted solution is worth 0 points, of course). After evaluation of Pete's homework he received 13 points. How many solutions did he submit?

4. Prove the following inequality:

```   (1 x 3 x 5 x ... x 99)/(2 x 4 x 6 x ... x 100) < 0.1
```

Session N 25 (04/02/2000)

Session questions

1. Prove that x/(x+1) < (x+1)/(x+2) for any x > 0.

2. Prove Pick's formula for any rectangular triangle with its legs on lattice lines. Derive the proof of Session 24 HW Question 1 from that and finish the proof of Pick's theorem.

3. Using Fermat's "Little" Theorem find the remainders of 21999 modulo 7 and modulo 13.

Homework questions

1. Find a cyclical traversal of a chessboard by chess knight (that will finish our proof of Session 24 HW Question 2).

2. Find minimum natural n > 1 such that n increased by 1 is divisible by 2, n increased by 2 is divisible by 3, ..., n increased by 9 is divisible by 10.

3. Place 7 stars into some 7 boxes of a 4 x 4 table so that the following is true: if one cuts out any two rows and any two columns of the table then at least one star is left intact.

4. Prove (Hint: by induction) the following equality:
12 + 22 + ... + n2 = n(n+1)(2n+1)/6

Session N 26 (04/09/2000)

Session questions

1. Prove that for any placement of six stars into some six boxes of a 4 x 4 board one can cut out two rows and two columns so that no stars will be left on the board.

2. Prove Fermat's Little Theorem. Hint: prove that for any natural n not divisible by prime p set of remainders modulo p of numbers n, 2n, ..., (p-1)n is the same as set {1, 2, ..., p-1}.

3. a) Find relationships between sets of numbers N, Z, Q, R
b) Why don't sets 2Z and N coincide?

Homework questions

1. There are six metallic rods, each one exactly 1 m long. Can one cut them into ten rods of 27 cm in length, twelve rods of 15 cm in length and twenty-five rods of 6 cm in length?

2. An electric outlet in Elbonia has seven round holes positioned in the vertices of a regular septagon. An electric plug there has seven round throngs placed similarly. Holes of the outlet are numbered 1 thru 7 clockwise. Is it possible to number the throngs in such a way that however one puts the plug into the outlet at least one of the throngs will be inserted into the hole with the same number?

3. There are N people in the room, and each one of them is either a knight who always tells the truth or a knave who always lies. Every one of them says: "All the other people in this room are knaves". How many knights are there in the room?

4. Prove the following inequality:
(1.01)1000 > 1000

Session N 27 (04/16/2000)

Session questions

1. In Session 26 HW Question 2: what if we change number seven to number 4? To any other even number n = 2k? Hint: the answer is negative for any even number of throngs.

2. List all types of convex sets on a straight line.

3. Give as many examples as possible of convex sets on a plane.

Homework questions

1. Prove that intersection of two convex sets on a plane is also a convex set.

2. A circle is divided into six sectors; six chips are placed into the sectors, one chip per sector. One can perform the following operation: move exactly two chips to the neighboring sectors. Is it possible to gather all the chips in one sector after several such operations?

3. There are twelve blank spaces on a sheet of paper arranged in a row and numbered from 1 thru 12. Tom and Jerry are playing a game making their moves in turn. Tom's move consists of writing "+" or "-" into any odd-numbered blank space and Jerry does the same with even-numbered spaces. After all the spaces are filled, they count the number of times "+" stands next to "-" and Jerry punches Tom in the nose as many times. Tom makes his move first - what is his strategy to minimize the punishment presuming Jerry plays perfect game?

4. On the Island of Knights and Knaves a traveler comes to a fork in the road. He knows that one of the roads goes to the Knaves' City and another - to the Knights' City. There is a native who agrees to answer exactly one question (however, the traveler doesn't know who the native is: knight or knave). What question must he ask in order to determine which road leads where?

Session N 28 (04/23/2000)

Session questions

1. On the Island Of Knights and Knaves you can ask one question of a native to determine whether she has a pet alligator at home. What question do you ask?

2. On the Island Of Knights and Knaves you know that words "flip" and "flop" mean "yes" and "no" in native language but you don't know which one means what. What one question do you ask to determine the meaning of the word "flip"?

3. Given three convex sets on a straight line such that every two of them have non-empty intersection prove that all three sets have non-empty intersection.

4. Based on the previous result prove by induction 1-dimensional case of Helly's Theorem: if several convex sets on a straight line are such that every two of them have non-empty intersection then all of them have non-empty intersection.

Homework questions

1. Given four convex sets on a plane such that every three of them have non-empty intersection prove that all four sets have non-empty intersection.

2. One thousand digits are written in a row in such way that a 2-digit number formed by any two successive digits is divisible by either 17 or by 23. The last digit is 1. What is the first digit in the sequence?

3. Eight numbers each equal to +1 or -1 are arranged around a circle. Every minute the following happens: between any two numbers we write their product and then we erase all the old numbers. Prove that eventually all numbers will be equal to +1.

4. Sequence of Fibonacci numbers is defined by the following rules. F0 = 0, F1 = 0 and for any n > 1 we have
Fn = Fn-1 + Fn-2.
Find all Fibonacci numbers divisible by 4.

Session N 29 (04/30/2000)

Session questions

1. What can you say about a person on the Island of Knights and Knaves if she says to you: "I am a knave"?

2. What one question do you ask a native of the Island of Knights and Knaves so that the answer will always be "flip"?(See Session 28 Question S2).

3. A and B are both natives of the Island of Knights and Knaves. They are both on one room (nobody else is there) and A says: "At least one of us is a knave". Wjat can you say about them?

4. Three mathematicians are riding in the same car of a train when the train enters the tunnel. While in the tunnel the soot from its walls flies inside the car and dirties their faces. They start laughing at each other but then one of them realizes that his face must be dirty as well. What must be the chain of his reasonings?

5. Three players - A, B and C - are shown five caps: three red and two white. Then they are blindfolded and seated on three chairs arranged in a row so that A will see both B and C, B will see only C, and C will see no one. They are told that three of the caps just shown would be placed on their heads, after which three red caps are placed so (two remaining white caps are hidden). Then the blindfolds are taken off, and the players are asked if they can determine the color of their own cap. A answers no, then B answers no, and finally C says yes. What is his reasoning?

Homework questions

1. In Session 28 Question HW3: determine all numbers N such that if any N numbers +1 and -1 are written around a circle and then are subjected to the described operations then eventually all the numbers will be equal to +1.

2. There are N containers which are numbered 1 thru N and arranged in some arbitrary order in 2 stacks. A forklift can perform the following operation: take several containers from the top of one stack and then place them on top of the other stack. Prove that a forklift operator can put all the containers in one stack so they will be numbered in ascending order using no more than 2N-1 such operations.

3. A Christmas shop sells Humpties and Dumpties. 175 Humpties are worth more than 125 Dumpties but less than 126 Dumpties. Prove that three Humpties and one Dumpty cost more than 1 dollar.

4. Given six non-zero numbers a, b, c, d, e, f prove that among products ab, cd, ef, -ad, -be, -cf there are numbers of different sign (that is, at least one negative and at least one positive).

Session N 30 (05/07/2000)

Session questions

1. Prove that in a triangle the side that lies opposite a greater angle is longer (in other words, if angle ABC is greater than angle BAC, then side AC is longer than side BC).

2. Prove that in isosceles triangle the angles that lie opposite the equal sides are equal as well.

3. What is the probability of a coin falling head up after ten tosses resulted in "tails up"?

4. After 5 coin tosses what is the probability that number of heads will be exactly 0? 1? 2? 3? 4? 5?

Homework questions

1. In triangle ABC median AM is longer than half of side BC. Prove that angle BAC is acute.

2. A coin was tossed ten times. What is the probability that the number of heads will be strictly greater than the number of tails?

3. Prove that for any integer n number n3+5n is divisible by 6.

4. There are several chords drawn in a circle of unit raduis. Given that any radius of the circle intersects no more than 10 chords prove that the sum of the lengths of the chords is less than 70.

Session N 31 (05/14/2000)

Session questions

1. In Session 30 Question HW 1: prove that AM is equal to BC/2 if and only if angle A is right.

2. Prove that "pi" (also known as ratio of curcumference to its diameter or simply as 3.1415926...) is greater than 3 and less than 3.5. Hint: find the perimeters of regular hexagons inscribed in and circumscribed about the unit circle.

3. Prove the following triangle congruence theorems:
a) if all three sides of triangle ABC are equal to the correspondent sides of triangle DEF then ABC and DEF are congruent.
b) if two sides of triangle ABC and angle between them are equal to the correspondent sides and angle of triangle DEF then ABC and DEF are congruent.
c) if one side of triangle ABC and two angles adjacent to it are equal to the correspondent side and angles of triangle DEF then ABC and DEF are congruent.

Homework questions

1. Three circles are centered in three points which lie on the same straight line. It is known that the circles do not intersect. Given the fourth circle touching all three of them prove that its radius is greater than one of the three radii of the original circles.

2. There are 64 stones of different weight. Given the conventional balance which allows you only to determine which one of any two stones is heavier find the two heaviest stones using 68 weighings.

3. Natural numbers x and y satisfy the equality 43x = 34y. Prove that x+y is a composite number.

4. A man is standing on the edge of Grand Canyon - see picture below. He tosses a coin ten times and each time if it comes up head he steps 1 meter to the left, otherwise he steps 1 meter to the right. What is the probability of him staying alive?

```    0
/U\
H_____________________________
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

```

Session N 32 (05/28/2000)

Session questions

1. How many squares can you dissect a unit square into? Prove that one can dissect it into N squares for any natural number N greater than 5.

2. Prove that a unit square cannot be dissected into 2, 3 or 5 squares.

Homework questions

1. A hexagon ABCDEF is such that all triangles ABC. BCD, CDE, DEF, EFA, FAB are congruent. Prove that the diagonals AD, BE and CF are all equal.

2. Do there exist natural numbers a and b such that ab(a-b)=45045?

3. A 2x2 square was cut out from 5x5 table (cuts can go only along the grid lines) and the rest of the larger square was dissected into 1x3 polyminoes. Find all possible positions of the smaller square.

4. A chess king stands on the lower left square of a 100x100 chessboard. There are also 50 rooks positioned somewhere else on the board. The king makes his moves diagonally in the direction of the upper right square until it reaches the corner. After every king's move one (and only one) of the rooks moves as well. Prove that at some moment, no matter how the rooks move, the king will be in check (if the king has to move onto a square which is under attack that will also constitute being in check).

Session N 33 (06/04/2000)

Session questions

1. In Session 32 HW Question 3 solve the exactly same problem if the table has dimensions 7x7.

2. There is a machine that takes as an input cards with pair of non-negative integers (a,b) and produces output of the same kind. There are three operations the machine can perform:
I) given a card (a,b) the machine produces card (a+1,b+1);
II) given a card (a,b) with the even numbers the machine produces card (a/2,b/2);
III) given two cards (a,b) and (b,c) the machine produces card (a,c).
Also the machine returns all the original cards.
a) Given the card (0,0) determine all the cards that can be obtained using the machine.
b) Do the same if the original card was (0,1).
c) If the original card was (5, 19) can one eventually obtain card (1, 2000)?

Homework questions

0. In Question 2 determine what cards can be obtained if initially you have two cards (5,16) and (11,18)?

1. Every one of 102 students in the school has at east 68 friends there. Prove that at least four of them have equal number of friends.

2. There are 30 students in a class and they need to form a basketball team with 2 centers, 5 guards and 5 forwards. How many ways are there to do that? (we do not distinguish between two teams if one can be obtained from another by simply changing the order of forwards or centers or guards).

3. There are several spiders sitting on the edges of a unit wireframe cube. A spider tolerates a neghbor only if the distance between them (which is measured along the wire) is at least a) 1; b) 1.1. What is the maximum number of spiders that can peacefully inhabit the wireframe?

4. There is a pile of 1001 stones. Two players play a game making their moves in turn. Each move consists of removing N stones from the pile, where N is a power of a prime number, that is, pk, where p is a prime, and k is a non-negative integer. The player who makes the last move wins. Who wins if both players play errorless game?

Session N 34 (06/11/2000)

Session questions

1. Nine points lie on the intersections of three consecutive horizontal and three consecutive vertical gridlines. Construct a 4-segment broken line that passes through all nine points.

2. Dissect a square into five rectangles such that no two of them have coinciding common sides.

3. Dissect a square into several obtuse triangles.

Summer homework (2000)

1. Can one construct an 8-segment closed broken line that intersects every one of its own segments exactly once?

2. Bus tickets' numbers in Russia are sequences of six arbirary digits (can start with zeros). We will call a bus ticket "lucky" if the sum of its first three digits equals the sum of its last three digits. Prove that the number of all lucky tickets is the same as the number of tickets with the sum of all six digits equal to 27.

3. A unit segment is covered by several, possibly overlapping, smaller segments. Prove that one can select a few of them in such a way that they do not intersect and the sum of their lengths is at least 1/2.

4. a) Table with dimensions 10x10 is covered by fifty-five (possibly overlapping) 2x2 squares. Prove that one of them can be deleted while keeping the table completely covered.
b) What is the minimum number N such that if the table is covered by N similar squares then one of them can be deleted so that the table remains completely covered?

5. Prove that any number of the form a000..0b cannot be a perfect square (there is at least one zero between the first digit a and the last non-zero digit b).

6. Construct a tesselation of the plane into a set of squares such that only two squares have equal sides.

7. Positive numbers x and y are such that difference between square root of x and square root of y equals 10. Prove the inequality x-2y < 200.

8. A unit square is dissected into several rectangles. For every rectangle we compute the ratio of its shorter side to its longer side. Prove that the sum of all these ratios is at least 1.

9. For Fibonacci numbers Fk (F0 = 0, F1 = 1) prove the following facts:
a) Fm+n = Fm+1Fn + FmFn-1.
b) Fmn is divisible by Fm.
c) If Fn is a prime number then either n = 4 or n is prime.

10. Russian Treasury has an unlimited amount of coins of the following denominations: 1 kopeck, 2 kopecks, 5 kopecks, 10 kopecks, 20 kopecks, 50 kopecks, and 1 ruble. Numbers A and B are such that one can pay sum of A kopecks with B such coins. Prove that one can pay B rubles with A such coins.

11. Point M lies on side AB and point K lies on side BC of triangle ABC. Segments AK and CM meet at point O. Prove that if OM = OK and angles KAC and MCA are equal then ABC is isosceles.

12. There are N physicists and N chemists sitting at a round table, and it is known that some of them always lie and others always tell the truth. It is also known that the number of physicists-liars is the same as the number of chemists-liars. Each of the scientists says "My neighbor on the right is a chemist". Prove that N is even.

13. There are seven people sitting at a round table. Every one of them is either a knave (always lies) or a knight (always tells the truth). Each of them says: "My neighbors are a knave and a knight". Prove that all of these people are knaves.

14. In a rectangular table some of the boxes are marked with a star. It is known that for any marked box the number of stars in its row is the same as the number of stars in its column. Prove that the number of rows that contain at least one star equals the number of columns that contain at least one star.

15. A hundred and one points are arranged around a circle. A frog sits at one of the points and then it starts jumping clockwise with its first leap to the neighboring point, then it jumps over one point, then over two points et cetera. Prove that one of the points will never be visited by the frog.