1

If Jack has $25$ white balls and $63$ black balls and all black ball weight are less than $26$ grams , all white ball weight are less than $64$ grams. (All weight are in integer and some balls may have the same weight.) Prove that Jack can select some white balls and some black balls such that total weight of all white ball is equal to total weight of black balls. (Number of white and black balls are not necessary equal.)

This is from Thailand POSN Camp $2$ , $19$ June $2020$.

Oleg Farenskiy
  • 1,223
  • Balls of same colour are treated identical? – UmbQbify Jun 21 '20 at 14:00
  • I can only think, if we find all possible combinations of weights of black balls and for each combination find all possible combinations of white and black balls.. this seems unimaginable.. – UmbQbify Jun 21 '20 at 14:05
  • Is "less than 26 grams" strictly less than, or less than or equal to? – Calvin Lin Jun 21 '20 at 14:25
  • @Calvin It must be strictly less than, else you could have $63$ black balls each weighing a gram and every white ball at $64$. – lulu Jun 21 '20 at 14:31
  • 1
    @Calvin Lin, I know this is weird but, thanks.. brilliant.org has been a huge help and self-teaching and, I've seen some of your posted questions, it was was kind of shocking to see you here. – UmbQbify Jun 21 '20 at 14:41
  • @AshWhole Glad to hear that! Keep at it :). I keep an eye on the "contest-math" tag, as I love these kinds of problem. – Calvin Lin Jun 21 '20 at 15:23
  • May I ask why this question is closed? – Oleg Farenskiy Jun 22 '20 at 09:47

1 Answers1

2

This is a common Olympiad problem setup, skinned in a myriad of ways.
I'm slightly surprised that "almost all participants can't prove it", since there's a decent chance that some of them have seen a version of it before (example below).

Hint: Pigeonhole principle.

Hint: Deal with the general case, then set $ n = 25, m = 63$.
We have positive integers $ 1 \leq w_i \leq n$ for $i = 1$ to $m$, and $1 \leq b_j \leq m$ for $j = 1$ to $n$.
WTS $\sum_I w_i = \sum_J b_J$ for some indexing set.

Hint: It is sufficient for the indexing set to be an interval (taking consecutive integers).
Let $W_i$ for $i=1$ to $m$ be the sum of the first $i$ elements.
Let $B_j$ for $j = 0$ to $n$ be the sum of the first $j$ elements.

Hint: Show that for some suitably defined function $j(i)$, we have $ 0\leq W_i - B_{j(i)} \leq n-1$.

These differences are our pigeons and the value of the differences is our holes. Then the result follows by pigeonhole principle as, either

  1. all of those differences are distinct and so one of them is equal to $0$, which gives subsets of the same sum, or
  2. two of those differences are the same, so taking the difference of sets yields subsets with the same sum.

Essentially the solution: (The obvious choice of definition is) $j(i)$ is the largest index such that $B_j \leq W_i$, allowing for $j=0$ as needed.

Notes:

  1. The case of $n = m$ is also pretty common. EG I posted an answer here.
  2. Another skin of this problem is Putnam 1993, which is where I first came across this setup:

Let $x_1, \ldots , x_{19}$ be positive integers less than or equal to 93. Let $y_1, \ldots , y_{93}$ be positive integers less than or equal to 19. Prove that there exists a (nonempty) sum of some $x_i$’s equal to a sum of some $y_i$’s.

  1. We are applying the 4th form of Pigeonhole Principle, namely

If there are $ n > \sum_{i=1}^k a_i$ pigeons and $k$ holes, then there is some hole with at least $a_i + 1 $ pigeons.

In this case, we have holes of value $0, 1, 2, \ldots, n-1$, with corresponding sizes $a_1 = 0, a_2=a_3=\ldots a_n = 1$ and $ \sum a_i = n-1 < n$ pigeons.

  1. See this generalization from 1977 Soviet where we remove the restriction on individual values, and just bound the total by $< mn$.
Calvin Lin
  • 68,864