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

  How many two-digit numbers are there such that the tens digit is greater than the units digit?

  Topics:

  Arithmetic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Ali Baba and the Forty Thieves

  Ali Baba wrote the number `17` on a piece of paper. The forty thieves pass the paper to each other, and each one either adds `1` to the existing number, or subtracts `1`, until each of them has done so once, and then they return the paper to Ali Baba.

  Is it possible that the number now written on the paper is `40`?

  Topics:

  Arithmetic Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  Find all pairs of prime numbers whose difference is `17`.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Prime Numbers Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  In a magical country, there are coins worth `1`, `2`, `3` and `5` liras. Yossi has `25` coins from the magical country.

  Must there necessarily be `7` coins of the same value among these coins?

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  In a class of `38` students, prove that there are four students who celebrate their birthday in the same month.

  Topics:

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

• Question

  Prove that there exist two powers of `2` such that their difference is divisible by `2017`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle
  Sources:
  • problems.ru web site

• Question

  On a circle, `2016` blue points and one red point are marked. Consider all possible polygons whose vertices are at these points. Which polygons are more numerous – those that contain the red point or those whose vertices are all blue?

  Topics:

  Combinatorics -> Matchings Geometry -> Plane Geometry -> Circles
  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

• Apples and Pears

  There is a basket containing `30` fruits. It is known that among any `12` fruits we take from the basket, there is necessarily at least one apple, and among any `20` fruits there is necessarily one pear. How many apples and how many pears are there in the basket?

  Topics:

  Combinatorics -> Pigeonhole Principle Algebra -> Inequalities Logic -> Reasoning / Logic
  Sources:
  • problems.ru web site

• Three Friends

  There are three friends, Weiss, Schwartzman, and Rotenberg. This trio of friends is special because one of them is blonde, one is ginger (redhead), and one has black hair. One day, the blonde guy said to Schwartzman: "We are a very special trio of friends! Notice that it's not only that the last names of the three of us mean colors, but also that each of our last names does not match his hair color."

  What hair color does each of these three people have?

  Note: "Schwartzman" means "black man", "Rotenberg" means "red mountain" and "Weiss" means "white" (from Yiddish).

  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Number Tables Logic -> Truth-tellers and Liars Problems
  Sources:
  • problems.ru web site