times.
This location was visited times.
1. Eleven girls and n boys went mushroom gathering and collected n2+9n+2 mushrooms altogether. Given that each one of them has found the same amount of mushrooms find if the number of boys was greater than the number of girls.
2. Numbers a, b, c, ... (n numbers in the collection) are such that
every one of them is less than their sum S divided by n-1. Prove that
a) they are all positive;
b) a + b > c;
c) a + b >= S/(n-1).
3. Point is selected on each side of a parallelogramm. Then points lying on adjacent sides are connected so that four small triangles are formed. Prove that the circumcenters of these triangles lie on the vertices of a parallelogramm.
4. An ant walks along the wire skeleton of a cube without ever doing a 180-degree turn. Is it possible that by some moment he will have visited one vertex of the cube 25 times while having visited each of all other vertices exactly 20 times?
1. In trapezoid ABCD (BC || AD) M is intersection of bisectors of angles A and B, N is intersection of bisectors of angles C and D. Knowing lengths of sides of the trapezoid, find distance between M and N.
2. Prove that number 993 x 1023 x 1049 + 980 x 1006 x 1036 is composite (use of calculators is absolutely and utterly prohibited).
3. For any two finite sets of points A and B on the plane let's
denote by dH(A,B) maximum of d1 and
d2, where d1 is maximum of distances from
points of A to set B, and d2 is maximum of distances
from points of B to set A. Prove that for any three finite sets X, Y. Z
the following inequality (triangle's inequality) holds true:
dH(X,Y)+dH(Y,Z) >= dH(X,Z)
4. Three runners A, B and C ran straight (ie, not in laps) 1000m distance at a competition. C was the last to start but during the run he passed somebody or has been passed exactly six times. It is known also that B started later than A, and that A has been passed or passed someone exactly five times. If B finished before A then what was the finishing order of the runners?
1. What are the three axioms of distance? Consider set of all people on Earth and define distance between two different people as 1 if they are currently in the same country and 2 if they aren't (zero for two identical people, of course). Does this function satisfy all axioms (non-negativity and zero only if elements are identical; simmetry; triangle inequality)?
1. Sum of three natural (not necessarily different) numbers is 100. We calculate all three pairwise non-negative differences between these numbers. What is the maximum possible value for the sum of these three differences?
2. In convex quadrangle ABCD AB=BC, CD=DA. Points K and L belong to AB and BC respectively and BK = 2AK, BL = 2CL. Points M and N are middles of segments CD and DA respectively. Prove that KM equals LN.
3. Least common multiple of some two natural numbers is 16 times greater than their greatest common divisor. Prove that one of these numbers is divisible by the other.
4. A pawn stands on the leftmost box of a 1x40 board. Two players in turn move the pawn to the left or to the right by the number of boxes which hasn't already been used during the previous moves. The player who cannot make a move loses. Who wins in the errorless game?
1. Is it possible to sort an array of 4 numbers with just 4 comparison operations?
2. Merge two sorted quadruples into a sorted 8-tuple using the least number of comparison operations.
1. Ann, Bob and Chet compose words from several given letters. They all have composed different number of words - Ann has most of them all, and Chet has the least amount. Then they counted the points in the following way - if a word is common for all three then it is not counted; it is worth 1 point if present in two lists and 2 points if present in just one list. Is it possible that Chet got the most points while Ann has the least?
2. Chess king traversed the entire chessboard having visited each field exactly once and finished on the initial square. Prove that it made an even number of diagonal moves.
3. Points A, B, C and D lie on the sides of angle with vertex O so that A lies between O and B, C lies between O and D. A straight line passing through midpoints of AD and BC meets the sides of the angle in points M and N (M belongs to "AB" side, and N belongs to "CD" side). Prove that OM/ON = AB/CD.
4. Does there exist a set of ten natural numbers such that none of these numbers is divisible by any other from the set but square of every number is?
1. Prove that it is impossible to merge two sorted quadruples into one sorted 8-tuple using less than 7 comparison operations.
2. Show how to do that using no more than 9 comparisons.
1. Is it possible to merge two sorted quadruples into one sorted 8-tuple using 8 comparison operations?
2. Each day eight people sit at the same round table for breakfast. Is it possible that after seven days each two of them have been neighbors at the table exactly once?
3. Seventeen two-digit natural numbers are written on a blackboard. One of them was raised to the 100th power and the result turned out to be divisible by all the other numbers on the board. Prove that it is actually divisible by the product of all the other numbers.
4. Two equilateral triangles ABC and ACO are drawn on the plane, as well as a circumference with center O passing through points A and C. Prove that for any point M on this circumference the following equality holds true: MA2 + MC2 = MB2.
1. Prove that one can merge two sorted n-tuples into one sorted 2n-tuple using no more than 2n-1 comparisons.
2. Prove that it is possible to sort an array of 2n numbers using no more than 2n(n-1)+1 comparisons ( Merge sorting algorithm)
1. On each of two identical cubes five vertices have been marked. Prove that it is possible to overlap these two cubes in space so that there are at least four pairs of coinciding marked vertices.
2. Points C1, A1 and B1 are chosen on sides AB, BC and CA of triangle ABC respectively. Then points C2, A2 and B2 were chosen on segments C1B, A1C and B1A respectively. It is known that segments C1A2, B1C2 and A1B2 are parallel to the sides of ABC and pass thru one point. Prove that areas of triangles A1B1C1 and A2B2C2 are equal.
3. There are one hundred dumbbells weighing 1, 2, ..., and 100 kg respectively. Is it possible to split them into ten groups so that all ten groups have different masses and for any two groups the lighter group has more dumbbells than the heavier one?
4. Given 1996 fractions 1/1996, 2/1995, 3/1994, ..., 1995/2 and 1996/1 can one select three of them such that their product equals 1?
1. If 1997 = 1 + 1996 is replaced in Session 123 HW Question 4 by another odd not-prime number is the answer "No" still correct?
1. Prove that there are infinitely many natural numbers n not ending with zero such that S(n) = S(n2).
2. A computer panel consists of 100 backlit buttons arranged in a square 10 x 10 table. Pushing each button will change the state of all the buttons which happen to be in the same row or in the same column with the one pushed. Initially all the buttons are lit. What is the minimum number of buttons one must press to make the panel absolutely dark?
3. A broken line ABCDE is such that all its vertices lie on one circumference so that when read clockwise they go in the order ABDEC. It is known that angles ABC, BCD and CDE are all equal to 45o. Prove that AB2 + CD2 = BC2 + DE2.
4. Let us consider a full domino set where values of numbers on the domino pieces vary from 0 to N. What is the maximum length of a domino chain that can be laid out according to the rules?
1. How many edges must be removed from a complete graph with n vertices to satisfy the conditions of Euler theorem about existence of a path passing through all the edges exactly once?
1. It is permitted to multiply a given natural number by two and/or also to reshuffle its digits in any order (but not to put a zero at the first place). Prove that one cannot turn 1 into 811 using these operations.
2. A mushroom is called bad if there are more than 11 worms living inside of it. A worm is called thin if it has eaten no more than 1/5 of the mushroom it inhabits. Given that one quarter of all mushroom in a forest are bad, prove that no less than one third of all their worms are thin.
3. Points E and F lie on sides AB and BC of rhombus ABCD and AE = 5 BE, BF = 5 CF. Find angle BAD if it is known that triangle DEF is equilateral.
4. Find all natural solutions of equation 105x + 211y = 106z.
1. The following algorithm is being performed to sort an array of n different numbers: number in the first position is compared with the number in the second position and they are transposed if they are not in ascending order; then the same is done for the numbers in positions 2 and 3, then 3 and 4 etc. After this cycle is finished, it is repeated then repeated again and again until n-1 cycles are performed. Is it true that in the end all numbers will be arranged in ascending order?
2. In a quadrangle ABCD points E, F and G are midpoints of sides AB, BC and AD respectively. It is known that GE is perpendicular to AB, GF is perpendicular to BC and angle ABC equals 96o. Find angle ACD.
3. Eleven vertical and eleven horizontal segments are drawn on the plane. Prove that it is impossible for every horizontal segment to intersect exactly ten vertical segments and for every vertical segment to intersect exactly ten horizontal segments.
4. Find all solutions in natural numbers for equation LCM(x, y2) + LCM(x2, y) = 1996.
1. Is true that if x and y are natural numbers and x = ad, y = bd where d is their GCD then LCM(x, y2) = ab2d2?
1. Do there exist natural numbers a, b, and c such that (a+b)(b+c)(c+a) = 4242?
2. A triangle with sides a, b, c whose perimeter equals 1 is given. Prove the inequality: (1+a)/(1-2a) + (1+b)/(1-2b) + (1+c)/(1-2c) > 6.
3. There are ten electric poles. An electrician is given the following assignment: to connect the poles with cables so that each cable connects exactly two poles, no two poles are connected with more than one cable and, most importantly, for any four poles there must be exactly three cables linking them together. Prove that the assigned task is impossible.
4. A rectangle with integer sides is dissected into dominoes 1 x 2. Let A denote the number of 2 x 2 squares within the rectangle such that they consist of two dominoes, and let B denote the number of such squares that consist of boxes from four different dominoes. Prove that A > B.
1. In HW Question 4: does there exist any self-replicating configuration of sandwich stacks other than {1, 2, ..., n}?
1. A deck of playing cards is arranged in such a way that suits alternate as follows: spades, clubs, hearts, diamonds, spades, clubs, hearts, diamonds and so on. A portion of the deck from the top was taken and "spliced" into the rest of the deck so that order of every "half" is preserved. After that cards are dealt in series of fours. Prove that in every quadruple all suits are different.
2. Prove that equation m! x n! = k! has infinitely many solutions such that m, n, k are natural numbers greater than 1.
3. Regular 100-gon is dissected into parallelograms. Prove that at least twenty-five of them are rectangles.
4. There are several stacks of sandwiches (altogether n(n+1)/2 of them, n is some given natural number). The following operation is performed each minute: one sandwich is taken from the top of each stack and all the gathered sandwiches are piled into one new stack. Prove that eventually there will be n stacks with 1, 2, ..., and n sandwiches in them.
1. List all possible stack configurations for Session 128 HW Question 4 for N = 1, 2, 3, 4, 5 (N - total number of sandwiches) and connect them with the arrows showing how the configurations change.
2. What is the minimum number of parallelograms one can dissect a regular 2n-gon into?
1. Is it possible to find four different natural numbers such that the sum of any two of them is a power of five?
2. Does there exist a rectangular triangle which can be dissected into one regular triangle and one isosceles triangle?
3. A few municipal employees have equal salaries. After receiving their money an employee would from time to time perform the following procedure: he/she takes a part of his/her money and gives it to the rest of his/her colleagues so that each one of them gets equal share. After several days it turned out that one of the employees had 24 cents and another one - 17 cents. How many employees were there in that group?
4. There are 3n people living in the city of Buddyville and it is known that any two of them have at least one common acquaintance. Prove that it is possible to select n people such that each one of the rest of Buddyvillians is acquainted with at least one of the selected people.
1. Is it possible to place all integers from -7 thru 7 (including zero) around a circle so that for every number the product of its neighbors is non-negative?
2. A rectangular sheet of graphed paper is such that 360 squares 2x2 can be cut out from it (along the gridlines). Prove that it is possible to cut out 200 rectangles 1x7 from the same sheet.
3. Numbers x, y, z, t satisfy the inequality
(x+y+z+t)2 >= 4(x2+y2+z2+t2)
Prove that there exists a real number A such that
(x-A)(y-A)+(z-A)(t-A) = 0.
4. Triangular table filled with numbers is formed as follows: the first row has N zeros, the second row (which, as well as every row after that, is shifted half-position to the right relatively to the previous row) has N-1 ones, the third row is filled with N-2 arbitrary natural numbers etc. so that for any two neghboring numbers a and b in any row and their neighbors c and d from above and below it holds true that ab - cd = 1. Prove that all the numbers in the table are integers.
Example:
0 0 0 0 0
1 1 1 1
4 2 5
7 9
31
1. In Session 128 HW Question 4 prove (induction by N) that for any numbers N and n such that N <= (n+1)n/2 if we start with N sandwiches then eventually the stack diagram will be a sub-diagram of triangular diagram with n stacks.
1. Write a program that tries to find a triangular number table of order 10 (constructed following the rules from Session 130 HW Question 4) whose numbers are all natural (except for the ten zeros in the 0th row) and such that it contains as few different numbers as possible (we know there is an example with only 10 different numbers - fill kth row with numbers k for every k = 2,...9).
2. Natural numbers 1 thru 100 are arranged somehow around a circumference. For any three consecutive numbers their sum is calculated. Prove that some two of these sums differ by at least 3.
3. Points K and L lie on sides AB and AC of an acute-angled triangle ABC respectively and KL // BC. Point M is intersection of perpendiculars erected at K and L to AB and AC respectively. Prove that A, M and circumcenter O are collinear (ie, belong to one straight line).
4. Value of quadratic binomial ax2+2bx+c is negative for any real x. Prove that value of quadratic binomial a2x2+2b2x+c2 is positive for any real x.
1. Using similar triangles and common sense (size of a regular cinema hall, size of the screen etc), calculate approximately size of one frame on a cinema reel.
2. Again, using common sense and the fact that a human eye needs about 1/25 of a second to fully process a picture calculate speed of a car necessary to create a visual "standing wave" effect in 5-spike hubcap.
1. Cube 3x3x3 is formed by 27 unit cubes. How many of the smaller cubes can be taken out so that when looking at the big cube from any side one would still always see a 3x3 square without any holes?
2. There are 6930 digits "1" written in a row. Then each 5th of them was "reversed" (that is, its sign was changed); after that, every 7th was reversed; after that each 9th was reversed and finally each 22nd was reversed. Find the sum of all numbers.
3. None of three odd natural numbers a, b and c are perfect squares. Can number abbcca be a perfect square?
4. CEO of a company likes to bundle several orders in one announcement. However, level of discipline in the company is not very high and some of his orders are not complied with immmediately which requires repeating them sometimes more than once. During the last year he issued exactly 100 announcements covering altogether less than 100 orders. It is known that it is enough to read any 50 announcements to learn about all his orders. Prove that some 49 of his announcements contain all his orders.
1. N numbers "1" are written in a row, where N = a1a2...an, and a1, a2... are different natural numbers. After that each a1th number is "reversed" (see Session 132 HW Question 2), then each a2th number is reversed etc. What is the sum of all numbers after all n reversal operations are performed?
2. Find three smallest odd natural numbers which are not perfect squares but their product is.
1. Find all natural n such that 5n+3n is divisible by 5n-1+3n-1.
2. In triangle ABC point M is middle of BC, r1 and r2 are radii of incircles for triangles ABM and ACM respectively. Prove that r1 < 2r2. Hint: use standard formula for raduis of incircle.
3. A corporal made an assignment sheet for his squad. There are 50 soldiers in the squad and the sheet covers 30 days. Every day exactly four soldiers have some duties to perform and for every soldier break between his consecutive assignments must be at least 5 days. Then squad commander added one special daily assignment. Prove that it is possible to add an extra soldier to each day schedule so that 5-day rule will be still honored.
4. Number 1/1997 is represented as a periodic decimal fraction. Prove that there are no more than 200 sevens in the basic period of this fraction.
1. Remember once again and prove formula for radius of incircle of a triangle. (r = 2S/p; S - area, p - perimeter).
2. a) Prove that for any natural n period of decimal
representation of 1/n is shorter than n.
b) Find smallest prime number p such that period of decimal
representation of 1/p is shorter than p-1.
1. One ruble coin weighs 6 g, two ruble coin weighs 17 g, and five ruble coin weighs 30 g. In a bank branch you can exchange any set of coins for any other of the same total weight. If one starts with 1998 rubles is it possible for her to get exactly 2099 rubles (for the purpose of this problem assume existence of only 1, 2, and 5 ruble coins)?
2. Diagonals of quadrangle ABCD intersect at point E. It is known that AB = CE, BE = AD, and angles AED and BAD are equal. Prove that BC > AD.
3. There are exactly 1999 people in Transsilvania. Three of them are vampires but only few know who they are. A traveller asked all of the transsilvanians to name two people who, in their opinion, are vampires. Each vampire truthfully named the other two while other people could answer anything. Prove that using this data the traveller can find himself a guide who is not a vampire.
4. Square is dissected into several rectangles with equal perimeters. Given that one of its diagonals intersects all the rectangles prove that the same is true for the other diagonal.
1. Find a formula for (an) where a0 = 0, a1 = 1 and an+2 = an+1-an.
2. Find general solution for recursive series (an) which satisfies formula an+2 = pan+1+qan.
1. Sequence of numbers (an) is such that a0 = 21999 and an=999an-1/ (an-12+1) for any natural n. Prove that a198 < 0.1.
2. Is it possible to place nine different two-digit numbers into the boxes of a 3x3 table so that product of numbers in any two neighboring boxes is divisible by 2520?
3. There were 60 passengers on a plane; some of them were soldiers, some were engineers, some were pretending to be soldiers, some were pretending to be engineers, and others were regular passengers. Total number of real soldiers and real engineers is four times greater than the total number of fake soldiers and fake engineers. Total number of soldiers (fake and real together) is seven times greater than total number of engineers (fake and real together). How many regular passengers were there?
4. In triangle ABC angle BAC = 60o. Point K is intersection of median CM and altitude BN. Also CK = 6, KM = 1. Find angles of ABC.
This has been the last session of Mat.Kruzhok (MathCircle)
Thank you and good luck!
Back to MathCircle Homepage
Back to DF-ES Homepage
