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-
Government Elections
In the parliamentary elections of a certain country, a number of parties participated (the exact number is unknown). Every citizen who participated in the elections voted for one party.
For every positive integer k, let `d_k` denote the number of parties that received k or more votes. Prove that the sum `d_1+d_2+d_3+...` is equal to the number of citizens who voted in the elections.
Sources:Topics:Combinatorics -> Induction (Mathematical Induction)- Grossman Math Olympiad, 2017, Juniors Question 4
-
A Walk in the Plane
Given a Cartesian coordinate system x-y in the plane. You need to get from the point (1,0) to the point (2006,2005), where in each step you are allowed to move one unit up (in the positive direction of y) or one unit to the right (in the positive direction of the x-axis).
a. In how many different paths can the task be performed?
b. In how many different paths can the task be performed if it is forbidden at any stage to pass through a point on the line x=y?
Sources:Topics:Combinatorics -> Combinatorial Geometry Combinatorics -> Binomial Coefficients and Pascal's Triangle Geometry -> Plane Geometry -> Plane Transformations -> Congruence Transformations (Isometries) -> Reflection- Grossman Math Olympiad, 2006 Question 7
-
The Winning Exercise
Two fair dice (1-6) are rolled, and two calculations are made:
1. The sum of all 10 visible faces (5 on each die)
2. The sum of the two top faces of the dice, multiplied by 5
What is the probability that the result of the first calculation is greater than that of the second calculation?
Sources: -
Knight's Moves
A knight moves on an infinite grid. It starts at the point (0,0) and must reach
the point (5,27). Assuming it moves in the smallest number of steps required,
how many different possibilities does it have to reach this point?Sources: -
The Hidden Number
Bar and Ilan each chose an integer between 1 and 30.
Ilan: Is your number double mine?
Bar: I don't know. Is your number double mine?
Ilan: I don't know. Is your number half of mine?
Bar: I don't know. Is your number half of mine?
Ilan: I don't know.
Bar: I know what your number is.
Sources: -
Two Argue, the Third Takes
The entire class is in dispute!
42 think yes, 43 think maybe, and 36 think no.
When two people who think differently from each other meet, they both change their position to the third.
What is the minimum number of meetings that must take place until everyone agrees on the same position?
Sources: -
It's Crowded Here!
55 gears are placed on the game board in the shape of a 'pyramid':
10 gears in the bottom row, 9 gears in the row above, and so on.
In this state, the gears cannot rotate freely (convince yourself why!)
Remove gears to allow free movement.
What is the maximum number of gears that can remain on the board so that they can all rotate?
Sources:Topics:Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry- Bar-Ilan's weekly mathriddle competition, 2024 Question 10
-
Question
Eighth-grade students threw rubber balls into a box and then tried to guess how many balls had accumulated there. Five students tried to guess: 45, 41, 55, 50, 43, but no one guessed the exact amount. The guesses differed from the truth by 3, 7, 5, 7, and 2 balls (not necessarily in the same order as the guesses). How many balls were in the box?
Sources:Topics:Number Theory Arithmetic Algebra -> Word Problems Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures- Beno Arbel Olympiad, 2017, Grade 8 Question 1
-
Question
In this letter exercise, identical letters represent identical digits, different letters represent different digits, and asterisks represent any digit. Find all the digits.
`(ABCD)^2 = A B ** ** ** C D `Sources:Topics:Number Theory Arithmetic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Puzzles and Rebuses -> Reconstruct the Exercise / Cryptarithmetic- Beno Arbel Olympiad, 2017, Grade 8 Question 4
-
Question
Find the largest natural number in which all digits are distinct, and if you look at every 3 consecutive digits, you get a number divisible by 13.
Sources:Topics:Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rule by 11 Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures- Beno Arbel Olympiad, 2017, Grade 8 Question 7