Proof and Example, Proof by Contradiction

Proof by contradiction (reductio ad absurdum) is an indirect proof technique. It assumes the negation of the statement to be proven is true, and then derives a logical contradiction from this assumption, thereby establishing the original statement's truth. Questions require applying this method.

• Question

  A square is divided into several convex polygons (more than `1`), each of which has a different number of sides. Prove that among these polygons there is a triangle.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Combinatorics -> Graph Theory Geometry -> Plane Geometry -> Triangles Proof and Example -> Proof by Contradiction Geometry -> Solid Geometry / Geometry in Space -> Polyhedra Minimum and Maximum Problems / Optimization Problems

• 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

  A plane is colored with two colors (that is, every point on the plane is colored with one of these two colors). Prove that there exist two points on the plane at a distance of `1` such that they are both the same color.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry -> Triangles Proof and Example -> Constructing an Example / Counterexample 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

  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

  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