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

  An `N×N` table is filled with numbers such that all rows are distinct (differing in at least one position). Prove that it is possible to delete a column such that in the remaining table all rows are also distinct.
  (a) Hint

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Proof and Example -> Proof by Contradiction
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 2

• Question

  When it's dark outside and there are no buses, Yossi and Danny always hang out together. Currently, there are no buses, and Yossi is walking alone to the park. Is it true that it is daytime now?

  Topics:

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

• Question

  One day, Harry Potter found a strange notebook in which the following one hundred sentences were written:

  "In this notebook, there is exactly one sentence that is false."

  "In this notebook, there are exactly two sentences that are false."

  "In this notebook, there are exactly three sentences that are false."

  ...

  "In this notebook, there are exactly one hundred sentences that are false."

  Are there any true sentences in this notebook, and if so, how many? Justify your answer!

  Topics:

  Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction Logic -> Truth-tellers and Liars Problems Logic -> Reasoning / Logic -> Paradoxes

• Question

  In a square with side length 1, a finite number of segments parallel to the sides of the square were drawn, with a total length of 18 (they can intersect). Prove that among the parts into which the square is divided by the segments, there is a part with an area of at least 0.01. 
  A. Engenes, A. Brazins 

  Topics:

  Geometry -> Plane Geometry Geometry -> Area Calculation Algebra -> Inequalities Proof and Example -> Proof by Contradiction
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 6

• Question

  In Wonderland, there are `n` cities, and every two of them are connected by a road. The roads meet only in the cities (there are no junctions outside the cities). A wicked magician wants to turn all the roads into one-way streets in such a way that if you leave any city, you can't return to it anymore.

  a. Prove that the wicked magician can do this.

  b. Prove that there exists a city from which one can reach any other city, and that there exists a city from which it is impossible to leave at all.

  c. Prove that there exists a path that passes through all the cities and there is only one such path.

  Topics:

  Combinatorics -> Graph Theory Combinatorics -> Induction (Mathematical Induction) Proof and Example -> Proof by Contradiction

• Question

  Can you fill a `5xx5` table with real numbers such that the sum of each row is positive, and the sum of each column is negative?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Double Counting Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction
  Sources:
  • problems.ru web site

• Question

  Can you fill a table of size `5xx5` with

  a. Integers,

  b. Real numbers,

   such that the sum of each row is even, and the sum of each column is odd?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Double Counting Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction

• Question

  Can you find `35` integers whose average is equal to `6.35`?

  Show hint

  Log in here to receive the hint
  Topics:

  Arithmetic Combinatorics -> Double Counting Algebra -> Inequalities -> Averages / Means Proof and Example -> Proof by Contradiction
  Sources:
  • problems.ru web site

• Question

  In two classes with an equal number of students, a quiz was administered. After grading the quiz, the teacher claimed that the number of grades of `0 ` was `13` greater than the number of all other grades combined. Is it possible that he was mistaken?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Double Counting Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction
  Sources:
  • problems.ru web site

• Question

  Does there exist a perfect square whose digits sum to `2001`?

  Justify or provide an example!

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 Number Theory -> Division -> Parity (Even/Odd) Number Theory -> Prime Numbers -> Prime Factorization Proof and Example -> Proof by Contradiction
  Sources:
  • problems.ru web site