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

• Corruption in Parliament

  The parliament of the magical country consists of `20` people. It is known that among the `20` members of parliament, there is at least one who is not corrupt. Additionally, it is known that for any two members of parliament we choose, one is necessarily corrupt. How many members of parliament of the magical country are corrupt?

  Topics:

  Algebra -> Inequalities Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Playing with Chocolate

  Yossi and Danny are playing the following game. They have a chocolate bar of size `5xx7` squares, which is placed on a table. Each player, in turn, breaks one of the pieces of chocolate on the table along a straight line and returns the resulting pieces to the table. That is, in the first turn, the original chocolate bar is broken, and in the following turns, one piece is chosen from the pieces created up to that point and broken. It is only possible to break along the lines of the squares, and each break is from edge to edge. The player who cannot make a move loses. The winner eats all the chocolate.

  Which of the two can guarantee a victory for themselves, if Yossi makes the first move?

  Topics:

  Combinatorics -> Invariants Combinatorics -> Game Theory Logic -> Reasoning / Logic

• Game with Piles of Stones

  Two players are playing the following game. On the table are three piles of stones. The first pile has `10` stones, the second – `15`, and the third – `20`. Each player, in their turn, chooses one of the piles currently on the table and divides it into two smaller piles. The player who cannot make a move loses.

  Which of the two players has a winning strategy, and what is it?

  Topics:

  Combinatorics -> Invariants Combinatorics -> Game Theory Logic -> Reasoning / Logic
  Sources:
  • problems.ru web site

• Question

  Find a two-digit number that is twice as large as the product of its digits.

  Topics:

  Number Theory Arithmetic Algebra -> Algebraic Techniques Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Algebra -> Equations -> Diophantine Equations
  Sources:
  • problems.ru web site

• Question

  Suppose two pyramids are tangent to each other if they have no common interior points and they intersect in a non-degenerate planar polygon. Is it possible for 8 pyramids in space to all be tangent to each other? 
  A. Angeles 

  Topics:

  Combinatorics -> Combinatorial Geometry Proof and Example -> Constructing an Example / Counterexample Geometry -> Solid Geometry / Geometry in Space -> Polyhedra
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 11-12 Question 1 Points 7

• Question

  Solve the equation:

  `(x + 2010)(x + 2011)(x + 2012) = (x + 2011)(x + 2012)(x + 2013) `

  Topics:

  Algebra -> Algebraic Techniques Algebra -> Equations Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  A knight exited the square `a1` and, after several moves, returned to the same square.

  Is it possible that the knight made an odd number of moves?

  Show hint

  Log in here to receive the hint
  Topics:

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

• Question

  A knight moves from square `a1` to square `h8`. Is it possible that along the way it visited every square on the board exactly once?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Double Counting Combinatorics -> Invariants Combinatorics -> Graph Theory Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring

• Question

  Given an `M times N` matrix, where each cell contains a real number. It is known that the sum of the numbers in each row and each column is equal to `1`.

  Prove that `M = N`.

  Topics:

  Combinatorics -> Double Counting Logic -> Reasoning / Logic Algebra -> Inequalities -> Averages / Means

• Question

  Given a positive integer N, consider the following process: Let `S(N)` denote the sum of the digits of N. Take the sum of the digits of `S(N)`. Repeat this operation until a single-digit number is obtained. We call the number of times we performed the above process until we obtained a single-digit number the "depth" of N. For example, the depth of 49 is `S(49)=13 -> S(13)=4`, the operation was performed twice (and the depth of 45 is 1).

  a) Prove that for every number N there is indeed a finite depth, that is, a single-digit number is always obtained at some stage of the process.

  b) Let `x(n)` denote the minimum number (with the smallest value) with depth N. Find the remainder of `x(5776)` when divided by 6. Justify your answer!

  c) Find the remainder of the number `x(5776) - x(5708)` when divided by 2016. Justify your answer!

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Induction (Mathematical Induction) Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence
  Sources:
  • Gillis Mathematical Olympiad, 2015-2016 Question 3