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

• Colorful Street

  Along the street are 16 houses, in red, blue, and green. There is at least one house of each color. No two adjacent houses are of the same color.
  Between any two blue houses there is a red house. Between any two green houses there is a blue house and a red house.
  What is the largest possible number of green houses?
  Note: The street is straight, all houses are located on one side of the street.

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 3-4 Question 6

• Colorful Street 2

  There are 15 houses along the street, colored red, blue, and green. There is at least one house of each color.
  Between any two blue houses there is a red house. Between any two green houses there is a blue house.
  What is the largest possible number of green houses?
  Note: The street is straight, and all houses are located on one side of the street.

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 5-6 Question 5
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 7-8 Question 6

• Magic Fractions

  Let's call a fraction magic if both its numerator and denominator are less than 10. For example, the fraction `1/9` is considered magic, the fraction `6/8` is also magic, but the fraction `3/14` is not magic.
  How many magic fractions are there that are greater than one-half and less than 1?

  Note: For the purpose of this question, `2/3` and `4/6` are considered different fractions.

  Topics:

  Arithmetic -> Fractions Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 5-6 Question 6

• Star of David in a Circle

  Eight points are given on a circle. In how many different ways can a Star of David be drawn with vertices at these points?

  

  Note: A Star of David is a figure obtained when two triangles intersect and their sides create exactly 6 intersection points.

  Topics:

  Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 7-8 Question 4

• The Units Digit

  Miriam has eight cards with consecutive three-digit numbers. The units digit of the smallest number is 1,
  the units digit of the largest number is 8. Miriam arranged the cards in a row such that the first number is divisible by 2,
  the second number is divisible by 3, the third number is divisible by 4, and so on until the eighth number which is divisible by 9.
  What is the units digit of the number divisible by 7?

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grade 9 Question 6

• Weighing Coins

  Given are seven outwardly identical coins; four are genuine and three are counterfeit. The three counterfeit coins are of identical weight, as are the four genuine coins.
  It is known that a counterfeit coin is lighter than a genuine coin. In one weighing, you can select two groups of coins and determine which is lighter, or if they have the same weight.
  How many weighings are needed to locate at least one counterfeit coin?

  Topics:

  Logic -> Reasoning / Logic Algorithm Theory -> Weighing Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems
  Sources:
  • Gillis Mathematical Olympiad, 2019-2020 Question 1

• Mathematical Conference

  202 participants from three countries attended a mathematical conference: Israel, Greece, and Japan.
  On the first day, every pair of participants from the same country shook hands. On the second day, every pair of participants
  where one was Israeli and the other was not Israeli shook hands. On the third day, every pair of participants where one
  was Israeli and the other was Greek shook hands. In total, 20200 handshakes occurred. How many
  Israeli participants were at the conference?

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory Combinatorics Algebra -> Word Problems Algebra -> Equations -> Diophantine Equations
  Sources:
  • Gillis Mathematical Olympiad, 2019-2020 Question 2

• Children's Clubs

  In a kindergarten, there are three clubs: Judo, Agriculture, and Mathematics. Each child participates in exactly one club, and each club has at least one participant. The total number of children in the kindergarten is 32. On Friday, the kindergarten teacher gathered 6 children to tidy up the classroom. The teacher counted and found that exactly half of the Judo club members, a quarter of the Agriculture club members, and an eighth of the Mathematics club members volunteered for the task. How many students are in each club?

  Show hint

  Log in here to receive the hint
  Topics:

  Algebra -> Word Problems Logic -> Reasoning / Logic Arithmetic -> Fractions Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Number Theory -> Division
  Sources:
  • Gillis Mathematical Olympiad, 2018-2019 Question 1

• Drawing of a Relation

  Given a 5x5 grid divided into 1x1 squares. Two squares are considered related if they are in the same row or column, and the distance between their centers is 2 or 3.
  For example, in the drawing, all the squares related to the red square are marked in gray. Sammy receives a blank grid and wants to mark as many squares as possible such that no two of them are related. What is the maximum number of squares he can mark?
  

  Show hint

  Log in here to receive the hint
  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry
  Sources:
  • Gillis Mathematical Olympiad, 2018-2019 Question 2

• Equality in Stages

  The numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 are written on the board, and David is supposed to change them in stages. At each stage, David is allowed to choose two numbers and change them by 1, that is, to add 1 to both, subtract 1 from both, or add 1 to one and subtract 1 from the other.

  Can David, after a number of stages, reach a situation where all the numbers on the board are equal? If so, show an example, and if not, explain your answer in detail.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Invariants Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Grossman Math Olympiad, 2017, Juniors Question 3