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

  Alice loves to drink tea. For this, she always takes one cup and one saucer for the cup. Alice has `3` different cups and `2` different saucers. In how many different ways can she assemble her tea set?

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  From city A' to city B', there are `4` roads, and from city B' to city C', there are `3` roads. In how many different ways can one get from A' to C', if we are only allowed to travel on the roads, and in addition, we do not want to travel backwards? 

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  In a class there are `15` girls and `16` boys. We want to choose a committee consisting of one girl and one boy. In how many different ways can the committee be chosen?

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  In a company, there are `8` mathematicians, `15` economists, and `25` programmers. We need to choose a committee of three people, including one person from each profession. In how many different ways can the committee be chosen?

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  Given a square that is divided into `4` smaller squares. In how many different ways can the smaller squares be colored green and orange?

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  Given a real number `a` such that `a+1/a` is an integer. Prove that `a^n+1/a^n` is also an integer for every natural number `n`.

  Topics:

  Number Theory Combinatorics -> Induction (Mathematical Induction) Algebra -> Algebraic Techniques Proof and Example Algebra -> Sequences

• Question

  `101` points are located on a circle. Which polygons with vertices at these points are more numerous – polygons with `51` sides or polygons with `50` sides?

  Topics:

  Combinatorics -> Binomial Coefficients and Pascal's Triangle Combinatorics -> Matchings Geometry -> Plane Geometry -> Circles

• Question

  Are there more seven-digit numbers that have no zeros in their decimal representation, or those that have no two adjacent identical digits in their decimal representation?

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Who Broke the Glass?

  One of the following four students: Avi, Benny, Gili, and Danny – broke a glass. The principal asks them who did it. Here are the answers she received:

  Avi: I know for certain that whoever broke the glass, it was not me or Benny.

  Benny: I know for certain that whoever broke the glass, it was not me or Danny.

  Gili: I know for certain that whoever broke the glass, it was not me or Benny.

  Danny: I know for certain that whoever broke the glass, it was not me or Avi.

  It is known that only one of them broke the glass, and it is also known that three of the students told the truth, and one lied. So who broke the glass?

  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Logic -> Truth-tellers and Liars Problems

• Question

  The numbers from `1` to `2n` are written in a row in some order. Add to each number the index of the position it stands on. Prove that among the `2n` sums we obtained, there are two whose difference is divisible by `2n`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle Proof and Example -> Proof by Contradiction