Review and discussion of solutions to the summer homework questions 1, 2, 7, 9, 11, 12, 13, and 14.

The rest of the summer HW is due next session.

Review and discussion of solutions to the summer homework questions 3, 4, 5, 6.

Questions 8 and 10 of the summer homework are due next session.

1. Is it true that a graph with 16 vertices, each with degree 3, must have a hamiltonian path - that is, a non-self-intersecting path passing through all the graph's vertices?

1. Two gifted mathematicians were each given a secret natural number - the only information they have is that their numbers are natural and differ by one. They take turns asking each other the same question again and again: "Do you know my number?" Prove that eventually one of them will answer positively.

2. A farm has four warehouses built in the vertices of a square with side length equal to 10 miles. Owners need to connect them all with a network of paved roads but they only have enough money to pay for 28 miles of pavement. Show how they can carry out their plan.

1. Two non-intersecting perpendiculars are dropped from points on the sides of an angle to the opposite sides. Prove that the perpendicular which is farther away from the vertex has greater length.

2. If three planar forces acting upon an object result in an equilibrium, then what equation must be true for the three vectors of these forces?

Summer homework questions 10 and 15 are due next session. And also:

1. There is a number written on each face of a cube. For every pair of adjacent faces the absolute value of the difference of the two numbers written on them is calculated. Prove that the twelve numbers obtained can be split into two six-number groups with equal sums of their members.

2. A sequence of numbers (a_{n}) is defined as follows:
a_{1} = 19, a_{2} = 97, and a_{n+2} =
(a_{n+1}+1)/a_{n} for any natural n. Find
a_{1997}.

1. When a segment is projected onto a line, how does it change its length?

1. Find the limit of (1 - cos x)/x when x tends to zero.

2. Diagonals in a convex quadrangle ABCD intersect at point O. It is known that AB = BC = CD, and angle AOD is half of the sum of BAD and CDA. Prove that ABCD is a rhombus.

3. Find any two 10-digit numbers such that their LCM equals the square of their difference.

4. Ten coins are laid out in a row. Some of them are genuine weighing exactly 10 g, and some are counterfeit weighing 9 g (it is known that both types are present). It is also known that each genuine coin lies to the left of any counterfeit one. Is it possible to find all the genuine coins using only two weighings on a two-cup balance (no additional weights are provided)?

1. Find a function that at point 0 is an infinitesimal of lesser order than f(x)=x.

2. Prove that for any two natural numbers their product equals the product of their LCM and GCD.

1. There are 2002 employees in Central Bank of Mathematistan. They all came to an anniversary party and were seated at one round table. It is known that salaries of any two neighbors differ by either 2 or 3 thousand dollars. What is the maximum possible difference in two salaries in the bank provided they all are different?

2. All the types of Russian flora were enumerated with indices 2 thru 20000 without skips and repetitions. For any pair of plants the greatest common divisor of their indices was saved in a separate database but the indices themselves were later lost due to a computer malfunction. Is it possible to restore all the indices based on the GCD data?

3. Right triangle ABC has legs AC = 3, BC = 4. Then point A is translated some distance parallel to BC. Then B is somehow moved parallel to AC. And finally C is translated parallel to AB. After all these transformations it turned out that CBA is a right angle and AB = 1. Find BC.

4. Number A of form 1000...0001 is divisible by 19. Prove that A is divisible by 13.

1. Prove formulas for sin(x+y), cos(x+y).

2. Prove that R = abc/4S, r = 2S/p, where a,b,c denote sides of a triangle, S is the triangle's area, p is the perimeter, R and r are radii of its circumscribed and inscribed circles respectively.

1. There are 10 coins such that exactly two of them are counterfeit. A coin detector operates in the following way: when presented with some three coins it selects one of them. It is known that detector cannot select a genuine coin if the trio contains at least one counterfeit coin. Find both counterfeit coins using six operations of the detector.

2. A perpendicular bisector to side BC of triangle ABC intersects segment AB at point D and segment AC extended thru point A at point E. Prove that AD is shorter than AE.

3. There are three identical pots of honey and Winnie the Pooh, Piglet and Rabbit play the following game. Winnie can eat only from pots 1 and 2, Piglet only from pots 2 and 3, and Rabbit only from pots 3 and 1. Each one of them can consume either one or two full spoons of honey at a time. They take turns making their moves and the one who cannot make a move (that is, eat one full spoon from any of his "assigned" pots) loses. Prove that Winnie the Pooh and Piglet can together ensure that Rabbit loses.

4. Given three prime numbers p_{1}, p_{2}, and p_{3}
prove that

(p_{1}+p_{2}+p_{3})^{3} -
(-p_{1}+p_{2}+p_{3})^{3} -
(p_{1}-p_{2}+p_{3})^{3} -
(p_{1}+p_{2}-p_{3})^{3}

is divisible by p_{1}p_{2}p_{3}.

1. Which number is greater: sin(1000) or cos(1000) ?

2. Prove that two vectors are perpendicular if and only if their dot product is zero.

1. Sequence of numbers (a_{n}) starts with a_{1} = 2
and a_{n+1} = a_{1}a_{2}...a_{n} + 1
for any n = 1, 2, ... Prove that for any n

1/a_{1} + 1/a_{2} + ... + 1/a_{n} < 1.

2. Prove that in any polygon one can find side BC and vertex A (different from B and from C) such that foot of the perpendicular dropped from A to line BC lies on segment BC,

3. A martian is always born at midnight and lives for exactly 100 days. It is known that throughout the entire history of Martian civilization (now completely extinct) there was odd number of Martians born. Prove that there were at least 100 days when population of Mars was an odd number.

4. Solve simultaneous equations

a = bcd

a+b = cd

a+b+c = d

a+b+c+d = 1

1. Prove that n-member sequence z_{k} = 1/a_{k}
for k < n, z_{n} = 1/(a_{n}-1) (here a_{k} is
the number sequence from Session 110 HW Question 1) provides the only
solution for simultaneous equations:

x_{1}x_{2}...x_{k} = x_{k+1}+
x_{k+2}+...+x_{n}

(n here is a fixed natural number, k is any integer from 0 thru
n-1; when k=0 the left side is 1).

1. Prove that for any natural n the second last digit of 3^{n}
is even.

2. Two rays emanating from vertex A of square ABCD are built in
such a way that they both intersect the square and vertex C lies between
them. Perpendiculars from vertices B and D to both rays are dropped to
produce four points - namely, feet of these perpendiculars. What is the
area of the quadrangle formed by these four points if side of ABCD is 1
and angle between two rays equals *u*?

3. Two players in turns increase natural number written on a board so that after every move the difference between new value and old value is positive but less than the old value. Initial value of the number is 2. The player who obtains 1987 wins. Who wins in the errorless game?

4. Ten friends sent out Christmas postcards (strictly within this group) so that each one sent cards to exactly five of his friends. Prove that some two of them have exchanged Christmas greetings.

1. Solve Session 111 HW Question 3 if 1987 is substituted by a) 2002; b) 1900. What if it is an arbitrary natural number N > 1?

2. Solve equation sin(x) + cos(x) = 1.

1. Find all natural numbers divisible by 30 that have exactly 30 different divisors.

2. All sides and diagonals of a quadrangle are shorter than 1. Prove that it can be covered by a circle with radius 0.9.

3. Prove that in an infinite sequence of different natural numbers greater than 1 it is always possible to find one hundred members such that each of them is greater than their index in the sequence.

4. In the country of Graphland there are N cities and each two are connected by exactly one road. The roads do not intersect each other (when they accidentally meet outside of the cities one of them is elevated to form a bridge over another). A ministry of transportation made all the roads one-way in such a way that if you leave a city you can never come back. Prove that there exists exactly one path that follows the traffic rules and goes through all the cities.

1. Prove that one can cover a triangle whose sides are all shorter than 1 with a circle of radius 2/3.

1. Solve equation cos(x) + cos(2x) + 1 = 0 for 0 < x < 2(pi)

2. Angle bisectors BD and CE in triangle ABC intersect at point O. Prove that if OD = OE then either ABC is isosceles or angle A equals 60 degrees.

3. A small township is built in form of a square with 9 blocks (3 blocks by 3 blocks). What is the shortest path for the asphalt-laying machine to cover all the streets if it begins and ends in the corner point A? (sides of the big square are also streets).

4. On a chamber music festival there are six participants. During every concert some of them play on stage and all the others listen from the chairs. What is the minimum number of concerts necessary for every musician to hear each other at least once?

1. Reminder about Helly's theorem: if any three out of four convex sets on the plane have a common point then all four have a common point. Use that to solve Session 112 HW Question 2 (perhaps even with better estimate for the radius).

1. Point M is taken inside square ABCD. Prove that centroids of triangles ABM, BCM, CDM, DAM form a square.

2. Find all natural numbers *n* that can be represented as a
sum of two co-prime numbers both greater than 1.

3. Find any positive number *a* such that
{*a*}+{1/*a*} = 1 (here {} denotes a fractional part of a
real number). Can such a number be rational?

4. A class consists of 32 students. Thirty-three study groups were organized such that each group has exactly three students and no two of the groups coincide. Prove that some two groups have exactly one student in common.

1. Express a vector going from point O to centroid of triangle ABC via vectors OA, OB and OC.

1. In convex quadrangle ABCD diagonal AC divides its middle line MN (M is midpoint of BC, N is midpoint of AD) in half. Prove that triangles ABC and ACD have the same area.

2. Vertices of regular 10-gon are painted black and white, alternating in color. Two players play the following game making their moves in turn. A move consists of drawing a segment connecting two identically colored vertices; any two of these segments must not intersect (even at the ends). The player who makes the last move wins. Who wins in the errorless game?

3. Numbers 1 thru 64 are written into the boxes of a chessboard: first row has numbers 1 thru 8 from left to right, second row - numbers 9 thru 16 from left to right, etc. Every number is then somehow assigned either plus or minus sign so that every row and every column have exactly four pluses and four minuses. Prove that the sum of all numbers on the chessboard is zero.

4. All the dumbells in a set weigh 1, 2, 4, 8, ... (power of two) grams; some of the dumbells can have the same weight. Two sets of dumbells are in equilibrium on a two-pan balance, and it is known that all the weights on the left pan are different. Prove that the number of the dumbells on the right pan is greater than or equal to the number of the dumbells on the left pan.

1. Prove that vectors OP where P lies on straight line AB are exactly the ones that can be represented as tOA + (1-t)OB, where t is a real number. Also show that points from segment AB correspond to values of t in [0;1].

2. In right triangle ABC (angle A equals 90 degrees) express AH (altitude) as a vector via vectors AB and AC.

3. Solve HW Question 2 Session 115 for any regular 2n-gon.

1. Prove that for any natural n the following equality holds true:

(1/n)^{2} + (1/n + 1/(n-1))^{2} + ... +
(1/n + 1/(n-1) + ... + 1)^{2} = 2n - (1+1/2+1/3+...+1/n)

2. There are 61 coins exactly two of which are counterfeit. It is known that all genuine coins weigh the same, and all the counterfeit coins weigh the same but differently from the genuine ones. It is not known, however how the weight of a genuine coin differs from the weight of a counterfeit one. Determine that (whether genuine coin is heavier or lighter) using only three weighings on a two-cup balance without any additional weights.

3. Prove that if product of two positive numbers is greater than their sum then that sum is greater than 4.

4. Square table 8 x 8 is colored white. It is allowed to choose any rectangle 1 x 3 and change color in all of its boxes. Is it possible to achieve all-black table using only these operations?

1. What is the minimum number of comparison operations to find maximum number out of the set of N different numbers? two maximum numbers?

1. Two chessplayers played one game with time control using
standard double clock: after each move a player stops his clock
automatically resuming an opponent's clock. It is known that after
both of them made 40 moves their clocks both showed exactly 2h30m.

a) Prove that during the game there was a moment when difference
between the clocks was at least 1m51s.

b) Can we be sure that at some moment difference between the
clocks was exactly 2m?

2. Two straight lines are drawn through vertices A and B of triangle ABC. They divide the triangle into four parts - three triangles and one quadrangle. Given that three of these four parts have equal areas prove that the quadrangle is among them.

3. Twenty soccer teams participate in a tournament. In the first day all the teams played one match each. Same was true for the second day as well. Prove that after the second day it is possible to find ten teams such that no two of them have yet played each other.

4. Sequence of numbers (x_{k}) is such that x_{1}
= 1/2 and x_{k+1} = x_{k}^{2}+x_{k}
for any natural k. Find the integer part of the sum
1/(x_{1}+1)+1/(x_{2}+1)+...+1/(x_{100}+1)

5. Thirty students decided to visit each other's homes (during
afterschool hours). It is known that during one evening a student can
visit several homes but on any day when he has guests he doesn't
go anywhere. Prove that for each student to visit everybody else

a) four evenings aren't enough.

b) five evenings aren't enough.

c) ten evenings are enough.

d) seven evenings are enough.

Back to **MathCircle Homepage**

Back to **DF-ES Homepage**