Kvant Math Problem 166

Let $A_1$ and $A_2$ be the sets of participants of the two trips, and let $B_i \subset A_i$ be the boys in the $i$-th trip.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m18s
Source on kvant.digital

Problem

  1. Students of one class went on two hiking trips in September. In the first trip, the number of boys was less than $\dfrac25$ of the total number of participants of that trip, and in the second one it was also less than $\dfrac25$. Prove that in this class boys make up less than $\dfrac47$ of the total number of students, given that each student participated in at least one of the trips.
  2. Let in the $i$-th trip ($i=1$, 2, $\ldots$, $n$) boys made up $\alpha_i$ of the total number of participants of this trip. What is the maximum fraction that boys can constitute at the general meeting of all tourists (all those who were in at least one of the $n$ trips)?

Exploration

Let $A_1$ and $A_2$ be the sets of participants of the two trips, and let $B_i \subset A_i$ be the boys in the $i$-th trip. The conditions state

$$\frac{|B_i|}{|A_i|} < \frac25 \quad \Longrightarrow \quad |B_i| < \frac25 |A_i|, \qquad i=1,2.$$

Write $G_i = A_i \setminus B_i$ for girls. Then $|G_i| > \frac35 |A_i|$.

The class is the union $A_1 \cup A_2$. Boys in the class form $B = B_1 \cup B_2$, while girls form $G = G_1 \cup G_2$.

To maximize the fraction of boys in the union, one wants to maximize $|B|$ while minimizing $|G|$. This suggests two opposing strategies: make the boys' sets disjoint to increase $|B|$, and make the girls' sets overlap as much as possible to decrease the union size. The interaction between these two constraints determines the extremal configuration.

A first naive attempt would assume proportionality is preserved under union, but this fails because overlaps affect boys and girls asymmetrically.

The key structural quantity is the relationship between overlaps:

$$|A_1 \cup A_2| = |B| + |G_1 \cup G_2|.$$

Thus the problem reduces to controlling how small $|G_1 \cup G_2|$ can be relative to the constraints on $|G_i|$.

The most delicate point is whether both trips can simultaneously achieve their maximal allowed boy fractions while still allowing maximal overlap among girls. This determines whether the bound $4/7$ is tight.

Problem Understanding

This is a Type A problem for part 1 and a Type C optimization problem for part 2.

We are given two trips where boys form less than $2/5$ of each participant set, and every student appears in at least one trip. We must bound the proportion of boys in the union.

The central difficulty is that overlap between the two trips is unrestricted, and must be exploited adversarially to maximize the global boy fraction.

The claimed bound is $4/7$ for two trips, and for $n$ trips with given local proportions $\alpha_i$, we must determine the maximal possible global proportion.

For part 1, the correct bound is

$$\boxed{\frac47}.$$

For part 2, the answer will depend on a balance between maximizing overlap of girls and distributing boys across trips.

Proof Architecture

Let $A_i$, $B_i$, $G_i$ be as above.

We will use the identity

$$|A_1 \cup A_2| = |B| + |G_1 \cup G_2|.$$

We will prove that in the extremal configuration for maximizing $|B|/|A_1 \cup A_2|$, the following hold simultaneously: boys are disjoint across trips, and girls form nested sets with maximal overlap.

A second lemma identifies that $|G_1 \cup G_2|$ is minimized when one of $G_1, G_2$ contains the other.

The hardest step is proving that these two extremal tendencies can be simultaneously realized without violating the constraints $|B_i| < \frac25 |A_i|$.

For part 2, we generalize this structure to $n$ trips, identifying the optimal balancing condition on the sizes $|A_i|$.

Solution

Let $A_i$ be the set of participants of the $i$-th trip, with $B_i \subset A_i$ the boys and $G_i = A_i \setminus B_i$ the girls. The assumptions give

$$|B_i| < \frac25 |A_i|, \qquad |G_i| > \frac35 |A_i|, \qquad i=1,2.$$

We write $B = B_1 \cup B_2$ and $G = G_1 \cup G_2$. Since the class consists of all participants in at least one trip,

$$|A_1 \cup A_2| = |B| + |G_1 \cup G_2|.$$

To maximize the fraction of boys, we maximize $|B|$ and minimize $|G_1 \cup G_2|$ under the constraints.

For boys, the union satisfies

$$|B| = |B_1| + |B_2| - |B_1 \cap B_2| \le |B_1| + |B_2|.$$

Thus the maximum is achieved when $B_1$ and $B_2$ are disjoint, so $|B| = |B_1| + |B_2|$.

For girls,

$$|G_1 \cup G_2| = |G_1| + |G_2| - |G_1 \cap G_2| \ge \max(|G_1|, |G_2|),$$

and equality is achieved when one girl set is contained in the other.

We now construct an extremal configuration consistent with both optimizations. Assume $|G_1| \ge |G_2|$ and take $G_2 \subset G_1$. Then

$$|G_1 \cup G_2| = |G_1|.$$

Choose $B_1$ and $B_2$ disjoint, and realize the maximal allowed sizes

$$|B_i| = \frac25 |A_i|, \qquad |G_i| = \frac35 |A_i|.$$

Let $|A_2| = x |A_1|$ with $0 < x \le 1$. Then

$$|B| = \frac25 |A_1| + \frac25 |A_2| = \frac25 |A_1|(1+x),$$

and

$$|G_1 \cup G_2| = |G_1| = \frac35 |A_1|.$$

Hence

$$|A_1 \cup A_2| = \frac25 |A_1|(1+x) + \frac35 |A_1| = |A_1|\left(1 + \frac25 x\right).$$

Therefore the global fraction of boys is

$$R(x) = \frac{\frac25(1+x)}{1 + \frac25 x} = \frac{2(1+x)}{5+2x}.$$

We maximize this on $0 < x \le 1$. Differentiating,

$$R'(x) = \frac{2(5+2x) - 2(1+x)\cdot 2}{(5+2x)^2} = \frac{10+4x-4-4x}{(5+2x)^2} = \frac{6}{(5+2x)^2} > 0.$$

Thus $R(x)$ increases with $x$, and its maximum occurs at $x=1$, giving

$$R_{\max} = \frac{2(2)}{5+2} = \frac47.$$

Since all inequalities in the assumptions are strict, the obtained value cannot be attained, only approached, hence the fraction of boys in the class is strictly less than $\frac47$.

This completes the proof. ∎

For part 2, let $A_i$ be the size of the $i$-th trip, and assume again that boys form the largest possible union while girls overlap as much as possible. As in the two-trip case, the extremal configuration occurs when all girl sets are nested, so that the union of girls has size equal to the largest of the $G_i$.

Thus

$$|A_1 \cup \cdots \cup A_n| = |B| + \max_i |G_i|.$$

To maximize $|B|$ and minimize $\max_i |G_i|$, we take $|B_i| = \alpha_i |A_i|$ and $|G_i| = (1-\alpha_i)|A_i|$, and choose the scaling of $|A_i|$ so that all $|G_i|$ are equal:

$$(1-\alpha_i)|A_i| = C.$$

Then

$$|A_i| = \frac{C}{1-\alpha_i}, \qquad |B_i| = \frac{\alpha_i}{1-\alpha_i} C.$$

Hence

$$|B| = C \sum_{i=1}^n \frac{\alpha_i}{1-\alpha_i}, \qquad \max_i |G_i| = C.$$

Therefore the maximal possible global fraction is

$$\boxed{\frac{\sum_{i=1}^n \frac{\alpha_i}{1-\alpha_i}}{1 + \sum_{i=1}^n \frac{\alpha_i}{1-\alpha_i}} }.$$

Verification of Key Steps

The crucial step in part 1 is the simultaneous realization of two extremal principles: disjointness of boys and maximal nesting of girls. The construction does not force any overlap constraint between boys and girls beyond set membership, so these two conditions are compatible.

The monotonicity of $R(x)$ was derived directly and shows that imbalance in trip sizes never improves the boy fraction; the worst case occurs when the two trips are balanced.

In part 2, the key step is the reduction of the union of girls to a single maximal set. Any attempt to overlap all girl sets more than this would require one set to exceed its prescribed size, violating $|G_i| = (1-\alpha_i)|A_i|$ at extremality.

Alternative Approaches

An alternative method for part 1 uses a linear programming formulation in terms of the eight intersection variables $B_1,B_2,B_{12},G_1,G_2,G_{12}$, reducing the problem to a two-variable optimization. This approach yields the same rational bound but is less transparent structurally.

For part 2, one can also derive the result via convexity arguments applied to the function $x \mapsto x/(1-x)$, interpreting each trip as contributing a weighted density to a common overlap structure.