Combinatorics, Double Counting

Double Counting is a combinatorial proof technique where a quantity is counted in two different ways. Setting the two resulting expressions equal to each other can lead to proving identities or inequalities. Questions require identifying a set that can be counted in multiple ways.

• Question

  In a country there are `100` cities, and from each city `4` roads lead out (a road can only start or end in a city). How many roads are there in this country?

  Topics:

  Combinatorics -> Double Counting Combinatorics -> Graph Theory
  Sources:
  • problems.ru web site

• 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

• The Sophisticated Task

  Hannah has a basket with `13` apples. Hannah wants to know the total weight of all these apples. Rachel has a digital scale, and she is willing to help Hannah, but only under the following conditions: In each weighing, Hannah can weigh exactly `2` apples, and the number of weighings cannot exceed `8`.

  Explain how, under these conditions, Hannah can know the total weight of the apples.

  Topics:

  Combinatorics -> Double Counting Algebra -> Equations Algebra -> Word Problems Proof and Example -> Constructing an Example / Counterexample Algorithm Theory -> Weighing
  Sources:
  • problems.ru web site

• 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

  Given an `M times N` matrix, where each cell contains a real number. It is known that the sum of the numbers in each row and each column is equal to `1`.

  Prove that `M = N`.

  Topics:

  Combinatorics -> Double Counting Logic -> Reasoning / Logic Algebra -> Inequalities -> Averages / Means

• 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 magical land consists of `25` provinces. Is it possible that each province borders an odd number of other provinces?

  Topics:

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