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

  A plane is colored with two colors (that is, every point on the plane is colored with one of these two colors). Prove that there exist two points on the plane at a distance of `1` such that they are both the same color.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry -> Triangles Proof and Example -> Constructing an Example / Counterexample Proof and Example -> Proof by Contradiction

• Question

  Is there a quadrilateral that can be cut into `6` parts by two straight cuts? Justify your answer or provide an example.

  Show hint

  Log in here to receive the hint
  Topics:

  Geometry -> Plane Geometry Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems

• Question

  It is known that all the angles of the given shape are right angles. Cut the shape into two polygons of equal area. You are only allowed to use an unmarked ruler.

  

  Show hint

  Log in here to receive the hint
  Topics:

  Geometry -> Area Calculation Geometry -> Plane Geometry -> Symmetry Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems

• Question

  In the plane, a point and `12` lines passing through it are given. Prove that there are two of these lines such that the angle between them is less than `17^@`.

  Topics:

  Combinatorics -> Pigeonhole Principle Geometry -> Plane Geometry -> Angle Calculation

• Question

  Given `12` intersecting lines in the plane. Prove that there exist two of these lines such that the angle between them is less than `17^@`.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Geometry -> Plane Geometry -> Angle Calculation Geometry -> Plane Geometry -> Plane Transformations -> Congruence Transformations (Isometries) -> Parallel Translation / Translation

• Balls in a Bag

  In a bag, there are `70` identical balls of different colors: `20` blue, `20` red, `20` yellow, and the rest are black and white. What is the minimum number of balls that must be drawn from the bag without looking, to ensure that we have `10` balls of the same color?

  Topics:

  Combinatorics -> Pigeonhole Principle

• Question

  In a `3×3` table, each of the squares can be colored black, or it can be left white. How many such colorings are there?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  In the "Sport-Toto" lottery, one must predict the results of soccer games – in each game, a win for the first team, a win for the second team, or a draw, without regard to the exact score. How many different ways are there to fill out a lottery ticket if each ticket contains `13` different games?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Product Rule / Rule of Product

• 26 Coins

  Given `26` coins that look identical. One of the coins is counterfeit, and it weighs less than a regular coin. How can you find the counterfeit coin using three weighings on a balance scale without weights?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Induction (Mathematical Induction) Logic -> Reasoning / Logic Algorithm Theory -> Weighing Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems

• 80 Coins

  Given `80` coins that look identical. One of the coins is counterfeit and weighs less than a regular coin. How can you find the counterfeit coin using four weighings on a balance scale without weights?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Induction (Mathematical Induction) Logic -> Reasoning / Logic Algorithm Theory -> Weighing Minimum and Maximum Problems / Optimization Problems