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

  A box contains `14` black socks and `14` white socks. Apart from color, all socks in the box are identical. Danny wants to take a pair of socks from the box without looking inside. How many socks does he need to take out to:

  A. Certainly have any pair of socks,

  B. Certainly have a pair of black socks?

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  On the circle, there are blue and red points. It is allowed to add a red point and change the colors of its neighboring points or remove a red point and change the colors of its neighboring points (it is not allowed to leave fewer than 2 points on the circle). Prove that it is impossible to move, using only these operations, from a circle with two red points to a circle with two blue points.
  K. Kaznvosky

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Algebra Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Set Theory Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Colorings -> Chessboard Coloring
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 1

• Question

  An `N×N` table is filled with numbers such that all rows are distinct (differing in at least one position). Prove that it is possible to delete a column such that in the remaining table all rows are also distinct.
  (a) Hint

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Proof and Example -> Proof by Contradiction
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 2

• Question

  Let a₁, a₂, ..., a₁₀₁ be a permutation of 2, 3, 4, ..., 102. Find all permutations such that a_i is divisible by i for all i.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 3

• Question

  A tourist arrived at an island inhabited by truth-tellers and liars. Truth-tellers always tell the truth, and liars always lie. The tourist is traveling with a local guide, and they see a farmer working in the field. The tourist asked the guide to find out if this man is a truth-teller or a liar. The guide spoke with the farmer and then said to the tourist: "He said that he is a truth-teller."

  A. What can be deduced about the farmer?

  B. What can be deduced about the guide?

  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Logic -> Truth-tellers and Liars Problems
  Sources:
  • problems.ru web site

• Question

  On Alice's birthday, her friends are asked how old she is. The Mad Hatter says that Alice's age is greater than `11`, and the Cheshire Cat says that her age is greater than `10`. It is known that exactly one of them is wrong. How old is Alice now? Explain!

  Show hint

  Log in here to receive the hint
  Topics:

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

• Question

  One day, Harry Potter found a strange notebook in which the following one hundred sentences were written:

  "In this notebook, there is exactly one sentence that is false."

  "In this notebook, there are exactly two sentences that are false."

  "In this notebook, there are exactly three sentences that are false."

  ...

  "In this notebook, there are exactly one hundred sentences that are false."

  Are there any true sentences in this notebook, and if so, how many? Justify your answer!

  Topics:

  Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction Logic -> Truth-tellers and Liars Problems Logic -> Reasoning / Logic -> Paradoxes

• Question

  Three hedgehogs have three pieces of cheese weighing `5`, `8`, and `11` grams. A fox offers to help the hedgehogs divide the cheese equally. The fox can bite off one gram from each of two cheese pieces of its choice. Can the fox, using these actions, reach a state where it leaves the three hedgehogs with equal pieces of cheese?

  Topics:

  Arithmetic Algebra -> Word Problems Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Number Theory -> Division
  Sources:
  • problems.ru web site

• Question

  There are `85` balloons in a room, red and blue. It is known that:

  - At least one of the balloons is red,

  - In any pair of balloons we take, at least one of the balloons must be blue.

  How many red balloons are in the room?

  Topics:

  Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  Is it possible to tile a `5xx5` board with dominoes?

  Note: The size of a board square matches the size of a domino square.

  Topics:

  Combinatorics -> Combinatorial Geometry Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Colorings -> Chessboard Coloring