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 knight moves from square `a1` to square `h8`. Is it possible that along the way it visited every square on the board exactly once?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Double Counting Combinatorics -> Invariants Combinatorics -> Graph Theory Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring

• Question

  Every person who ever lived on Earth performed a certain number of handshakes (including 0). Prove that the number of people who performed an odd number of handshakes is even.

  Topics:

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

• Question

  The numbers `1`, `2`, `3`, ..., `8` are written on the vertices of a cube. Prove that there exists an edge of the cube such that the difference between the numbers at its endpoints is at least `3`.

  Topics:

  Geometry -> Solid Geometry / Geometry in Space Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction

• A mistake in the exercise

  Prove that there is an error in the following multiplication problem:

  \(\begin{array}& & & * & * & * & 2 & 7 \\ \times & & & & & * & * \\ \hline & * & * & * & * & * & 6 \\ + & * & * & * & * & * & \\ \hline & * & * & * & * & 4 & 6 \end{array}\)

  Topics:

  Arithmetic Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction Number Theory -> Division Puzzles and Rebuses -> Reconstruct the Exercise / Cryptarithmetic
  Sources:
  • Beno Arbel Olympiad, 2013, Grade 7 Question 4

• Question

  Can the product of two consecutive natural numbers be equal to the product of two consecutive even numbers?

  Topics:

  Number Theory Algebra -> Inequalities Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Does there exist a convex quadrilateral such that each of its diagonals divides it into two acute triangles?

  Topics:

  Proof and Example -> Proof by Contradiction Geometry -> Plane Geometry -> Angle Calculation

• Question

  Prove that if `n!+1` is divisible by `n+1`, then `n+1` is prime.

  Topics:

  Number Theory -> Prime Numbers Proof and Example -> Proof by Contradiction

• Perpendicular Hands

  How many times a day do the hour and minute hands lie on the same line, forming an angle of `180^@`? Are any of these lines perpendicular to each other?

  Topics:

  Logic Proof and Example -> Proof by Contradiction Geometry -> Plane Geometry -> Angle Calculation

• Question

  Does there exist a natural number which, when divided by the sum of its digits with a remainder, yields `2017` as both the quotient and the remainder?

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 Proof and Example -> Proof by Contradiction

• Pine Trees in the Forest

  A forester counts pine trees in a forest. He walked along each of the circles in the image, and within each circle he counted exactly `3` pine trees. Prove that the forester surely made a mistake in his count.

  

  Topics:

  Logic -> Reasoning / Logic Set Theory Proof and Example -> Proof by Contradiction