MATH 64091
KSU Spring 2015
Jenya Soprunova
Parity
Example 1. Eleven gears are connected in a circle. Can they all rotate?
Solution. Any two adjacent gears rotate in opposite directions. Since the total number of
gears is 11, after we go around the circle, the first and the last gears would have to rotate in
the same direction, which is impossible, so the answer here is no.
Example 2. Seven integers are written around a circle. Show that you can find two numbers
next to each other whose sum is even.
Solution. If there are either two even numbers or two odd numbers next to each other, we
are done. Otherwise, even and odd numbers have to alternate, which is impossible as we
have 7 (odd!) numbers total around the circle.
Example 3. You start with 10 sheets of paper. Cut a few of them into 7 pieces, and a few
of them into 5 pieces. Then you cut some of the obtained sheets into 7 or 5 pieces again, and
so on. Can you get 2017 pieces this way?
Solution. When one cuts a piece of paper into seven (five) pieces the overall number of pieces
goes up by six (four). That is, after each round the overall number of pieces changes by an
even number. Since initially we had an even number of pieces, the overall number will stay
even throughout the process and we will never be able to get 2017 pieces of paper.
Example 4. Three hockey pucks, A, B, and C, lie on the floor of an ice arena and form
a triangle. A hockey player hits one of them so that it passes between the other two. He
repeats this 24 more times (he may hit any puck he wishes at every turn). Is it possible for
the pucks to be in the initial position after he is done?
Solution. Let us say that a triangle ABC formed by the pucks has a positive orientation
if as we go around the triangle in the clockwise direction the pucks go in the order A, B ,
C and a negative orientation if as we go around the triangle in the clockwise direction the
pucks go in the order A, C , B . Then the orientation changes after each hit. Hence after 25
hits the orientation will be opposite compared to the initial orientation, so the puck cannot
be in the initial position when the player is done.
2
Example 5. The numbers 1 through 2018 are written on the blackboard. At every step you
erase two numbers and write their positive difference instead. After this is done 2017 times
there will be a single number written on the board. Can this number be 0?
Solution. Let S be the sum of all the numbers written on the board and let’s see how S
changes at every step. If we decided to erase the numbers a and b with, say, a ≥ b and
replace them with a − b, then the overall sum goes down by a + b and up by a − b, so S
goes down by a + b − (a − b) = 2b, so at every step S decreases by an even number. The
initial value of S is
2018 · 2019
1 + 2 + · · · + 2018 = = 1009 · 2019,
2
which is odd, so S will remain odd at every step and when we get to a single number, it
cannot be equal to 0 (which is even).
Example 6. Is it possible to connect 7 computers with cables so that every computer is
connected to exactly three other computers?
Solution. If this were possible, the number of cables would have been (3 × 7)/2, which is not
an integer.
3
Homework Problems
Problem 1. Let m and n be integers. Show that mn(m + n) is even.
Problem 2. A cashier has only pennies, nickels, and quarters. When I asked him to break
a $1 bill he gave me 25 coins. Do you think the cashier made a counting mistake?
Problem 3. The product of 22 integers is equal 1. Show that their sum cannot be zero.
Problem 4. Is it possible to form a magic square out of the first 36 prime numbers? (A
magic square here is a 6 × 6 array of those 36 prime numbers where each number used
exactly once and all the row and column sums are the same.)
Problem 5. The numbers 1 through 10 are written in a row. Can you place pluses and
minuses between those numbers so that the value of the resulting expression is zero?
Problem 6. (a) There are 100 soldiers in a detachment, and every evening three of them
are on duty. Can it happen that after a certain period of time each soldier has shared duty
with every other soldier exactly once? (b) Same question about a detachment of 7 soldiers.
Problem 7. Sam bought a 96-page notebook and numbered the pages 1 through 192. He
then tore out 25 pages and added the 50 numbers that he found on those pages. Could the
number he got be 2016?
Problem 8. A grasshopper jumps along a line. His first jump is 1 inch, second is 2 inches,
third is 3 inches, and so on. At every jump he can go either to the left or to the right. Show
that he cannot return to his initial position after 2018 jumps.
Problem 9. Three frogs are sitting in three corners of a square. They play leapfrog taking
turns leaping over each other. If, say, frog A leaps over frog B then frog B is exactly in the
middle between the positions of frog A before the leap and after the leap. Can one of the
frogs at some point jump to the fourth corner of the square? Hint: keep track of the parities
of the frogs’ coordinates.
Bonus 1. Out of 101 coins, 50 are counterfeit and differ from the original ones in weight
by 1 gram (some could be lighter and some could be heavier). You pick a coin out of these
101 coins. You have a scale that shows the difference in weights between the two sides of the
scale. Can you check in one weighing if that coin is counterfeit?
