Let , (where ). For any given integer , consider a graph with vertices that contains a Hamiltonian cycle and has more than edges. For which lengths must the graph necessarily contain a cycle of length ?

Let be a given integer, . Consider a graph with vertices satisfying the condition: for any two non-adjacent vertices and in graph , the sum of their degrees must satisfy . Please answer the following questions and prove your conclusions.

(1) Suppose the length of the longest path in graph is satisfying the inequality , does graph necessarily contain a cycle of length ? (The length of a path or cycle refers to the number of edges that make up the path or cycle.)

(2) For the case where and graph is connected, can we determine that the length of the longest path in graph , ?

(3) For the case where , is it necessary for graph to have a path of length (i.e., a Hamiltonian path)?

Given sets , , if a positive integer leaves a remainder (the smallest non-negative remainder) that belongs to when divided by 19, then that positive integer is called an number. If a positive integer leaves a remainder that belongs to when divided by 19, then that positive integer is called a number.
(1) For what positive integer , among all its positive divisors, are the numbers of divisors and divisors equal?
(2) For which positive integers , are the numbers of divisors less than the numbers of divisors? For which positive integers , are the numbers of divisors greater than the numbers of divisors?

Find all functions such that for all , we have .

Let be a set of 2025 positive real numbers. For a subset , define as the median of when all elements of are arranged in increasing order, with the convention that . Define
Find the smallest real number such that for any set of 2025 positive real numbers, the following inequality holds:
where denotes the largest element in .

Ten monkeys have 60 bananas. Each monkey has at least one banana and any two monkeys have different amounts of bananas.
Prove that any six monkeys can distribute their bananas between others such that all 4 remaining monkeys have the same amount of bananas.

The Principle of Inclusion-Exclusion (PIE): Counting Overlapping Sets

The Principle of Inclusion-Exclusion (PIE) is a powerful combinatorial technique used to calculate the size of the union of overlapping sets. It corrects for overcounting by systematically adding and subtracting the sizes of various intersections.

1. The Basic Form of Inclusion-Exclusion

For two finite sets and , the size of their union is given by:


This formula accounts for the fact that elements in the intersection are counted twice—once in and once in —so we subtract the overlap.

For three sets , , and :


The pattern alternates between adding and subtracting the sizes of intersections of increasing complexity.

2. The General Formula of Inclusion-Exclusion

For finite sets , the size of their union is:


In words:

• Add the sizes of all individual sets.
• Subtract the sizes of all pairwise intersections.
• Add the sizes of all three-way intersections.
• Continue this pattern, alternating signs, until you reach the intersection of all sets.

3. Proof of the Inclusion-Exclusion Formula

Consider any element that belongs to at least one of the sets. We need to ensure each element is counted exactly once.

Define:


In the PIE formula:

• Each element is counted once for every set it belongs to.
• Each pairwise intersection removes elements counted twice.
• Each triple-wise intersection adds back elements removed too often.
• This alternation continues, ensuring each element is counted exactly once.

By summing over all elements, the formula holds by correcting these overcounts systematically.

4. Example: Counting Multiples

Find how many integers between and are divisible by , , or .

Let:

• 
• 
• 

Step 1: Count each set:


Step 2: Subtract pairwise intersections:


Step 3: Add the triple intersection:


Step 4: Apply PIE:


Thus, there are numbers between and divisible by , , or .

5. Applications of Inclusion-Exclusion

The principle of inclusion-exclusion has broad applications:

• Counting Problems: Solving problems involving overlapping categories.
• Probability Theory: Finding the probability of the union of events.
• Combinatorics: Counting permutations with restrictions.
• Set Theory: Analyzing intersections and unions of large collections.
• Graph Theory: Counting subgraphs and other combinatorial objects.

6. Advanced Generalization of Inclusion-Exclusion

For an arbitrary measure space and measurable sets , the inclusion-exclusion formula generalizes to:


This allows the principle to be applied to continuous spaces and probability measures.

7. Derangements and Inclusion-Exclusion

A classical application of PIE is counting derangements—permutations where no object appears in its original position.

Let represent the number of derangements of objects. Using PIE:


where the summation alternates signs based on how many fixed points to exclude.

8. Conclusion

The Principle of Inclusion-Exclusion is a fundamental tool in combinatorics, allowing precise counting of complex unions by carefully handling overlaps. It applies across multiple domains, including probability theory, graph theory, and set theory, providing a versatile method for solving intricate counting problems.

9. Principle of Inclusion-Exclusion Video by Sohil Rathi


References

• R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Edition (Addison-Wesley, 1994).
• I. Anderson, A First Course in Discrete Mathematics (Springer, 2001).
• Wikipedia: Inclusion-Exclusion Principle.
• AoPS: Principle of Inclusion-Exclusion.

Find all functions such that, for all integers that satisfy , the following equality holds:

(Here denotes the set of integers.)

Proposed by Liam Baker, South Africa