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

  In the following arithmetic puzzle, different digits have been replaced by different letters, and identical digits – by identical letters. Reconstruct the puzzle:

  `BAOxxBAxxB=2002`

  Topics:

  Arithmetic Algebra -> Equations Algebra -> Inequalities Logic -> Reasoning / Logic Number Theory -> Prime Numbers -> Prime Factorization Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Puzzles and Rebuses -> Reconstruct the Exercise / Cryptarithmetic

• Question

  Given `50` distinct natural numbers between `1` and `100`. It is known that no two of these numbers sum to `100`. Is it necessarily true that one of these numbers must be a perfect square?

  Topics:

  Number Theory -> Prime Numbers Arithmetic Combinatorics -> Pigeonhole Principle Combinatorics -> Matchings Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Set Theory Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Shlomi has a chessboard and a cube whose face size is the same as the size of a square on the board. Shlomi wants to paint the faces of the cube black and white, and then roll the cube across the board so that each time the face touching the board is the same color as the square it touches. The cube is supposed to pass through each square on the board exactly once. Can Shlomi do this? Justify or provide an example.

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring

• Question

  Every evening, Yuval finishes work at a random time and arrives at a bus stop. At this station, two buses stop: number `7`, which goes to Yuval's house, and number `13`, which goes to the house of his friend Shlomi. Yuval gets on the first bus that arrives and, depending on that, goes to Shlomi's or home.

  After a while, Yuval notices that after work, he goes to Shlomi's about twice as often as he goes home. He deduced from this that bus number `13` arrives twice as frequently as bus number `7`.

  Is Yuval necessarily correct?

  Show hint

  Log in here to receive the hint
  Topics:

  Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Probability Theory Logic -> Reasoning / Logic -> Paradoxes

• Do All Horses Have the Same Color?

  Shlomi claims to have proven by induction that in every herd, all horses are the same color:

  If there is one horse, then it is the color of itself - thus we have shown that the base case of induction holds.

  For the inductive step, we number the horses from `1` to `n`. According to the inductive hypothesis, the horses numbered from `1` to `n-1` are all the same color. Similarly, the horses numbered from `2` to `n` are also all the same color. And because the colors of the horses from `2` to `n-1` are fixed and cannot change depending on how we assigned them to one group or another, then the horses `1` and `n` must also be the same color.

  Did Shlomi make a mistake in his proof? If so, find the mistake.

  Topics:

  Combinatorics -> Induction (Mathematical Induction) Proof and Example -> Constructing an Example / Counterexample Logic -> Reasoning / Logic -> Paradoxes

• Baobab

  In the following exercise, identical digits have been replaced with identical letters, and different digits have been replaced with different letters. Reconstruct the exercise.

  `BAOxxBAxxB = 2002`

   

   

   

   

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Logic -> Reasoning / Logic Number Theory -> Prime Numbers -> Prime Factorization Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Puzzles and Rebuses -> Reconstruct the Exercise / Cryptarithmetic

• Question

  A wizard summoned `20` knights, of which `10` were elves and `10` were dwarves. The wizard wants to choose a team from them to perform a secret mission. This team must contain equal numbers of elves and dwarves.

  How many possibilities are there for such a team? (Note that he cannot choose an empty team)

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Binomial Coefficients and Pascal's Triangle Set Theory

• Question

  In a certain country, there are more than 101 cities. The capital is connected by flight routes to 100 cities, and every city other than the capital is connected by flight routes to exactly 10 cities. It is given that from any city, it is possible to reach any other city (possibly not by a direct route). Prove that it is possible to close half of the flight routes leading to the capital such that the possibility of reaching any city from any other city is preserved.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example
  Sources:
  • Tournament of Towns, 1981-1982, Spring

• Triangles in a Hexagon

  How many triangles are in the picture? Count all the triangles formed by the lines.

  

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics Geometry -> Plane Geometry -> Triangles
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Stage A, Grades 3-4 Question 3

• Cats for Grandma

  Grandma Hannah has a number of cats. One day, her three grandchildren, Avi, Benny, and Gili, came to visit and tried to guess how many cats she has.

  Avi said: "Grandma has at least 7 cats",

  Benny said: "But less than 10, I think",

  Then Gili said: "Grandma Hannah has either 9, or 10, or 11 cats".

  "You are all correct!" replied the grandma

   So how many cats does she have?
   

  Show hint

  Log in here to receive the hint
  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Stage A, Grades 3-4 Question 4