Proof and Example

This category emphasizes the core mathematical activities of constructing rigorous arguments (proofs) to establish general truths, and using specific instances (examples) to illustrate concepts, test conjectures, or find counterexamples. Questions may ask for either or both.

• Question

  In a magical land, there are `2017` cities, and each city is connected by direct roads to at least `1008` other cities. Prove that from any city in the magical land, it is possible to reach any other city (not necessarily by a direct route).

  Topics:

  Combinatorics -> Graph Theory Proof and Example -> Proof by Contradiction

• 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

  Does there exist an infinite arithmetic progression consisting only of prime numbers?

  Note: We do not consider "trivial" arithmetic progressions, which are constant.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Prime Numbers Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence Proof and Example -> Proof by Contradiction

• Question

  Prove that the sum of the digits of a perfect square cannot be equal to `2019 `.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 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

  Does there exist a perfect square that ends with the digits `...2017`?

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  `19` apple trees are arranged in a circle. Prove that there exists a pair of adjacent trees such that the total number of apples on them is even.

  Topics:

  Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction

• Question

  Can you find two numbers such that both their sum and their product are odd? Justify your answer or provide an example!

  Topics:

  Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction

• Question

  Can you divide `44` balls into `9` piles, each containing a different number of balls?

  Topics:

  Arithmetic Combinatorics -> Pigeonhole Principle Proof and Example -> Proof by Contradiction

• Question

  Each of seven children is holding a balloon that is either red, green, or blue. Prove that there are three children with balloons of the same color.

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Proof by Contradiction