Combinatorics, Invariants

An invariant is a property of a system or mathematical object that remains unchanged when transformations or operations are applied. Identifying an invariant can be key to solving problems about processes or proving impossibility. Questions involve finding such constant quantities or properties.

• Question

  From a chessboard, two opposite corners are removed (the squares `a1` and `h8`, for example). Can you tile the remaining board with dominoes?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Invariants Combinatorics -> Matchings Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring Puzzles and Rebuses

• Ants on a Stick

  On a stick that is one meter long, there are `10` ants, `5` from each side, at distances of one centimeter (see the picture). The ants on the left side of the stick move to the right, and the ants on the right side of the stick move to the left. The speed of each ant is constant and equal to one centimeter per second. When two ants meet, they both reverse direction and start moving away from each other. When any ant reaches the end of the stick, it falls off (ants are particularly stupid creatures).

  

  a. Will all the ants fall off the stick, and if so, in how much time?

  b. How many collisions will occur between the ants?

  Topics:

  Combinatorics -> Invariants Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures

• Milk and Coffee

  A. Hannah has two cups, one with milk and the other with coffee. The amounts of milk and coffee are the same. Hannah transfers two teaspoons of milk into the cup with coffee, mixes, and then transfers two teaspoons from the cup of coffee into the milk. Currently, she has two cups each containing a mixture of coffee and milk. What is greater – the amount of milk in the cup of coffee or the amount of coffee in the cup of milk?

  B. The same question, but this time Hannah adds milk to the coffee without mixing.

  Topics:

  Combinatorics -> Invariants Logic -> Reasoning / Logic

• Question

  The following numbers are written on the board: `1, 2, 3, …, 2016, 2017`. In one move, it is allowed to choose a pair of numbers written on the board, erase them, and write their (positive) difference in their place. After several such operations, a single number remains on the board. Is it possible that this is zero?

  Topics:

  Arithmetic Combinatorics -> Invariants Combinatorics -> Induction (Mathematical Induction) Number Theory -> Division -> Parity (Even/Odd) Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  A. You have a large jug of 12 liters of olive oil and two empty smaller vessels, one of 5 liters and one of 8 liters. Can you divide the oil you have into two equal parts, if you only have these vessels and no additional measuring tools?

  B. The same question, but instead of the 5-liter vessel, you have a 4-liter vessel.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) -> Euclidean Algorithm Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Prove that the given shape cannot be cut into dominoes:

  

  Topics:

  Combinatorics -> Invariants Combinatorics -> Matchings Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems

• Question

  Can you cut the shape on the left into six shapes like the shape on the right?

  

  Topics:

  Combinatorics -> Invariants Combinatorics -> Matchings Proof and Example Combinatorics -> Colorings -> Chessboard Coloring Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry

• Question

  Along the street are located `6` trees. One day, `6` parrots arrived and sat on the trees, one parrot on each tree. From time to time, two parrots each move to a neighboring tree of their choice. Can the parrots all gather on the same tree?

  Topics:

  Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd)

• The Grasshopper

  Consider an infinite grid of squares. A grasshopper sits on one of the squares. The grasshopper can jump two squares in any horizontal or vertical direction, and it can jump to the adjacent square diagonally. Can the grasshopper ever reach a square that is adjacent to its starting square by a side?

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Combinatorics -> Colorings -> Chessboard Coloring
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 2

• Log of Wood

  You have a very long log of wood. Can you measure exactly one meter from it, if you have for this purpose:
  а. A stick with a length of one and a half meters and another stick with a length of 40 centimeters,
  б. A stick with a length of one and a half meters and another stick with a length of 30 centimeters,

  Assuming you have no other measuring tools? Explain!

  Topics:

  Combinatorics -> Invariants Algebra -> Word Problems Logic -> Reasoning / Logic Arithmetic -> Division with Remainder
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 7
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 5-6 Question 2