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

  By how much is the sum of all even numbers not exceeding `100` greater than the sum of all odd numbers not exceeding `100`?

  Topics:

  Arithmetic Combinatorics -> Double Counting Algebra -> Algebraic Techniques Logic -> Reasoning / Logic Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence

• The King and the Corrupt Ministers

  The king of the magical land has `100` ministers. It is known that among any `10` ministers we choose, there is at least one corrupt minister. What is the minimum possible number of corrupt ministers in the magical land?

  Topics:

  Combinatorics -> Pigeonhole Principle Minimum and Maximum Problems / Optimization Problems

• Question

  In a company, there are `13` people, including the manager. One day, the manager decided to appoint a deputy, an alternate, a secretary, and a clerk from the company's employees. In how many different ways can he do this, if the skills of the employees do not affect the type of positions they can fill?

  Topics:

  Combinatorics -> Product Rule / Rule of Product

• Question

  Prove that 

  `1+3+5+...+(2n-1)=n^2`

  Topics:

  Combinatorics -> Induction (Mathematical Induction) Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence

• Frame

  On a grid paper, a square of size `NxxN` is given. Consider its frame with a width of one square. It consists of `4*(N-1)` squares.

  Can you write `4*(N-1)` consecutive integers (not necessarily positive) in the squares of the frame, such that the following condition holds:

  For every rectangle whose vertices are on the frame and whose sides are parallel to the diagonals of the original square, the sum of the numbers at the vertices is equal to a constant value. This also includes the "degenerate" rectangles of zero width that coincide with the diagonals of the square - in this case, simply sum the two numbers at the opposite vertices of the square.

  For:

  a. `N=3`

  b. `N=4`

  c. `N=5`

  

  Topics:

  Arithmetic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Tournament of Towns, 1983-1984, Fall, Practice Version, Grades 9-10 Question 3 Points 2+3+4

• Question

  A. You have a large jug of 12 liters of olive oil and two empty smaller vessels, one of 5 liters and one of 8 liters. Can you divide the oil you have into two equal parts, if you only have these vessels and no additional measuring tools?

  B. The same question, but instead of the 5-liter vessel, you have a 4-liter vessel.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) -> Euclidean Algorithm Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Prove that the given shape cannot be cut into dominoes:

  

  Topics:

  Combinatorics -> Invariants Combinatorics -> Matchings Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems

• Question

  Can you cut the shape on the left into six shapes like the shape on the right?

  

  Topics:

  Combinatorics -> Invariants Combinatorics -> Matchings Proof and Example Combinatorics -> Colorings -> Chessboard Coloring Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry

• Question

  A bouquet is composed of `7` roses, white and red (both colors are present). It is known that out of every two roses, one is necessarily white. How many white roses and how many red roses are in the bouquet?

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures

• Question

  Does there exist a perfect square that ends with the digits `...2017`?

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction