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

• The Grasshopper

  Consider an infinite grid of squares. A grasshopper sits on one of the squares. The grasshopper can jump two squares in any horizontal or vertical direction, and it can jump to the adjacent square diagonally. Can the grasshopper ever reach a square that is adjacent to its starting square by a side?

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Combinatorics -> Colorings -> Chessboard Coloring
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 2

• The Magic Octopuses

  In the magic sea live octopuses who can talk. Each octopus either always tells the truth or always lies. One day
  the following conversation took place between four octopuses, Avi, Benny, Gidi, and Danny:

  
  Avi: I am a green octopus
  Benny: I am not green
  Gidi: All green octopuses are liars
  Danny: Only a green octopus can be a liar

  
  It is known that only one of these four is a liar, and the rest are truthful.
  a. Who is the liar among the four friends? Explain!
  b. Is it possible to know what his color is?

  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Logic -> Truth-tellers and Liars Problems
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 6
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 5-6 Question 4

• Log of Wood

  You have a very long log of wood. Can you measure exactly one meter from it, if you have for this purpose:
  а. A stick with a length of one and a half meters and another stick with a length of 40 centimeters,
  б. A stick with a length of one and a half meters and another stick with a length of 30 centimeters,

  Assuming you have no other measuring tools? Explain!

  Topics:

  Combinatorics -> Invariants Algebra -> Word Problems Logic -> Reasoning / Logic Arithmetic -> Division with Remainder
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 7
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 5-6 Question 2

• Quiz

  In a class of 25 students, a quiz was given consisting of 7 questions. Prove that at least one of the following two statements is true:

  1. There is a student who solved an odd number of questions.
  2. There is a question that was solved by an even number of students.
  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 5-6 Question 5

• Pumbaa and the Candies

  Pumbaa has 11 chocolate candies and 13 toffee candies. Each time he can eat either two candies of different types,
  or three candies of the same type. What is the largest number of candies that Pumbaa can eat according to these rules?

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Invariants Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 5-6 Question 6

• Multiplying Rooks

  Given an `n times n` board where each square contains either 1 or -1.

  Define the value of an arrangement of rooks on the board as the product of the numbers on their squares.

  Is the sum of the values of all arrangements necessarily divisible by 4?

  Also given `n >= 4`

  (Solution for verification: yes or no)

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures

• Cutting

  What is the largest number of rectangles of size `2 times 5`  that can be cut from a `9 times 9` square?

  Topics:

  Geometry -> Area Calculation Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Stage A, Grades 3-4 Question 1
  • Young Mathematician Olympiad, 2018-2019, Stage A, Grades 5-6 Question 1

• Digit Sum - 9

  How many numbers in the range from 1 to 500 have a digit sum of 9?

  Topics:

  Number Theory Arithmetic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Stage A, Grades 3-4 Question 2

• Circle and Three Points

  A circle is drawn on the board, and three points are marked on it in the following colors (clockwise): green, blue
  and red. Jonathan is playing the following game – in each step he can do one of the following:
  a) Choose two adjacent points with different colors and draw a point between them in one of these two colors
  only.
  b) Choose two adjacent points with identical colors and draw a point between them in any color.
  c) Choose three adjacent points where at least two of them are the same color, and erase the middle one.

  Can Jonathan reach a state where there are three points left on the board in the following colors (clockwise): blue, green, red? Justify your answer.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Invariants Combinatorics -> Colorings
  Sources:
  • Gillis Mathematical Olympiad, 2015-2016 Question 4

• Sum of Products of Digits

  Let `P(n)` denote the product of the digits of the number `n`. For example, `P(1948) = 1 * 9 * 4 * 8 = 288`.

  A.

  Calculate `P(1) + P(2) + P(3) + ... + P(2016)`

  B.

  Find the maximum value of `{P(n)} /n`, where `2016 <= n <= 5777`.

  (Solution format: "x, y/z" where y/z is an unreduced fraction. For example "10000, 35/100")

  Show hint

  Log in here to receive the hint
  Topics:

  Arithmetic Algebra -> Word Problems Combinatorics -> Number Tables Number Theory -> Division
  Sources:
  • Gillis Mathematical Olympiad, 2016-2017 Question 2