Everybody has 66 balls

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Everybody has 66 balls

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 CTST P5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1500 posts

#1 h Mar 6, 2025, 1:46 AM • 2 Y

Y by Marcus_Zhang, MS_asdfgzxcvb

There are $2025$ people and $66$ colors, where each person has one ball of each color. For each person, their $66$ balls have positive mass summing to one. Find the smallest constant $C$ such that regardless of the mass distribution, each person can choose one ball such that the sum of the chosen balls of each color does not exceed $C$ .

This post has been edited 2 times. Last edited by YaoAOPS, Mar 6, 2025, 1:51 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

841 posts

#2 h Mar 6, 2025, 12:55 PM • 1 Y

Y by MS_asdfgzxcvb

The answer is $248/517,$ I think it is harder than P6
Prove is using greedy algorithm while construction is just $22$ $32/2068$ and $44$ $31/2068.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7322 posts

DottedCaculator

#3 h Mar 7, 2025, 4:29 PM • 2 Y

Y by MS_asdfgzxcvb, mpcnotnpc

The answer is $\frac{248}{517}$ . The construction is having $22$ colors of mass $\frac{248}{517}\frac1{31}$ , and $44$ colors of mass proportional to $\frac{248}{517}\frac1{32}$ . At least one color must have a total mass of $\frac{248}{517}$ .

For the bound, order the colors, then for each color, pick the smallest ball remaining assuming the total mass of the color selected does not exceed $\frac{248}{517}$ , and move to the next color otherwise. For any color, replacing the balls picked with the average of all the masses of the balls picked does not change the procedure. Then, replacing the remaining balls of that color of people who have not been selected yet with the common value of the balls of that color picked decreases the masses of balls, and the procedure still continues as normal. At the end, each person has identical ball distributions. Let these masses be $m_1$ , $m_2$ , $\ldots$ , $m_{66}$ . Then, the procedure works if $\sum_{i=1}^{66}\left\lfloor\frac{\frac{248}{517}}{m_i}\right\rfloor\geq2025$ . Let $a_i=\left\lfloor\frac{\frac{248}{517}}{m_i}\right\rfloor$ . Then, $m_i>\frac{248}{517(a_i+1)}$ , so $\sum_{i=1}^{66}\frac1{a_i+1}<\frac{517}{248}$ . It suffices to show that this is impossible when $\sum_{i=1}^{66}(a_i+1)\leq2024+66$ , which is true by smoothing as $\frac{517}{248}=\frac{22}{31}+\frac{44}{32}$ is the optimal lower bound when $\sum_{i=1}^{66}(a_i+1)\leq2024+66$ .

Therefore, $C=\boxed{\frac{248}{517}}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

356 posts

#5 h Mar 26, 2025, 10:20 PM

Y by

To paraphrase Titu, it's the first nontrivial case that counts. Maybe it counts a bit more for people who can do algebra though.

Label the colors by $1, \ldots, 66$ . The answer is $C = \tfrac{248}{517}$ , which is the optimal constant for $22$ colors with all balls weighing $32\lambda$ and $44$ colors with all balls weighing $31\lambda$ for some $\lambda$ .

We claim that for any configuration of colors, the greedy algorithm taking the smallest valid weighed ball of smallest color, without any total weight exceeding $C$ until possibly color $66$ , works. To see this, suppose that for each $j$ , exactly $k_j$ people choose balls of color $j$ . In this case, the average weight of the selected balls for each color $j \le 65$ is greater than $\tfrac{C}{1 + k_j}$ . To show that the algorithm does not fail at color $66$ . Observe that the color $66$ balls of the remaining people all have weight less than
$\epsilon = 1 - \frac{C}{1 + k_1} - \ldots - \frac{C}{1 + k_{65}}.$ Since $f(x):=\tfrac{1}{x}$ is convex, the restriction
$\big((k_1 + 1) + \ldots + (k_{65} + 1)\big) + k_{66} = 2090$ implies
$\left(\frac{1}{1 + k_1} + \ldots + \frac{1}{1 + k_{65}}\right) + \frac{1}{k_{66}} \ge 22 \cdot \frac{1}{31} + 44 \cdot \frac{1}{32} = \frac{1}{C}$ by Karamata's inequality, which rearranges to $k_{66}\cdot \epsilon \le C$ . The conclusion follows.

This post has been edited 2 times. Last edited by Blast_S1, Mar 27, 2025, 10:48 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a