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
Danny flips a coin `3` times and records the results in a row. How many different possibilities are there for this row?
Topics:Combinatorics -> Product Rule / Rule of Product -
Question
In a soccer team, a captain and a vice-captain are chosen. In how many different ways can this selection be made?
Note: A soccer team always has `11` players.
Topics:Combinatorics -> Product Rule / Rule of Product -
Question
In space, there are 30 non-degenerate vectors. Prove that there are at least 2 such that the angle between them is no greater than 45 degrees.
A. TulpigoSources:Topics:Geometry -> Trigonometry Geometry -> Spherical Geometry Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry -> Angle Calculation Geometry -> Vectors- Tournament of Towns, 1979-1980, Main, Spring Question 4
-
Question
In Wonderland, there are `n` cities, and every two of them are connected by a road. The roads meet only in the cities (there are no junctions outside the cities). A wicked magician wants to turn all the roads into one-way streets in such a way that if you leave any city, you can't return to it anymore.
a. Prove that the wicked magician can do this.
b. Prove that there exists a city from which one can reach any other city, and that there exists a city from which it is impossible to leave at all.
c. Prove that there exists a path that passes through all the cities and there is only one such path.
-
Question
Let M be a set of points in the plane. O is called a partial center of symmetry if it is possible to remove a point from M such that O is a regular center of symmetry of what remains. How many partial centers of symmetry can a finite set of points in the plane have?
V. PrasolovSources:Topics:Combinatorics -> Combinatorial Geometry Proof and Example -> Constructing an Example / Counterexample Geometry -> Plane Geometry -> Symmetry- Tournament of Towns, 1980-1981, Spring, Main Version, Grades 9-10 Question 2 Points 7
-
Wolf and sheep
The game takes place on an infinite plane. One player moves the wolf, and the other – 50 sheep. After a move by the wolf, one of the sheep makes a move, then the wolf again, and so on. In one move, the wolf or sheep moves no more than one meter in any direction. Can the wolf always catch at least one sheep, regardless of the initial configuration?
Sources:Topics:Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Combinatorics -> Game Theory Proof and Example -> Constructing an Example / Counterexample- Tournament of Towns, 1980-1981, Spring, Main Version, Grades 9-10 Question 5 Points 16
-
Question
In a country there are `100` cities, and from each city `4` roads lead out (a road can only start or end in a city). How many roads are there in this country?
Sources: -
Question
In a foreign country, every phone number has `7` digits, and the first digit is always different from `0`. What is the maximum number of phone numbers that can exist in that country?
Sources: -
Question
We call a number nice if it consists only of odd digits. How many four-digit nice numbers exist?
Sources: -
Question
In a company, there are `30` employees. The youngest is `20` years old, and the oldest is `45` years old. Is it necessarily true that there are people in this company who are the same age?
Sources:Topics:Combinatorics -> Pigeonhole Principle