times.
This location was visited times.
1. Prove that 39 is the correct answer to Summer Homework question 5b.
2. Prove that 300..001 cannot be a perfect square.
1. In Summer Homework Question 7 what are the values of x and y for which the equality is achieved?
2.In Summer Homework Question 13 what are the values of N such that if there are N people sitting at the table and announcing the same statements then all of them must be knaves?
1. Find the smallest prime p such that Fibonacci number Fp is composite. Use of computers is permitted.
1. Prove that arithmetic mean of two non-negative numbers is greater than or equal to their geometric mean.
2. Prove the same for four non-negative numbers.
3. Prove that 90..01 cannot be a perfect square.
1. In a convex 13-gon all its diagonals are drawn so they divide it into a number of smaller polygons. What is the maximum number of vertices such a part can have?
2. A six-digit phone number is given. How many seven-digit numbers are there such that the given number can be obtained from them by crossing out one of the digits?
3. Thirty chairs stand in a row, some of them are occupied. Every
minute somebody comes and sits down in one of the chairs, and
simultaneously one of his/her neighbors (if any) stands up
and leaves. What is the maximum possible number of occupied chairs
at some moment of the game if initially
a) all the chairs are empty;
b) ten out of the thirty are occupied?
4. If 0 <= x, y <= 1 prove that x/(1+y) + y/(1+x) <= 1.
1. Prove the AM-GM inequality (Arithmetic Mean >= Geometric Mean) for any N=2k non-negative numbers.
2. Prove the AM-GM inequality for any three non-negative numbers.
3. Prove the AM-GM inequality for any N non-negative numbers.
4. Prove that if all the sides of a quadrilateral have length no greater than 1 then its area is less than or equal to 1.
1. See Session 37 HW Question 1 for convex 14-gon.
2. Prove the following inequality
1/2 - 1/3 + 1/4 - 1/5 + ... -1/99 + 1/100 > 1/5.
3. Squares of some two consecutive natural numbers differ only by the order of their last two digits. Find those numbers.
4. For any natural n prove that F2n+1 = FnFn+2 + (-1)n where (Fn) is the Fibonacci series.
1. Prove that set of all natural numbers N and the set of even natural numbers E have the same cardinality.
2. Prove that the set of all integers Z is countable (that is, of the same cardinality as N).
3. Split N into ten countable subsets.
4. Split N into infinite number of countable subsets.
5. Prove that the set of all rational numbers Q is countable as well.
1. Prove that the circles built on all four sides of a convex quadrilateral as on diameters completely cover the quadrilateral.
2. Ali-Baba is trying to get into the treasure cave. There is a closed barrel standing in front of the cave with 4 holes uniformly positioned in its side. There is a jar with a herring behind every hole and the genie of the cave will grant access to the treasure if and only if all the herrings are positioned identically - either all heads up or all heads down. Ali-Baba can put his hands in any two holes and upon examination of the two corresponding herrings decide whether he wants to change their "direction". After every such "move" the barrel spins and stops so that there is no way to determine which holes were examined previously. How should Ali-Baba act to get inside cave?
3. In a country every two cities are connected with a separate one-way road. Prove that a traveler can start from some city and drive abiding the rules of the road visiting each city in the country exactly once.
4. In a regular 2n-gon all its diagonals are drawn dissecting it into several smaller polygons. What is the maximum number of sides that such a part can have?
1. What if in Session 39 HW Question 1 the quadrilateral is not convex?
2. Prove that segment [0;1] is not countable, that is, for any series of numbers (ak) there is a number 0 < x < 1 such that x is not equal to any of ak.
3. Write a computer program that draws a regular 2n-gon with all its diagonals. Use this program to test your conjectures for Session 39 HW Question 4.
1. Sort numbers 5100, 691, 790, 885 in accordance with their absolute value.
2. Prove the inequality
1+1/sqrt(2)+1/sqrt(3)
+...+1/sqrt(n) < 2sqrt(n),
where
sqrt(x) denotes a square root of x.
3. For natural number m numbers a1, ...,
ap constitute all of its natural divisors, and numbers
b1, ..., bq form the corresponding set for
natural number n. It is known that the two following
equalities hold true:
a1 + ... + ap = b1 + ... + bq
1/a1 + ... +
1/ap =
1/b1 + ... +
1/bq
Prove that m = n.
4. A traveler arrives to a small town and wants to stay in a
hotel. He doesn't know exactly how many days he will stay and of all means of payment he only has with him a small golden chain with N rings. The hotel manager agrees to accept the rings as payment at the rate one ring per day but insists on being paid on daily basis. The traveler decides to cut some rings of the chain in such a way that he is able to settle his bill every day (the manager can give him back some of the rings he will have received before). What is the absolute minimum number of cuts (with every cut some miniscule amount of gold is lost and everybody wants to avoid that) necessary for that purpose if
a) N = 7 ?
b) N = 15 ?
c) N = 73 ?
1. Find examples of two different natural numbers such that
2. Prove that a non-decreasing series (ak) of natural numbers is such that every natural number can be represented as a sum of several members of the series with different indices if and only if a1 = 1 and for any k > 0 the following inequality holds true ak+1 <= a1 + ... + ak + 1.
1. For a natural number n prove that S(n(n-1)) cannot equal S((n+1)2) where S(x) denotes the "sum of the digits" function.
2. Numismatist Theo keeps his entire coin collection in a very thin box with dimensions 30cm x 70cm, and all of his coins have diameter no greater than 10cm. One day his old trusty box broke and he was given another one with dimensions 40cm x 60cm. Prove that he will be able to put his collection into the new box as well (again, of course, without overlaps).
3. In a trapezoid one of the diagonals equals the sum of the bases. It is known also that the angle between diagonals is 60 degrees. Prove that the trapezoid is isosceles.
4. There are only nine items for sale in a convenience store of a small town of Inflationville, and on January 1, 2001 all of them were priced at 1 dollar. Starting January 2, the price for each one of them either doubled or tripled every day until February 1, 2001 when it was discovered that all nine prices were different. Prove that one of the items' price is now at least 25 times greater than some other price in the store.
1. Prove that for any natural n the sum n3 + (n+1)3 + (n+2)3 is divisible by 9.
2. Prove that for any natural n the sum 11n+2 + 122n+1 is divisible by 133.
3. Prove that for any natural n 23n + 1 is divisible by 3n+1.
4. Prove that for any natural n and positive number x the inequality (1+x)n > 1+nx holds true.
1. A, B, C, D, E, F and G are natives of the island of knights and knaves (knights always tell the truth and knaves always lie). A says that B claims that C told him that D said that E insisted that F denied that G is a knight. C also says that D is a knave. Given that A is a knave how many knaves can there be in that group? (here "says", "claims" etc means "can say", "can claim" etc.)
2. There are more than 3 players in a round-robin chess tournament where everyone plays each other the same amount of times (perhaps, more than one). A player gets 1 point for a win, 1/2 point for a draw and 0 points for a loss. The tournament is scheduled to last 26 days (every day players split into pairs and every pair plays one game). After the 13th day one of the players realized that she had an odd number of points and all the others had an even number of points. How many players were participating in the tournament?
3. Prove the double inequality 479 < 2100 + 3100 < 480.
4. There are several (possibly different) squares. Prove that it is possible to dissect them into some finite number of parts all of which can then be arranged on the plane without overlapping to form one big square.
1. Prove that for any natural n there exists a scheme for a round-robin tournament with 2n players where every participant plays each other exactly once and on every day of the tournament exactly n pairs play each other.
1. There are 40 passengers on the bus and altogether they have 49 coins of denomination 10, 15 and 20 kopecks. Bus fare is 5 kopecks. Prove that it is impossible for everyone to pay exact fare (meaning that the driver gets exactly 40 x 5 = 2 roubles and each of the passengers parts with exactly 5 kopecks of his/her own money).
2. A tourist stands on a straight paved road in the desert. He can travel the road at speed 6 kmph and the desert at speed 3 kmph. Find the set of points he can reach within exactly one hour of time.
3. In a group of people each one has exactly one friend and exactly one enemy ("being a friend" and "being an enemy" are symmetric relationships, e.g., if A is a friend of B then B is a friend of A and so on). Prove that the group can be split into two subgroups such that everyone has neither their friend nor their enemy within the same subgroup.
4. Four dumbbells of different weights are given. Sort them by weight using no more than 5 weighings on regular two-cup scales.
1. In Session 43 HW Question 1 could it be possible to pay the driver if there were exactly 50 coins?
2. If we need to sort in ascending order N different weights
using regular 2-cup scales, prove that
a) N(N-1)/2 weighings is enough;
b) N-2 weighings is never enough;
c) For N = 2k prove that Nk weighings is enough.
Hint: prove that if W(n) is a function of number of weighings necessary to sort n weights then W(2n) <= 2W(n)+2n.
1. There are two convex polygons on the plane: one with m vertices and another with n vertices. It is known that no vertex lies on a side of another polygon. What is the maximum number of parts these two polygons can divide the plane into?
2. Twelve black and white chips are positioned in the vertices of a regular duodecagon. Prove that there are three chips of the same color that lie in vertices which form an isosceles triangle.
3. Solve simultaneous equations:
x2+xy+y2=7
y2+yz+z2=21
z2+zx+x2=28
4. Every two cities in a country are connected with either a highway or a direct airline flight. Prove that one of these means of transportation (travel by car or air flight) connects all the cities, i.e. it is possible to travel from any city in the country to any other using only that particular type of transportation.
1. In Session 44 HW Question 1 prove that the correct answer (2*min(m,n)+2) can be always attained.
2. In Session 44 HW Question 4: if there are three types of transportation is it still true?
1. Prove that if an even number can be represented as a sum of two perfect squares then its half can be represented this way as well.
2. A convex quadrilateral is dissected into four triangles of equal perimeter by its diagonals. Prove that it is a rhombus.
3. Prove that in a connected graph you can always delete one of the vertices (with all its adjacent edges) so that the remaining graph is still connected.
4. Prove that the three following statements are equivalent:
a) Polygon P is convex.
b) Each diagonal of P lies completely within P.
c) Each angle of P has value less than 180 degrees.
5. Several natural numbers are arranged around a circumference. Every minute we perform the following operation: between any two neighboring numbers their G.C.D. is written, and then we erase all the "old" numbers. Prove that eventually all the numbers on the circumference will be equal.
1. Prove that every connected graph contains a spanning tree.
2. Prove that every tree has a pendant vertex.
3. Prove that sum of the angles of any N-gon is (N-2)180o.
4. a) Prove that in any N-gon P with N > 3 there is a diagonal lying completely within P.
b) Is it true that for any vertex V of P there is such a diagonal going out of V?
1. In a round-robin chess tournament with 20 players a participant who took 19-th place (not tied with any other player) had 9.5 points. How many points could all the other players have had?
2. Some natural number a is divided by all natural numbers less than itself. It is known that the sum of all different(!) remainders of those operations equals a. Find all such numbers.
3. In a convex polygon all angles are obtuse. Prove that the sum of its diagonals is greater than its perimeter.
4. Several points on the plane are placed in such a way that a triangle with vertices on any three of these points has area less than or equal to 1. Prove that all the points can be covered by some triangle with area 4.
1. In Session 46 HW Question 3 prove that condition that all angles are obtuse can be replaced by a requirement that the number of vertices of the polygon is greater than 4.
1. A crazy traveler goes from his home city A to the city B which is farthest possible from A, then he goes to city C which is, in turn, the farthest possible from B et cetera. Given that city C is not A and that all distances between cities in the country are different prove that the traveler will never return to his homecity.
2. There are 300 boots in a warehouse: one hundred of them have size 9, one hundred have size 10, and the remaining hundred - size 11. It is also known that there are exactly 150 left and 150 right boots. Prove that one can always find at least 50 proper pairs of boots in the warehouse.
3. Find some 100 natural numbers such that their sum equals their product. (Also try to come up with a description of such sets of numbers).
4. There are 1985 vertices in a graph and they are colored either red, green or blue so that no edge of the graph connects two vertices of one color. Given that every vertex of the graph has the same degree prove that there exists a red vertex connected to some blue vertex and to some green vertex.
1. In Session 47 HW Question 2 find an example of a warehouse with exactly 50 proper pairs of boots.
2. Write a program that finds all the sets of 100 natural numbers such that their product equals their sum.
1. What number must be written instead of * if it is known that the textbook problem "There are n straight lines on the plane with exactly * points of intersection. Find n" has exactly one solution?
2. A sequence of k numbers is written on a blackboard. Every second one of the numbers (not the last one) is replaced with the sum of all the numbers positioned to the right of it. Prove that sooner or later the sequence will repeat.
3. In a 1000-digit integer all digits but one are fives. Prove that this number cannot be a perfect square.
4. There are 35 piles of peanuts on the table and there is an inexhaustible supply of peanuts. You can select any 23 piles and add one peanut to each one of them. Prove that you can make all the piles equal using the described operations.
5. A wolf is sitting in the center of a square field, and four guarddogs are sitting in its corners. Wolf's objective is to escape the field, and the dogs' goal is to prevent that. Wolf can move anywhere but dogs can only run along the contour of the field; however, their maximum speed exceeds the maximum speed of the wolf by 50%. It is also known that wolf can easily dispatch of one dog but will fail to two dogs. Prove that the dogs can achieve their goal.
6. In some country cities are connected by air routes in such a way that there are no more than three of them going out of every city. It is also known that one can fly from any city to each other with no more than one stopover. What is the maximum possible number of cities in this country?
7. In a round-robin volleyball tournament none of the twelve participating teams gained exactly 7 points (a team gets 1 point for a win and 0 for a loss). Prove that there are three teams A, B and C such that A defeated B, B defeated C, and C defeated A.
8. An isosceles triangle ABC (AB = AC) with angle A = 20o is given. Prove that 2BC < AB < 3BC.
9. Ten white and twenty black chips are uniformly positioned around the circle. The following operation is permitted: any two chips separated by exactly three other chips can be transposed. Two chip arrangements are called equivalent if one can be obtained from another using several such operations. Find the maximum number of non-equivalent arrangements.
10. Point K is given inside square ABCD. Perpendiculars to BK, CK, DK and AK are drawn through A, B, C and D respectively. Prove that all four perpendiculars meet at the same point.
Back to MathCircle Homepage
Back to DF-ES Homepage
