Parity Problems

1. The numbers 1 through 2010 are written on the blackboard. At

every step you erase two numbers and write their positive
difference instead. After this is done 2009 times there will be a
single number written on the board (why?). Can this number
be 0?
1. The numbers 1 through 2010 are written on the blackboard. At
every step you erase two numbers and write their positive
difference instead. After this is done 2009 times there will be a
single number written on the board (why?). Can this number
be 0?
2. A grasshopper jumps along a line. His first jump is 1 inch,
second is 2 inches, third 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 2014 jumps.
1. The numbers 1 through 2010 are written on the blackboard. At
every step you erase two numbers and write their positive
difference instead. After this is done 2009 times there will be a
single number written on the board (why?). Can this number
be 0?
2. A grasshopper jumps along a line. His first jump is 1 inch,
second is 2 inches, third 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 2014 jumps.
3. Three frogs are placed on three vertices of a square. Every
minute, one frog leaps over another frog, in such a way that the
leapee is at the midpoint of the line segment whose endpoints
are the starting and ending position of the leaper. Will a frog
ever occupy the vertex of the square that was originally
unoccupied?
4. On the table there are 7 cups, all of them are upside down. In
one move, you can flip any 4 cups. Is it possible to ensure
that all the cups are right way up after some moves?
4. On the table there are 7 cups, all of them are upside down. In
one move, you can flip any 4 cups. Is it possible to ensure
that all the cups are right way up after some moves?
5. On the number line we mark 45 points lying outside the
segment AB. Prove that the sum of the distances from these
points to point A does not equal the sum of the distances
from these points to point B .
4. On the table there are 7 cups, all of them are upside down. In
one move, you can flip any 4 cups. Is it possible to ensure
that all the cups are right way up after some moves?
5. On the number line we mark 45 points lying outside the
segment AB. Prove that the sum of the distances from these
points to point A does not equal the sum of the distances
from these points to point B .
6. Give 2015 positive integers a1 , a2 , · · · a2015 . Let b1 , b2 , · · · b2015
be the same numbers but in different order. Show that the
product (a1 − b1 )(a2 − b2 ) · · · (a2015 − b2015 ) is always even.
4. On the table there are 7 cups, all of them are upside down. In
one move, you can flip any 4 cups. Is it possible to ensure
that all the cups are right way up after some moves?
5. On the number line we mark 45 points lying outside the
segment AB. Prove that the sum of the distances from these
points to point A does not equal the sum of the distances
from these points to point B .
6. Give 2015 positive integers a1 , a2 , · · · a2015 . Let b1 , b2 , · · · b2015
be the same numbers but in different order. Show that the
product (a1 − b1 )(a2 − b2 ) · · · (a2015 − b2015 ) is always even.
7. Each square of a 25 × 25 table is filled with either 1 or −1.
Let ai be product of all numbers in the i-th row and bj be
product of all numbers in the j-th column. Show that
a1 + · · · a25 + b1 + · · · b25 6= 0.
8. In a 6 × 6 chart all but one corner blue square are painted
white. You are allowed to repaint any column or any row in
the chart (i.e., select any row or column and flip the color of
all squares within it). Is it possible to attain an entirely white
chart by using only the permitted operations?
8. In a 6 × 6 chart all but one corner blue square are painted
white. You are allowed to repaint any column or any row in
the chart (i.e., select any row or column and flip the color of
all squares within it). Is it possible to attain an entirely white
chart by using only the permitted operations?
9. To send a message consisting of n2 zeros and ones, you write
it in the form of a n × n table. Append an n−column consists
of the row sum of its elements modulo 2. Similarly, you also
append an (n + 1)−row consists of the column sum of its
elements modulo 2. For example, if the message is 0111, the
2 × 2 table would be augmented to 3 × 3 table in the figure.
0 1 1
1 1 0
1 0 1
Prove that if the extended (n + 1) × (n + 1) table has only
one mistake, then this error will be found and corrected.
10. Out of 101 coins, 50 are counterfeit and differ from the
original ones in weight by 1 gram. You pick a coin out of
those 101 coins. You have a scale that shows the difference in
weights between the two sides of the scale. Find the least
number of weighings you need to perform to know if this coin
is counterfeit?
10. Out of 101 coins, 50 are counterfeit and differ from the
original ones in weight by 1 gram. You pick a coin out of
those 101 coins. You have a scale that shows the difference in
weights between the two sides of the scale. Find the least
number of weighings you need to perform to know if this coin
is counterfeit?
11. Is it possible to arrange 40 persons at a round table so that
every 2 persons, between whom there is an even number of
persons, have a mutual friend and that every 2 persons,
between whom there is an odd number of persons, does not
have a mutual friend.
12. Product of 100 natural numbers a1 × a2 × · · · × a100 are
written on a blackboard. Consider the 99 expressions, each of
which is obtained by replacing one of the multiplication sign
by the plus sign. It is known that exactly 32 values of these
expressions are even. What is the largest number of even
numbers among a1 , a2 , · · · , a100 .
12. Product of 100 natural numbers a1 × a2 × · · · × a100 are
written on a blackboard. Consider the 99 expressions, each of
which is obtained by replacing one of the multiplication sign
by the plus sign. It is known that exactly 32 values of these
expressions are even. What is the largest number of even
numbers among a1 , a2 , · · · , a100 .
13. On the line, there are two coins the red one is on the left and
the blue one is on the right. You are allow to do any of the
two operations: insert two coins of the same color in a row
anywhere in a straight line and remove any two adjacent coins
of the same color. Is it possible for a finite number of
operations on a straight line to leave exactly two coins: the
red on the right, and blue - on the left?
14. A lock has 16 keys arranged in a 4 × 4 array, each key
oriented either horizontally or vertically. In order to open it,
all the keys must be vertically oriented. When a key is
switched to another position, all the other keys in the same
row and column automatically switch their positions too (see
diagram). Show that no matter what the starting positions
are, it is always possible to open this lock (Only one key at a
time can be switched).
15. Is it possible to paint on a board of size 25 × 25 so that each
cell has an odd number of colored neighbors?
15. Is it possible to paint on a board of size 25 × 25 so that each
cell has an odd number of colored neighbors?
16. Can a convex nonagon (a polygon with 9 sides) be cut into
parallelograms?
15. Is it possible to paint on a board of size 25 × 25 so that each
cell has an odd number of colored neighbors?
16. Can a convex nonagon (a polygon with 9 sides) be cut into
parallelograms?
17. Let n ≥ 2 be an integer and Tn be the number of nonempty
subsets S of {1, 2, 3, · · · , n} with the property that the
average of the elements of S is an integer. Prove that Tn − n
is always even.
15. Is it possible to paint on a board of size 25 × 25 so that each
cell has an odd number of colored neighbors?
16. Can a convex nonagon (a polygon with 9 sides) be cut into
parallelograms?
17. Let n ≥ 2 be an integer and Tn be the number of nonempty
subsets S of {1, 2, 3, · · · , n} with the property that the
average of the elements of S is an integer. Prove that Tn − n
is always even.
18. A circle is divided by points into 3k arcs so that there are k
arcs of length 1, 2, and 3. Prove that there are 2 diametrically
opposite division points.