Combinatorics

Combinatorics is the art of counting. It deals with selections, arrangements, and combinations of objects. Questions involve determining the number of ways to perform tasks, arrange items (permutations), or choose subsets (combinations), often using principles like the product rule and sum rule.

Pigeonhole Principle Double Counting Binomial Coefficients and Pascal's Triangle Product Rule / Rule of Product Graph Theory Matchings Induction (Mathematical Induction) Game Theory Combinatorial Geometry Invariants Case Analysis / Checking Cases Processes / Procedures Number Tables Colorings

• Question

  In a school, there are `400` students. Prove that there exist two students who celebrate their birthday on the same date of the year.

  Topics:

  Combinatorics -> Pigeonhole Principle
  Sources:
  • problems.ru web site

• Question

  Someone made `15` point-like holes in a carpet that is `4xx4` meters in size. Is it always possible to cut out a rug of size `1xx1` meter from the original carpet such that it has no holes?

  Show hint

  Log in here to receive the hint
  Topics:

  Geometry Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry
  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

  How can you divide `7` apples equally among `12` children, if you are not allowed to cut any apple into more than `5` pieces?

  Show hint

  Log in here to receive the hint
  Topics:

  Algebra -> Word Problems Arithmetic -> Fractions Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Number Theory -> Division
  Sources:
  • problems.ru web site

• Question

  Given a three-digit prime number with all its digits distinct. It is known that its last digit is equal to the sum of the other two digits. Find all the possibilities for the last digit of this number.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Prime Numbers Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 2, 4, and 8 Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• 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 Knight and the Dragon

  A knight encountered a dragon with three heads on his way and they began to fight. Every time the knight chops off one of the dragon's heads, three new heads appear in its place. Is it possible that at the end of the battle, the dragon will have a thousand heads?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd)

• Question

  The number `458` is written on the board. In each single step, you are allowed to either multiply the number written on the board by `2`, or erase its last digit.

  Is it possible to obtain the number `14` using these operations?

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site