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

• Donkey in the Middle

  Avi, Beni, and Gadi played "Donkey in the Middle" - at any moment someone stands in the middle and tries to catch a ball that the other two are passing. If he succeeds, one of the other two replaces him.
  After the game, it turned out that Avi stood in the middle 8 times, Beni 4 times, and Gadi 13 times.
  Who was the first and who was the last to stand in the middle?

  Topics:

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

• Question

  The numbers `1,2,3,4,5` are written at the vertices of a regular pentagon, with each number at exactly one vertex. A trio of vertices is called successful if it forms an isosceles triangle, where the number at its apex is greater than the numbers at the other two vertices, or where the number at its apex is smaller than the numbers at the other two vertices.

  Find the maximum number of successful trios that can exist.

  Show hint

  Log in here to receive the hint
  Topics:

  Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Geometry -> Plane Geometry -> Symmetry Minimum and Maximum Problems / Optimization Problems

• The Beaver and the Mole

  There is a plot of land in the shape of a square `4 times 4` divided into cells of `1 times 1`. The beaver wants to build a house on it that occupies 4 cells, which from a top-down view looks like this:

  

  The mole wants to disturb him. For this purpose, it can dig holes, each of which occupies one cell. It is impossible to build on the cells that have become holes. What is the smallest number of holes the mole needs to dig so that the beaver cannot build the house?

   

  Topics:

  Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Colorings Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 3-4 Question 4
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 5-6 Question 2

• Doughnuts

  Ayala, Benny, Gili, Danny, and Hadas received a package of doughnuts containing

  • 10 doughnuts with dulce de leche
  • 8 doughnuts with peanut butter
  • 9 doughnuts with chocolate
  • 11 with strawberry jam

  Each of them has their favorite type of doughnut.

  • Ayala ate 5 doughnuts of her favorite type
  • Benny ate 6 doughnuts of his favorite type
  • Gili ate 7 doughnuts of her favorite type
  • Danny ate 8 doughnuts of his favorite type
  • Hadas ate 9 doughnuts of her favorite type

  After that, they were left with 3 doughnuts of different types. What is each of their favorite type of doughnut?

  Topics:

  Arithmetic Algebra -> Word Problems Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 3-4 Question 5

• 6 on the Board

  The number 6 is written on the board. At each step, you can add the digit 6 to the end of the number (so that it is the units digit,) or replace the number with the sum of its digits.
  Which numbers can be obtained in this way? Describe the entire set of numbers and explain why there are no more

  Topics:

  Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 Combinatorics -> Induction (Mathematical Induction) Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Algebra -> Sequences Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 3-4 Question 6
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 5-6 Question 5

• Another Donkey in the Middle

  Avi, Beni, and Gadi played "Donkey in the Middle" - at any given moment, someone is in the middle, trying to catch a ball that the other two are passing to each other.
  If he succeeds, one of the other two replaces him. After the game, Avi said that he was in the middle 8 times,
  Beni said he was in the middle 4 times, and Gadi forgot how many times he was in the middle.
  They also remember that Beni was the last one in the middle. Describe all the possibilities for the number of times Gadi was in the middle,

  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Final, Grades 5-6 Question 3

• Ten-Digit Number

  Yael writes ten-digit numbers in whose decimal representation each of the digits `0, 1, 2, 3, 4, 5, 6, 7, 8, 9` appears exactly once.
  In the numbers that Yael writes, the difference between any two adjacent digits is at least 2. What is the smallest number Yael can write?
   

  Topics:

  Number Theory Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 3-4 Question 3
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 5-6 Question 1

• Numbers with Ascending Digits

  Miri writes down all the numbers in whose decimal representation only the digits `1, 2, 3, 4, 5` appear.
  (Not all digits have to appear) and all the digits that appear are written in ascending order (e.g., 135 or 1234 or 5 but not 153 and not 1223).
  How many numbers will Miri write down?

  Topics:

  Combinatorics
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 3-4 Question 7

• Orange Star of David

  The area of the blue triangle is equal to 1. Calculate the area of the orange Star of David:

  

  Topics:

  Geometry -> Area Calculation Geometry -> Plane Geometry -> Triangles Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 5-6 Question 3

• More Game Cubes

  Aviv has game cubes, where two opposite faces of each are painted red and the rest are blue.
  Aviv glued together a `3 xx 3 xx 3` cube from the game cubes. Then his friend Kfir came and calculated the total red area on the surface of the large cube.
  What is the largest result Kfir can get?

  Topics:

  Geometry -> Solid Geometry / Geometry in Space Combinatorics -> Combinatorial Geometry Minimum and Maximum Problems / Optimization Problems Combinatorics -> Colorings
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 5-6 Question 6