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

  Every person who ever lived on Earth performed a certain number of handshakes (including 0). Prove that the number of people who performed an odd number of handshakes is even.

  Topics:

  Combinatorics -> Double Counting Combinatorics -> Graph Theory Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction

• Question

  The numbers `1`, `2`, `3`, ..., `8` are written on the vertices of a cube. Prove that there exists an edge of the cube such that the difference between the numbers at its endpoints is at least `3`.

  Topics:

  Geometry -> Solid Geometry / Geometry in Space Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction

• Question

  The game takes place on an infinite plane. One player moves the wolf, and another player moves K sheep. After the wolf's move, one of the sheep makes a move, then the wolf again, and so on. In one move, the wolf or a sheep cannot move more than one meter in any direction. Can the wolf always catch at least one sheep, regardless of the initial positions?

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Geometry -> Plane Geometry Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Minimum and Maximum Problems / Optimization Problems
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 11-12 Question 2

• Question

  K friends simultaneously learn K pieces of news (one piece of news per friend). They begin to phone each other and exchange news. Each call lasts one hour. How long will it take for all friends to know all the news? Consider the cases:
  (a) (5 points) K=64
  (b) (10 points) K=55
  (c) (12 points) K=100
  (a) Answer

  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 11-12 Question 4

• Question

  On an infinite grid of squares, 6 squares are marked, as in the diagram. How many squares contain stones? In one move, a stone can be removed if it has no adjacent stone above and to its right; then, two stones are placed in the squares above and to the right of the removed stone. Can we remove all stones from the marked squares if the initial state is:
  A. (8 points) All marked squares.
  B. (8 points) Only the bottom-left marked square.

  O 
  O O 
  O O O

  M. Konvitz'

  Topics:

  Combinatorics -> Invariants Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 11-12 Question 5

• Question

  A box contains pencils in three colors: red, green, and blue, totaling `20` pencils. There are `6` times more blue pencils than green pencils. There are fewer red pencils than green pencils. How many red pencils are in the box?

  Topics:

  Arithmetic Algebra -> Inequalities Algebra -> Word Problems Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures

• Question

  A grasshopper can jump `80` centimeters forward or `50` centimeters backward. Can the grasshopper move away from its starting point in fewer than `7` jumps to a distance of exactly one meter and `70` cm?

  Show hint

  Log in here to receive the hint
  Topics:

  Arithmetic Number Theory -> Chinese Remainder Theorem Algebra -> Word Problems Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Algebra -> Equations -> Diophantine Equations

• Birds and Seeds

  Nine identical birds eat less than `1001` seeds for lunch, and ten such birds eat more than `1100` seeds for lunch. How many seeds does one bird eat for lunch?

  Topics:

  Algebra -> Inequalities Algebra -> Word Problems Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Number Theory -> Division

• Question

  Find all natural numbers with the following property: when divided by 7, their remainder is equal to their quotient.

  Topics:

  Number Theory Algebra -> Inequalities Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Arithmetic -> Division with Remainder

• Question

  Find all two-digit numbers `A` such that the square of the sum of its digits is equal to the sum of the digits of `A^2`.

  Topics:

  Number Theory Arithmetic Algebra -> Inequalities Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures