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

  Consider the integers from `1` to `700`.

  a. How many of these numbers are even?

  b. How many of these numbers are divisible by `7`?

  c. How many of these numbers are not divisible by `2` nor by `7`?

  Answer question c.

  Topics:

  Number Theory -> Prime Numbers Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Matchings Number Theory -> Division -> Parity (Even/Odd) Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Set Theory

• 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

  What is the maximum number of chess kings that can be placed on an `8xx8` board such that they do not threaten each other?

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry

• Question

  What is the maximum number of rooks that can be placed on an `8xx8` board so that they do not threaten each other?

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Minimum and Maximum Problems / Optimization Problems

• 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

  A cannibal captured `6` people.

  a. In how many different ways can he choose one person for breakfast, one person for lunch, and one person for dinner?

  b. In how many different ways can he choose three people to release them?

  Topics:

  Combinatorics -> Binomial Coefficients and Pascal's Triangle Combinatorics -> Product Rule / Rule of Product Number Theory -> Division

• Question

  In a class of `30` students, each one is allowed to go on the annual trip or stay at home. What is the number of possible combinations for going on the trip?

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  Given `11` numbers between `1` and `99`. Prove that there are two of them such that their difference is strictly less than `10`.

  Topics:

  Combinatorics -> Pigeonhole Principle

• Question

  Along the street are located `6` trees. One day, `6` parrots arrived and sat on the trees, one parrot on each tree. From time to time, two parrots each move to a neighboring tree of their choice. Can the parrots all gather on the same tree?

  Topics:

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

• 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