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

  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

• Question

  The numbers `1`, `2`, `3`, ..., `9` are divided into `3` sets. Prove that there is a set where the product of the numbers is greater than or equal to `72`.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory Combinatorics -> Pigeonhole Principle Algebra -> Inequalities Proof and Example -> Proof by Contradiction

• Question

  Given `50` distinct natural numbers between `1` and `100`. It is known that no two of these numbers sum to `100`. Is it necessarily true that one of these numbers must be a perfect square?

  Topics:

  Number Theory -> Prime Numbers Arithmetic Combinatorics -> Pigeonhole Principle Combinatorics -> Matchings Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Set Theory Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Shlomi has a chessboard and a cube whose face size is the same as the size of a square on the board. Shlomi wants to paint the faces of the cube black and white, and then roll the cube across the board so that each time the face touching the board is the same color as the square it touches. The cube is supposed to pass through each square on the board exactly once. Can Shlomi do this? Justify or provide an example.

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring

• Question

  Given natural numbers m, n such that `m/n <= sqrt 23`, prove that `m/n+3/{mn} <= sqrt 23`

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Algebra -> Inequalities Proof and Example -> Proof by Contradiction Algebra -> Algebraic Techniques -> Roots / Radicals
  Sources:
  • Mink Exercises and Additional Competition Materials, 2018-2019, Exercise 3 Question 4

• Question

  Is there a solution in natural numbers to the equation `x^2 + 12 = y^3` such that

  a. x is even (easier)

  b. x is odd

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Prime Numbers Number Theory -> Modular Arithmetic / Remainder Arithmetic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Arithmetic -> Division with Remainder Algebra -> Equations -> Diophantine Equations
  Sources:
  • Mink Exercises and Additional Competition Materials, 2018-2019, Exercise 3 Question 6

• Toys

  Jonathan has a collection of wooden toys. Some are cubes and some are spheres, some are red and some are blue.

  It is known that there are more spheres than cubes, and it is known that there are more blue toys than red toys.

  Prove that Jonathan has a blue sphere.

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 1

• Quiz

  In a class of 25 students, a quiz was given consisting of 7 questions. Prove that at least one of the following two statements is true:

  1. There is a student who solved an odd number of questions.
  2. There is a question that was solved by an even number of students.
  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 5-6 Question 5