1.In Session 48 HW Question 3 try to find a solution if the number of digits is not given.

2. In Session 48 HW Question 6 can there be exactly nine cities in such a country?

1. For some natural number *n* *x = n ^{2}+1* is a 10-digit number. Prove that some two of its digits are equal.

2. City of Polygon is a convex polygon with sides and diagonals its streets. It is known that no three of its diagonals meet at the same interior point. In all the vertices and points of intersection of the diagonals the city has built tram stops. Also the tram tracks were built so that some of the streets are tram lines and every tram stop is served by at least one line. Prove that one can get from each stop to any other by tram with no more than two transfers.

3. There are two counterfeit coins among nine given coins. Genuine coins weigh 10g, while counterfeit coins weigh 11g. Using scale with one pan (which simply measures the weight put into the pan) determine both counterfeit coins with no more than 5 weighings.

4. Point C is given within a rectangular quadrant with vertex O. Point X is chosen on one side and point Y is chosen on another side of the quadrant. Prove that the perimeter of triangle XYC is greater than or equal to double length of segment OC.

1. Write 12345_{10} and 1000_{10} in the number system with base 7.

2. Write 532_{8} in the number system with base 3.

3. What is the value of 592_{7}?

1. There is a partially erased example of addition written on a blackboard:

2 3 5 1 6 4 2 _____________ 4 2 4 2 3Find out the number base this addition is done in and the numbers themselves.

2. Boxes of a rectangular table are filled with real numbers. Operations of the following type are allowed: choose any row or column and change signs of all the numbers on that line. Prove that using these operations one can obtain a table such that for any line (ie, row or column) the sum of its numbers is non-negative.

3. Is the decimal fraction 0.12345678910111213...202122... periodical?

4. Natural numbers *a* and *b* are such that
*a ^{2}+ab+1* is divisible by

1. How many different tables can be obtained by permitted operations in Session 50 HW Question 2? Answer should be a range of all possible integers.

2. There are *n* weights and a regular two-pan balance that is used to weigh sugar for the customers. If the weights can be placed on both cups of the balance then what is the maximum number *W* such that any integer weight from 1 thru *W* can be measured out using the balance and the weights? And what must the weights be?

3. Among numbers 0, 1, 2, ..., 3^{k}-1 select 2^{k} numbers such that none of them equals arithmetic mean of two other selected numbers.

1. Positive numbers *a*, *b*, *c* are such that their sum equals 6. Prove that the sum of their squares is greater than or equal to 12.

2. Square table 6 x 6 is covered by dominoes without overlapping. Prove that there is a line parallel to one of the sides of the table that dissects the table without cutting any of the dominoes.

3. Points A, B and C are all nodes of the unit grid on the plane. It is known that AB > AC. Prove that AB - AC > 1/*p*, where *p* is perimeter of triangle ABC.

4. Find all the natural solutions for the simultaneous equations

a^{2} + b - c = 100

a + b^{2} - c = 124

1. Prove Session 51 HW Question 2 for tables with dimensions 4 x 4. What if the table has dimensions 8 x 8? 5 x 6?

2. Draw all different (non-isomorphic) trees with the number
of vertices *V*, where *V* equals 1, 2, 3, 4, 5, 6, 7.

1. Prove that in any convex polygon the sum of any two angles is greater than or equal to the difference of any two other angles.

2. Do there exist two different 7-digit numbers written with digits 1, 2, 3, 4, 5, 6, 7 without repetition such that one of these numbers is divisible by the other?

3. Two neighboring countries Dillia and Dallia have currencies named, respectively, diller and daller. In Dillia exchange rate is 1 diller = 10 dallers. In Dallia, I daller is exchanged for 10 dillers. A businessman has 1 diller and can travel between two countries free of charge. He doesn't spend any money but only exchanges some of it. Prove that he will never have equal amounts of dillers and dallers in his possession.

4.^{*} Several identical race cars are arbitrarily
positioned along a circular racetrack. It is known that the overall amount of gas in their tanks is sufficient for one car to drive around the track. Prove that one of these cars can indeed drive full circle if it is allowed to collect gas from the vehicles it encounters on its way.

1. a) There are 8 numbers positioned in the vertices of a cube: seven zeroes and 1. Using the following operations - for any edge increase numbers on its ends by 1 - can one make all the numbers equal?

b) What if the numbers are seven zeroes and 2?

c) What if three zeroes and 1 are positioned in the vertices
of a tetrahedron?

d) Same question for three zeroes and 2.

e) Prove that if it is allowed to use converse operations
(that is, decrease numbers on the ends of any edge by 1) then
any set of numbers in the vertices of the tetrahedron with even
sum can be transformed into any other such set.

f) What is the complete invariant for "cube" version of
our question (items a-b)?

1. There are 101 coins only one of which is counterfeit whose
weight is different from the weight of a genuine coin. Using two
weighings on a regular two-cup balance find out whether the
counterfeit coin is heavier or lighter than genuine ones.
(*Warning*: do not attempt to find the counterfiet coin itself! we are only interested in finding out if it is heavier than genuine coins or not).

2. In a village for every boy all his girl acquaintances know each other. Also every girl knows more boys than girls. Prove that in the village the number of boys is greater than or equal to the number of girls.

3. In quadrangle ABCD BC = AD; M is midpoint of AD and N is midpoint of BC. Perpendicular bisectors for segments AB and CD intersect at point P. Prove that P also lies on perpendicular bisector for segment MN.

4. A square with dimensions 2 x 2 is dissected into several (more than one) rectangles. Prove that you can shade some of them so that the projection of the shaded figure onto one side of the square will have length greater than or equal to 1 and its projection onto another side will have length not greater than 1.

1. On the island of knights and knaves, the following conversation
between three natives A, B and C was overheard.

A: All of us are knaves

B: Exactly one of us is a knave.

Can it be determined who they are?

2. In the same setting:

A: B is a knave

B: A and C are of the same type

(Being of the same type means that either both people in question are knights or both are knaves). Can it be determined who they really are?

3. In the same setting:

A: B and C are of the same type.

Someone then asks C: "Are A and B of the same type?" What will be the answer?

4. On the island of knights, knaves and normals: there are three people A, B and C one of whom is a knight, one is a knave and one normal. They say:

A: I am normal

B: That is true.

C: I am not normal.

What are A, B and C?

5. On the island of knights, knaves and normals knaves are said to be of lowest rank, normals of middle rank, and knights of highest rank. Two people A and B make the following statements:

A: I am of lower rank than B.

B: That's not true!

Can their ranks be determined?

6. Same setting: three people A, B and C one of whom is a knight, one is a knave, and one normal. They say:

A: B is of higher rank than C.

B: C is of higher rank than A.

If C is asked "Who has higher rank, A or B?" what does C answer?

7. Several islanders are sitting around a table and each one of them says: "My neighbor on the right is of higher rank that myself". Who are these people?

8. On that same island knights are only permitted to marry knaves, and knaves only can marry knights (therefore normals can only marry normals). Two spouses make the following statements.

Mr.A: My wife is not normal. (b) is normal

Mrs.A: My husband is not normal. (b) is normal.

Who are Mr. and Mrs. A?

9. Same setting: two married couples A and B make the following statements.

Mr.A: Mr.B is a knight.

Mrs.A: My husband is right. Mr.B is a knight.

Mrs.B: That's right. My husband is indeed a knight.

What are each of these four people?

1. At a school dance party no one boy managed to dance with all the girls, but every girl danced with at least one boy. Prove that one can find two boys B_{1} and B_{2} and two girls G_{1} and G_{2} such that B_{1} danced with G_{1}, B_{2} danced with G_{2} but B_{1} didn't dance with G_{2} and B_{2} didn't dance with G_{1}.

2. Prove that number 222..22 (1982 digits) cannot be represented as xy(x+y) where x and y are natural numbers.

3. Three people A, B and C played table tennis. In every match two of them played each other and then the loser yielded his place to the third person etc. When they were finished it turned out that A played 10 matches while B played 21 matches. How many matches did C play?

4. A sequence of digits starts with 1, 9, 8, 2, and then every next member is calculated as the last digit of the sum of the four previous members of the sequence. Will there ever be four consecutive digits 3, 0, 4, 4 occurring in this sequence?

5. In a five-angled star ABCDE (vertices are listed according to the regular transversal; not clock- or counterclockwise!), angle A equals angle D, angle B equals angle C, and AB = CD. Prove that AE = DE.

6. Ninety-nine 2 x 2 squares were cut out from a sheet of graphed paper with dimensions 31 x 31 (small squares' sides must lie on gridlines). Prove that one can cut out one more 2 x 2 square out of the remains of the sheet. Is it true if a hundred squares had been cut out?

1. Three people A, B and C played a sequence of table tennis games. In every game two of them played each other and then the loser yielded his place to the third person etc. When they were finished it turned out that A played 10 games, B - 15 games and C - 17. Who lost in the second game?

2. Three people A, B and C played a sequence of table tennis games. In every game two of them played each other and then the loser yielded his place to the third person etc. When they were finished it turned out that A won 10 games, B won 12 games and C won 14 games. How many games did each of them play?

1. A square table with dimensions 1000 x 2001 is dissected into parts by the gridlines and by one of its main diagonals. How many parts are there altogether?

2. Number 101...101 is written by k zeros and k+1 ones (zeros and ones alternate). Prove that it is a composite number if k is greater than 1.

3. A triangle is formed by three segments whose lengths are consecutive natural numbers. It is also known that one of the triangle's medians is perpendicular to one of its angle bisectors. Find the length of its sides.

4. A tiling of a 7 x 7 square used three types of poliminoes: 1) "corner" trimino; 2) 2 x 2 square; 3) an "S" tetromino. Prove that exactly one tetromino (that is, of types 2 and/or 3) was used in the tiling.

1. How many ways are there to choose 20 coins from 20 nickels and 20 dimes?

2. How many ways are there to choose 20 coins from 20 pennies, 20 nickels and 20 dimes?

3. How many ways are there to put seven black balls and two white balls into 9 numbered (that is, different) holes?

4. How many ways are there to divide six identical apples, a pear, a plum and an orange between three people?

5. How many ways are there to put 4 black balls, 4 white balls and 4 red balls into 6 different boxes?

1. How many ways are there to arrange 5 red balls, 5 green balls and 5 blue balls in a row if no two red balls are allowed to be neighbors?

2. There are several regular triangles made of plastic with numbers 1, 2 and 3 written in the corners of each one of them. Is it possible to arrange them in a stack in form of triangular prism so that the sum of the numbers along every edge of the stack equals 55?

3. A rectangular table is filled with natural numbers. There are two operations allowed to perform on the table: 1) to double all the numbers within a row; 2) to subtract one from all the numbers of a column. Prove that using these operations one can turn all numbers in the table into zeros.

4. There are 2n (n > 1) straight lines drawn on the plane such that no two of them are parallel and no three intersect at the same point. Prove that among the parts they divide the plane into there are no more than 2n-1 angles (ie, infinite parts with only one vertex).

1. On the plane n straight lines no two of which are parallel and no three of which intersect at one point are drawn. Prove that there are exactly 2n infinite parts among those that these lines dissect the plane into.

2. A convex figure S is given on the plane. Prove that if a straight line doesn't contain an entire segment of F's boundary then it cannot intersect the boundary in more than two points.

1. Boxes of 5 x 41 table are arbitrarily colored black and white. Prove that one can select three rows and three columns in such a way that all nine boxes at their intersections are colored identically.

2. Baron Munchhausen (famous traveller and fibber from old German tales) has invented a time machine which can transfer a person instantaneously from March 1 (of any year) to November 1 (of any year), from April 1 to December 1 (of any year), from May 1 to January 1 etc. However, one cannot use the machine two times in a row (waiting for it to cool off takes at least a few days). The baron undertook a time travel on April 1 of 2001 and immediately returned back from it. He reported that his trip took him exactly 26 months. Prove that he is, as usually, mistaken.

3. Prove that 2^{58}+1 can be represented as a product of three natural numbers each greater than 1.

4. Vertices of a triangle are colored blue. Is it possible to put other 10 blue poiints and 20 red points inside this triangle in such a way that no three blue points lie on a straight line and any triangle with blue vertices has at least one red point inside of it?

1. Solve the Diophantine equation 3x + 5y = 7.

2. Solve the Diophantine equation 3x - 12y = 7.

0. Solve the Diophantine equation 1990x - 173y = 11.

1. Digits a and b are such that ab/bc = a/c. Prove that abb...bb/bb...bbc = a/c. (Here ab, bc etc. denote the numbers written by the given digits in the given order and the numbers abb...bb and bb...bbc both have exactly one hundred digits).

2. There are two cities Alphaville and Betaville which are 100 miles apart. Two cyclists A and B started riding toward each other, A from Alphaville with velocity 20 mph and B from Betaville with velocity 30mph. A fly started from Alphaville simultaneously with A flying with velocity 50mph - it flies toward B until they meet then it turns around and flies toward A until they meet then it turns around and flies toward B etc. and so on until A and B meet. How many miles will the fly eventually cover in the direction from A to B until the end of its flight?

3. In quadrangle ABCD point M is the midpoint of AB and point N is the midpoint of CD. Lines AD and BC intersect line MN at points P and Q respectively. If it is known that angles BQM and APM are equal prove that BC = AD.

4. Natural numbers a, b, k, l, m, n satisfy the following conditions:

m/n < a/b < k/l ; kn - ml = 1

Prove that b is greater than or equal to n+l.

1. Two sets of segments A_{1}, ..., A_{17} and B_{1}, ..., B_{17} on the straight line are such that for any k = 1, ..., 17 segment A_{k} has non-empty intersection with both B_{k-1} and B_{k+1} where B_{0} denotes B_{17} and B_{18} denotes B_{1}. Prove that for some k segments A_{k} and B_{k} have non-empty intersection.

2. What is the minimum number of chess kings such that for any arrangement of them on the chessboard there will always be a field under attack by at least two kings? (a king always attacks a field it occupies).

3. Prove (without ANY help of calculators, computers and other similar brain-numbing devices) that number 53 x 83 x 109 + 40 x 66 x 96 is composite.

1. Solve Diophantine equation xy = x + y + 3.

2. A snail is crawling along the plane with constant speed making a 60^{o} turn every half hour. Prove that it can return to the original point only after a whole number of hours.

3. A lucky 6-digit bus ticket is the one with the sum of the first three digits equal to the the sum of its last three digits (see Session 34, Summer homework Question 2). How many tickets in a row must one buy to make absolutely sure that at least one of them is lucky?

4. In an isosceles triangle ABC with angle B = 108^{o} an angle bisector CD is drawn where D lies on AB. Then a perpendicular to line CD at point D is erected and it meets side AC at point E. Prove that AE = BD.

1. Find a tessellation of the plane with identical regular n-gons for n = 3, 4, 6.

2. Construct a tessellation of the plane with identical convex pentagons.

3. Construct a tessellation of the plane with identical n-gons for any n > 6.

4. Does there exist a tessellation of the plane with identical concave quadrangles?

5.^{*} Prove that there is no tessellation of the plane with identical convex n-gons for n > 6.

1. Three boys - Peter, Paul and John - solved altogether one hundred questions from the math textbook. Each one of the boys solved exactly 60 questions. We will call a question "easy" if it was solved by every one of the boys and "difficult" if it was solved by only one of them. Prove that the number of "difficult" questions exceeds the number of "easy" questions by 20.

2. In a country of Faraway Land there are 101 cities and some of them are connected by one-way roads so that no two cities are connected by more than one such road. It is known that there are exactly 40 roads coming into every city and exactly 40 roads going out of every city in the country. Prove that one can travel from an arbitrary city to any other using no more than three roads.

3. Numbers a, b, c belong to segment [0;1]. Prove the following
inequality

a/(1+bc) + b/(1+ac) + c/(1+ab) <= 2.

4. Nine volleyball teams had just finished a round-robin tournament. Is it true that there must be some two teams A and B such that every other team has lost to either A or B?

1. For any positive a, b, c prove that a/b + b/c + c/a >= 3.

1. In quadrangle ABCD diagonals meet at point O. It is known that AB = OD, AD = CO and < BAC = < BDA. Prove that ABCD is a trapezoid.

2. Prove that if x + y + z >= xyz then x^{2} +
y^{2} + z^{2} >= xyz.

3. A circle is divided into N sectors and there are N+1 frogs sitting in those sectors. Every second some two frogs sitting in the same sector jump into different adjacent sectors of the circle. Prove that at some moment the frogs will occupy at least half of all the sectors.

4. Three players have some monopoly money - hundred dollars each (notes could be of any value: e.g. 7 dollars or 22 dollars). It is known that each one of them could pay to any other any sum from 1 thru 25 dollars (perhaps getting back some change). Prove that altogether they can pay out any sum from 100 thru 200 dollars (in monopoly money, of course).

1. In a tit-tat-toe round-robin school tournament with several partcipants one point was awarded for every victory, zero points for a draw and a point was subtracted for a loss. One of the kids has 20 points and another has 7 points. Prove that there was at least one draw in the tournament.

2. Find all numbers *n* = 11..111 (ones only in decimal
representation) such that there exist a number *m* = 1000..001
(an arbitrary number of zeros between two ones) which is divisible by
*n*.

3. In a trapezoid one of its diagonals equals the sum of its
bases and the angle between diagonals is 60^{o}. Prove that
the trapezoid is isosceles.

4. A 10 x 10 table is filled in with numbers according to the
following rule: cell at the intersection of *i*-th row and
*j*-th column has number 1/(*i+j-1*) written in it. There are
10 chess rooks positioned on the cells of the table so that no rook is under
attack by any other. Prove that the sum of the numbers written under
the rooks is at least 1.

1. If a <= b and x <= y then ay+bx <= ax+by.

2. If a+b+c = 0 then ab+bc+ca <= 0.

1. Numbers 1 thru 100 are written in a row in ascending order. It is permitted to erase several neighboring numbers replacing them with the number of the numbers erased. Is it possible after a few such operations to end up with two numbers 50, 51 ?

2. There are 1993 triangles positioned on the plane in such a way that every one of them contains at least 4 vertices of other triangles. Prove that some three triangles have a common point.

3. We will call a person secretive if he or she has no more than ten acquaintances. We will then call a person odd if all of his/her acquaintances are secretive. Prove that the number of odd people is less than or equal to the number of secretive people.

4. Natural numbers x and y are such that the sum of two
fractions (x^{2}-1)/(y+1) and (y^{2}-1)/(x+1)
is an integer. Prove that both fractions are integers.

1. Solve Diophantine equation x^{2} = y^{2} + 14.

2. Solve Diophantine equation x^{2} + y^{2} = x + y + 2.

1. Four cars A, B, C and D start simultaneously from the same point at the circular racetrack - A and B go clockwise and C and D - counterclockwise. Cars go with constant but different speeds. It is known that A meets C for the first time at the same moment when B meets D for the first time. Prove that A and B will meet (meaning one of them will catch up with another) for the first time at the same moment when C and D will.

2. In a convex quadrangle ABCD angles A and B are equal, BC = 1 and AD = 3. Prove that length of CD is greater than 2.

3. Some correct problem's statement in a problembook reads: "There are N numbers such that the sum of any ten of them is greater than the sum of the rest. Prove that all numbers are positive". There should have been some specific number printed instead of N. What could that number be? Find all answers.

4. For any natural number X let's denote by X' a number which is written by the same digits but in a reverse order and by P(X) the product of X's digits. Find all numbers X without zeros in their decimal representation such that XX' = 1000 + P(X).

1. Prove that for any natural number N the product of its digits is always less than or equal to N.

2. For any positive numbers x and y prove the inequality

x/y + y/x >= 2.

3. For any non-zero numbers x and y prove the inequality

x^{6}/y^{2}+y^{6}/x^{2} >=
x^{4}+y^{4}.

1. Two players play the following game. Number 1234 is written on a blackboard. A move consists of subtracting any non-zero digit of the number from it and replacing the number with the difference. A player who cannot make a move loses. If both players play errorless game who wins: the player who makes the first move or his opponent?

2. A toy railroad consists of several parts of two types A and B:
parts are 90^{o} arcs of a railroad track which differ only in
a prescribed direction printed on every arc. Initially one could
assemble a closed track from the arcs provided. Later one of the arcs
of type A was lost and replaced with the one of type B. Prove that
one cannot assemble a closed railroad now. (Note: direction of the
train's movement must coincide with the directions on all the arcs.)

3. In a convex pentagon ABCDE diagonals BE and BD meet diagonal AC at points K and M respectively. It is known that AE = EK = KB and AK = MC. Prove that EM = BC.

4. Natural numbers a, b, c and d are all divisible by natural number ab-cd. Prove that ab-cd = 1.

1. Solve Diophantine equation x^{2}+y^{2}=4z-1.

2. Solve Diophantine equation x^{2}-7y = 10 (or = 4).

3. Solve Diophantine equation 15x^{2}-7y^{2} = 0 (or = 9).

1. At a black market in the village of Perestroika one can always exchange any two ration coupons for any three other coupons and vice versa. Pete has 100 sugar coupons and he wants to exchange them for 100 salt coupons. Can he do that giving away in the process exactly 1991 coupons?

2. Vertices of a 3-dimensional closed broken line with 8 segments coincide with the vertices of a unit cube. Prove that one of its segments is an edge of the cube.

3. A game-show host and 30 players play the following game. Each one of them (including the host) writes down numbers 1 thru 30 in some arbitrary order. Then these number sequences are being compared and a player gets one point for every time he has same number at the same position as the host's sequence. It is known that all thirty players have different scores. Prove that one of their sequences is identical to that of the host.

4. In an acute-angled triangle ABC altitude AH, median BM and angle bisector CK are drawn. AH meets BM at point L, BM meets CK at point P, CK meets AH at point N and it is known that points L, N and P are different. Prove that triangle LNP cannot be a regular one.

1. Two regular tetrahedrons with their vertices in two disjoint sets of 4 vertices of a cube produce a regular polytope as their intersection. What polytope is that?

2. Solve a Diophantine equation: x^{3}+ 21y^{2}+5=0.

1. Two hundred points are positioned somehow inside segment AB so that their set is symmetric with respect to the midpoint of AB. Some one hundred points are colored blue and the rest are colored red. Prove that the sum of distances from A to all blue points is equal to the sum of distances from B to all red points.

2. A boy and a girl play the following game where the girl makes the first move. There are 2n candies distributed somehow between n boxes. A move consists of simply taking one of the remaining candies and eating it. Prove that the boy can play in such a way that the two last candies will be taken from the same box.

3. Four rubles are paid by several coins - all of them of value 1, 2, 5 or 10 kopecks. Prove that out of the same set of coins one can always pay exactly three rubles.

4. Prove that for any natural n number (10^{n}-1)/81 -
n/9 is always an integer.

5. For a natural number m > 3 sum S of all the natural numbers x
not greater than m and such that x^{2}-x+1 is divisible by m
is calculated. Prove that S is divisible by m+1 (if there are no such
numbers x then S is naturally zero).

6. Prove that if x^{2} + xy + xz < 0 then y^{2}
> 4xz.

7. There is a set of 2000 points and a unit circumference given on the plane. Prove that one can find a point on a circumference such that the sum of distances from that point to all the 2000 points of the set is greater than 2000.

8. Positive numbers a and b are such that ((1+ab)/(a+b))^{2} <
1. Prove that one of the numbers a and b is greater than 1 and
another one is less than 1.

9. Several non-zero numbers are written on a blackboard. The following operation is then carried out a few times: some two numbers a and b are erased and replaced by a + b/2 and b - a/2. Prove that the resulting set of numbers cannot coincide with the original one.

10. A castle has 64 rooms arranged in a 8 x 8 square pattern such that any two neighboring rooms are connected with a door. Each day a painter living in the castle starts in a room where he slept and moves within the castle repainting fllors of every room he visits: black into white and vice versa. Initially all the floors are black. Is it possible for him to achieve after several days a chessboard coloring of the castle floors?

11. An infinite set A of natural numbers has at least one member in any hundred of consecutive natural numbers. Prove that it is possible to find four members of this set a, b, c and d such that a+b = c+d.

12. In a acute-angled triangle ABC altitude CH and median BK are drawn. It is known that BK = CH and angles KBC and HCB are equal. Prove that ABC is equilateral.

13. A special geometric instrument can perform the two following operations: a) to construct a straight line thru two given points; b) for a straight line and a point on it to erect a perpendicular to the given line thru the given point. Prove that using only that instrument given a straight line and a point outside of it one can build a perpendicular to the given line thru the given point.

Back to **MathCircle Homepage**

Back to **DF-ES Homepage**