MathCircle sessions (1999)

Click on a question mark image following a problem to see answer, solution or hint.

Session N 1 (09/19/1999)

Homework questions


1. In a 6 x 6 table all but one corner black box are painted white. You are allowed to repaint any column or any row in the table (i.e., you can select any row or column and change color of all boxes within that line). Is it possible to attain entirely white table by using a few of the permitted operations?

2. Four integers a, b, c, d produce 6 pairwise sums 2, 4, 9, 9, 14, 16. Is that possible? If a, b, c, d are not necessarily integers then what are their values?

3. A polygon was split by one straight-line cut into two triangles. How many vertices could that polygon have had?

Session N 2 (10/03/1999)

Session questions


1. John and Pete are tearing up a sheet of paper. John only tears a piece of paper into 3 smaller pieces while Pete only tears a piece of paper into 5 smaller pieces. After a few minutes can there be exactly 100 pieces of paper?

2. Without lifting a pencil from the paper can you trace all the unit segments of 3 x 3 table so that each segment is traced exactly once? You are allowed to visit a vertex more than once.

Homework questions


1. A 6 x 6 table is painted black and white so that in any 2 x 2 subtable the number of black boxes is even. You are allowed to repaint any column or any row in the table (i.e., you can select any row or column and change color of all boxes within that line). Prove that one can make the entire table painted white using only the permitted operations.

2. Prove that in any graph the number of odd vertices is always even.

3. Ten identical books cost more than $11, while nine of the same books cost less than $10. What is the price of one book?

4. Find all natural numbers p such that p, p+10 and p+20 are all primes.

Session N 3 (10/10/1999)

Session questions


1. Prove that the sum of degrees of all vertices in a graph equals twice its number of edges.

2. There are 100 rabbits sitting in 99 cages. Prove that one of the cages is occupied by at least two rabbits.

3. There are approximately 2.5 million people living in Greater Boston area. It is known that no human being has more than 1 million hairs on their head. Prove that there are two Bostonians with exact same number of head hairs.

4. Given 12 integers prove that difference between some two of them is divisible by 11.

5. There is a box with 31 candies and two players play a game making their moves in turn. A move consists of taking exactly 1 or 2 candies from the box. The player who cannot make a move loses. Who wins (the player who makes the first move or the other one) if both players play errorless game?

Homework questions


1. In a grocery shop there are 25 boxes with 3 types of apples (each box contains apples of only one type). Prove that one can find 9 boxes with apples of the same type.

2. Eight different natural numbers not greater than 15 are given. Prove that between their pairwise differences one can find three equal numbers.

3. One hundred poker chips are aligned in a row. It is permitted to perform the following operation: transpose any two chips that have exactly one other chip between them. Is it possible to reverse the order of chips using these operations?

4. There are three piles with 10, 15 and 20 stones respectively. Two players play a game making their moves in turn. A move consists of splitting any one pile with more than one stone into two smaller piles (not necessarily equal). The player who cannot make a move loses. Who wins (the player who makes the first move or the other one) if both players play errorless game?

Session N 4 (10/17/1999)

Session questions


1. A chess king occupies box h8 on a chessboard. Two players play a game making their moves in turn. The player who cannot make a move wins. A move consists of moving the king one box to the left, or one box down, or one box diagonally left-down. Who wins in an errorless game?

2. (THEOREM) Two players play a game making their moves in turn. The player who cannot make a move wins. It is known that the game has a finite number of possible positions. Prove that in the beginning one of the players has a winning strategy, that is, he/she can win regardless of other player's moves.

3. There are two piles of candies with 100 and 101 candies respectively.Two players play a game making their moves in turn. The player who cannot make a move wins. The move consists of taking some arbitrary number of candies (at least one) but from one of the piles only. Who wins in an errorless game?

4. Remainders modulo natural number k: if we know remainders for numbers A and B then we can calculate remainders for their sum A+B and their product AB (without knowing A/k or B/k).

Homework questions


1. There are 20 points selected on a circumference. Two players play a game making their moves in turn. A move consists of connecting some two of the selected points with a segment that doesn't intersect any of the previously drawn segments (they can have a common vertex but not a common interior point). The player who cannot make a move loses. Who wins (the player who makes the first move or the other one) if both players play errorless game?

2. Prove that there exists natural number n such that 3n ends with digits 01.

3. Write tables of addition and multiplication for remainders modulo 5, 6 and 7 (six tables in all).

4. Ten baseball teams are playing round-robin tournament (each team plays each other exactly once). Prove that by any moment of time some two teams have played equal number of games.

Session N 5 (10/24/1999)

Session questions


1. Prove that there exists natural number n such that 3^n ends with digits 001 (a generalization of homework problem).

2. How many zeroes does the number 100! end with?

3. There are two cities A and B on the same side of a river whose shoreline is a straight line L. What is the shortest path from A to B that touches line L?

Homework questions


1. There are 101 points selected on a circumference. Two players play a game making their moves in turn. A move consists of connecting some two of the selected points with a segment that doesn't intersect any of the previously drawn segments (they cannot even have a vertex in common). The player who cannot make a move loses. Who wins (the player who makes the first move or the other one) if both players play errorless game?

2. In the sequence of digits 12345678910111213...57585960 (built by writing natural numbers 1 thru 60 in a row) cross out 9 digits so that the number formed by the remaining digits will be a) maximum possible b) minimum possible.

3. Solve the alphanumeric puzzle YDAP + YDAP = DPAKA.

4. a) There are two cities A and B on a peninsula formed by two rays starting from the same point (angle between the rays is acute). What is the shortest path connecting A, some point on the first shore, some point on the second shore, and then city B?
b) There are two cities A and B on opposite sides of a river whose banks are two parallel lines. Inhabitants of the two cities decided to build a bridge across the river perpendicular to the banks. Where do they need to build it so that the path from A to B will be the shortest possible?

Session N 6 (10/31/1999)

Session questions


1. Solve the Question 4a from Session 5's homework if the angle formed by the rays is obtuse.

2. State and prove the divisibility rules for decimal base system when dividing by 2, 3, 4, 5, 6, 8, 9, 10, 11, 12.

3. Prove that 111..111 (2001 digits) is not an exact square.

Homework questions


1. A fly is stuck on the upper lid of a cylinder can. A spider sits in some point on the lower lid. Find the shortest path the spider can crawl to his prey across the surface of the can.

2. Prove that 896002838670906 is not an exact square.

3. Let us denote by S(x) the sum of digits of a natural number x. Number A has 7 digits, S(9A) = B, and S(B) = C. Find C.

4. The plane is painted black and white (that is, every point on the plane is painted either black or white).
(a) Prove that there are two points of the same color positioned exactly 1 cm apart.
(b) Prove that there exists a segment on the plane whose ends and middle point are of the same color.

Session N 7 (11/07/1999)

Session questions


1. See homework question 1 from session 6 for a cube-shaped can.

2. Tom caught Jerry and is prepared to have him for breakfast if Jerry doesn't prove his superior intellect. To test that, Tom thinks of three digits (0 thru 9, not necessarily different) a, b, and c; then Jerry must give him three natural numbers x, y and z, and after that Tom will let Jerry know the value of the sum ax+by+cz. If Jerry can find out the digits Tom thought of, he will be set free. Otherwise it is not going to be pretty... What is the surviving strategy for Jerry?

3. There are three villages situated on a flat plateau with 35, 20 and 10 children of school-going age respectivelyu. The state education committee decided to build a new school and they are trying to figure out the location in such a way that the overall distance traveled by all the children daily is minimum possible (no school bus is available). Where do they have to build the new school?

4. For the game from homework question 1 from session 5 find winning strategies when n (number of points) equals 1, 3, 5, 7, 9, 11, 13. Prove that the first player wins for both n = 11 and 13! What about n = 15?

Homework questions


1. The plane is painted using three colors (that is, every point on the plane is painted either red, green, or blue). Prove that there are two points of the same color positioned exactly 1 cm apart.

2. See session question number 3.

3. Ten numbers are written around a circle in such a way that any number equals exactly half-sum of its two neighbors. Prove that all the numbers are equal.

4. Point P is located inside triangle ABC. Prove that
a) 2(PA+PB+PC) is no less than AB+AC+BC
b) PA+PB+PC is no greater than AB+AC+BC

Session N 8 (11/14/1999)

Session questions


1. There are several coins of different size laid out on the moneychanger's table so there is no overlapping (touching is not allowed). A thief who cannot use his arms wants to steal one of the coins by leading the coin to the edge of the table with the help of his nose. However, if the coin touches any other on its path the moneychanger will hear the sound and the thief will be caught. Prove that the thief can steal one of the coins.

2. Fields a1 and h8 are cut out from 8 x 8 chessboard. Is it possible to cover the rest of the board by dominoes 1 x 2 without overlapping?

Homework questions


1. Boxes of 8 x 8 table are filled with numbers so that every number equals arithmetic mean of its neighbors. Prove that all numbers are equal.

2. There are several coins (possibly of different sizes) laid out on the flat table so there is no overlapping (touching is allowed). Prove that one of the coins touches no more than 6 other coins.

3. A bunch of consecutive sheets has fallen out from an old book. The first page of this bunch is page 387, and it is known that the last page's number is written by the same digits but in different order. How many pages have fallen out?

4. Is it possible to cover 10 x 10 board with T-shaped poliminoes (formed by 4 boxes) without overlapping?

Session N 9 (11/21/1999)

Session questions


1. Prove that in homework question 2 from session 8 there is a coin that touches no more than 5 other coins.

2. Sylvester Theorem: prove that for any finite set of points on a plane that do not all lie on one straight line there exists a straight line passing through exactly two of these points.

3. Find out when the number of divisors of a natural number is odd or even.

4. Prove that square root of 2 is irrational number.

5. Battalion of soldiers stands on a marching ground in the form of rectangle. In every row the tallest soldier is selected and John Smith is the shortest one of them. Then in every column the shortest soldier is selected and Jacob Brown turns out to be the tallest one of them. Who is taller: John or Jacob?

Homework questions


1. Is it possible to cover 10 x 10 board with 1 x 4 poliminoes without overlapping?

2. Prove that square root of 6 is irrational number.

3. Prove that you can pay any amount greater than 7 kopecks if you have enough coins with value of 3 and 5 kopecks.

4. A policeman is pursuing a gangster on the streets of Gotham City whose map is:

  • a) rhombus whose sides and one of the diagonals are all of the same length (they are the streets).
  • b) 1 x 2 table with all the lattice segments of the same length.
    Create a winning strategy for the policeman if it is known that his best speed is twice that of the gangster's best speed.

    Session N 10 (12/05/1999)

    Session questions


    1. Find G.C.D. for the following pairs

  • (73, 91);
  • (1111973, 1111991);
  • (n, n+1);

    2. How many ways are there to select a) one; b) two out of three tennis balls?

    3. How many ways are there to select two out of ten tennis balls? Three out of ten?

    4. We have ten red and ten blue tennis balls. How many ways are there to select two balls of a) different color; b) the same color?

    5. How many ways are there to arrange ten tennis balls in a row?

    Homework questions


    1. Find G.C.D.(n, 3n+1).

    2. How many ways are there to arrange 10 red and 10 blue tennis balls in a row (no distinction is made between the balls of the same color)?

    3. There are 6 persons in a room. Prove that there are either three of them such that every two of them are acquainted with each other or three of them such that every two of them are NOT acquainted with each other.

    4. Can one find three integers such that the sum of their squares equals 1999?

    Session N 11 (12/12/1999)

    Session questions


    1. What values can G.C.D.(2n-3, 3n+5) take?

    2. Prove that the number of ways to select k objects out of n is n!/k!(n-k)!.

    3. Formulas for (a+b)2, (a+b)3.

    4. In Question 3 from Session 10 HW: is the same true if there are only 5 people in the room?

    Homework questions


    0. Write the formulas for (a+b)k for k = 4, 5, 6, 7.

    1. A grasshopper makes 25 jumps along the straight line jumping each time to the left or to the right. The length of the first jump is 1cm, of the second jump - 2 cm, then 3 cm, etc. Can the grasshopper end up in the same point it started from?

    2. There are 15 cities in a country and some pairs of them are connected with the paved roads. It is known that at least 7 paved roads are going out of every city. Prove that one can drive from any city in the country to any other using the paved roads only (in other words, the graph of the cities and roads is connected).

    3. Find all 3-digit numbers ABC such that ABC is divisible by 7, A+B+C is divisible by 7 and all three digits A, B and C are different.

    4. Prove that in a convex quadrangle sum of the sides is greater than the sum of the diagonals.

    Session N 12 (12/19/1999)

    Session questions


    1. Prove the Newton's binomial formula for (a+b)n.

    2. Prove that the numbers in Pascal's triangle (the binomial coefficients) comply with the following property: every number equals the sum of its two neighbors from the previous line.

    Homework questions


    1. Twenty-one boys gathered 209 apples during their field trip. Prove that some two of them have the same amount of apples.

    2. Find a and b if a-b = 5 and a/b = 5.

    3. a) There are 7 coins lying on a table - all of them with their "head" side up. It is permitted to perform the following operation: take any four of the coins and turn them over. Is it possible that after several such operations all the coins will be lying "tails up"?
    b) Same question for 10 coins.

    4. What is the maximum possible number of 2 x 4 poliminoes that can be placed inside 7 x 7 square without overlapping?

    Back to MathCircle Homepage

    Back to DF-ES Homepage