times.
This location was visited times.
1. The answer is no. Show that the number of black boxes in the
table always remains odd and therefore cannot become zero.
2. Assume without loss of generality that a <= b <= c <= d and then
obviously a+b=2, a+c=4, a+d=b+c=9, d=14, c+d=16. The only solution to this simultaneous equation is a=-1.5, b=3.5, c=5.5, d=10.5.
3. Any number from three thru six.
1. No. Check the parity of the overall number of pieces and show that it never changes.
2. No. There are eight vertices that have odd number of edges going out of them and therefore each one of them should be either a beginning or an end of such a trace which is impossible.
1. Show how you can make entire first row and entire first column white using the permitted operations. After that all the boxes must be white.
2. Count the number of all the edges going out of all the vertices and check itsparity. It must be even since every edge has been counted exactly twice.
3. There is only one solution: $1.11.
4. p = 3 is the only answer. Check the remainders modulo 3 to see that any other prime number can be excluded.
1. Show that every edge in the sum is counted exactky twice.
2. If every cage is occupied by no more than one rabbit then obviously there are no more than 99 rabbits.
3. Think of 1000001 imaginary cages numbered 0 thru 1000000. Put every bostonian in a cage whose number equals to the number of hairs on his/her head. If each cage contains no more than two persons then altogether there are no more than 2 x 1000001 < 2500000 "caged" people - thus we proved that some cage has at least three people in it (even more than we wanted!).
4. Having mentally built 11 cages numbered 0 thru 10 let's put every number into a cage corresponding to its remainder modulo 11. Then by pigeonhole principle some two numbers are in the same cage.
5. The first player wins by taking one candy with the first move. After that he/she must maintain divisibility by 3 - that is, if the opponent takes x candies then the first player takes 3-x candies.
1. Use three imaginary cages for three types of apples - put every box into a corresponding cage.
2. Show that there are 28 possible differences which can have values from 1 thru 14 and additionally, difference 14 can occur no more than once.
3. No. Such transpositions can only transpose chips on positions of equal parity.
4. This is not really a game - meaning that the outcome doesn't depend on how the players play. Indeed, the game ends when there are exactly 45 one-stone piles. Since with every move the number of piles increases by 1, and initially there are three piles, it follows that the game always lasts exactly 42 moves regardless of the players' moves. Thus, the second player makes the last move.
1.
Let's mark every box with a plus sign "+" if that is a "winning" field (that is, the player who starts the game with the king standing on that field wins) and with a minus sign "-" if that's the "losing" field. Start with a1, which
clearly must be marked with "-" and fill out the entire board.
2. That is not exactly true - for example, if the game doesn't have "end" positions (that is, the ones that do not have a move leading out of them)
then obviously a player can always make a move and therefore the game will drag on forever. Let us then prove that one of the players has a non-losing startegy (then in the case of a game that always lasts some finite amount of time that strategy is bound to be a winning one). We can use the same reasoning as in the previous question and mark all end positions with "-", then mark all the positions from which a player can move into an end position with a "+" (they are winning fields, of course). Furthermore if a field is such that any move from it leads to a "+" field then we can mark it with a "-" etc. Finally, the original start position will be marked with either plus or minus, QED.
3. The first player wins by taking one candy from the bigger pile thus making the numbers of candies in piles equal. After that all he/she needs to do is to maintain that equality with every move until the end of the game.
4. A+B (mod k) = A(mod k) + B(mod k) (subtract k if that sum is greater than k-1).
1. The first player wins by connecting some two diametricaly opposed points A and B with the first move. Then she simply makes moves symmetric to the ones of the second player with respect to the line AB.
2. Create 100 imaginary cages marked with numbers 0 thru 99 which will house any number of integers simply by assigning number X to the cage whose number equals X (mod 100). If you place numbers 30, 31, ..., 3100 into the cages in this manner, then by the pigeonhole principle some two of them - 3m and 3n, m > n - will share a cage therefore having the same remainder modulo 100. Show then that 3m-n has reainder 1 mod 100, QED.
3. This is just an exercise in accuracy.
4. Obviously, any team cannot play less than zero and more than nine games. Therefore there are only ten possibilities; also, zero and nine cannot happen simultaneously. So we have ten teams ("rabbits or pigeons") and no more than nine cages (numbers of the games played - 0 thru 8, or 1 thru 9). Thus pigeonhole principle applies.
1. Use remainders modulo 1000 instead of modulo 100.
2. Answer: 24. Just find out how many times five goes into 100! as a factor.
3. Reflect B about line L to produce point B'. Then point of intersection of L and AB' is the touch point for the desired shortest path.
1. Unsolved.
2. a) the digits to cross out are the first eight and the eleventh (zero).
b) cross out the first nine digits.
3. 8126 + 8126 = 16252.
4. a) Reflect point A about one of the sides of the angle to obtain point A' then reflect point B about other side to produce point B'. Then intersections of line A'B' with the sides will give you the touchpoints.
b) Perform a translation of point A in the direction perpendicular to the river's shores at the distance equal to the river's width. Then intersect line A'B with the shore closest to B. That will give us one of the bridge's endpoints.
1. In this case the traveller goes from point A to the vertex of the angle and then to point B.
2. They are all pretty straightforward except rule for 11 which goes like this: calculate alternating sum of a number's digits starting with the ones and check if the result is divisible by 11. For instance, 94897253701 would give you 1-0+7-3+5-2+7-9+8-4+9 = 19, meaning that the original number is not divisible by 11.
3. This number is divisible by 3 but not by 9 which disqualifies it immediately.
1. Construct a flat fold-out version of the can - a rectangle with two circles and use the fact that the shortest path on the plane is a straight line.
2. Use divisibility by 2 and 4.
3. Surely C must be divisible by 9 and it is obvious that B < 73. Therefore C = 9.
4. a) Take a regular triangle with side 1 and look at its vertices' colors.
b) Take any segment AB with two equally colored (say, in black) ends. If its midpoint M is white let's reflect A about B and B about A to construct points B' and A' respectively. If any of the new points are black then we get the needed trio; if not, then A', B' and M form one.
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?
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
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?
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?
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?
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:
1. Find G.C.D. for the following pairs
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?
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?
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?
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.
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.
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"?
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
Solutions for Session N 2 (10/03/1999)
Session questions
Homework questions
Solutions for Session N 3 (10/10/1999)
Session questions
Homework questions
Solutions for Session N 4 (10/17/1999)
Session questions
Homework questions
Solutions for Session N 5 (10/24/1999)
Session questions
Homework questions
Solutions for Session N 6 (10/31/1999)
Session questions
Homework questions
Solutions for Session N 7 (11/07/1999)
Session questions
Homework questions
a) 2(PA+PB+PC) is no less than AB+AC+BC
b) PA+PB+PC is no greater than AB+AC+BC
Solutions for Session N 8 (11/14/1999)
Session questions
Homework questions
Solutions for Session N 9 (11/21/1999)
Session questions
Homework questions
Create a winning strategy for the policeman if it is known that
his best speed is twice that of the gangster's best speed.
Solutions for Session N 10 (12/05/1999)
Session questions
Homework questions
Solutions for Session N 11 (12/12/1999)
Session questions
Homework questions
Solutions for Session N 12 (12/19/1999)
Session questions
Homework questions
b) Same question for 10 coins.
