Martin has two boxes $A$ and $B$. In the box $A$ there are $100$ red balls numbered from $1$ to $100$, each one with one of these numbers. In the box $B$ there are $100$ blue balls numbered from $101$ to $200$, each one with one of these numbers. Martin chooses two positive integers $a$ and $b$, both less than or equal to $100$, and then he takes out $a$ balls from box $A$ and $b$ balls from box $B$, without replacement. Martin's goal is to have two red balls and one blue ball among all balls taken such that the sum of the numbers of two red balls equals the number of the blue ball. What is the least possible value of $a+b$ so that Martin achieves his goal for sure? For such a minimum value of $a+b$, give an example of $a$ and $b$ satisfying the goal and explain why every $a$ and $b$ with smaller sum cannot accomplish the aim.
Problem
Source:
Tags: combinatorics
16.09.2019 08:49
Wow, over two weeks and still no solution? This must be a very hard P1. The smallest $a+b$ is $\boxed{101}$. For example, take everything from $A$, and then whatever blue one we pick will work. If $a+b = X\leq 100$, then it is possible that Martin gets the red balls $1, 2, \ldots, a$, and the blue balls $201-b, \ldots, 200$. Then the biggest red sum is $2a = 2(X-b) \leq 200-2b < 201-b$, so then Martin will not achieve his goal. Thus every $a,b$ with sum smaller than $101$ will not work.
16.09.2019 09:12
Sir if he takes 200 from blue ball then his goal will not be achieved so 101 is not minimum value
16.09.2019 09:14
We cannot use same ball twice the question says without replacement
16.09.2019 09:16
It should be 102
17.10.2020 05:42
Jafet98 wrote: Martin has two boxes $A$ and $B$. In the box $A$ there are $100$ red balls numbered from $1$ to $100$, each one with one of these numbers. In the box $B$ there are $100$ blue balls numbered from $101$ to $200$, each one with one of these numbers. Martin chooses two positive integers $a$ and $b$, both less than or equal to $100$, and then he takes out $a$ balls from box $A$ and $b$ balls from box $B$, without replacement. Martin's goal is to have two red balls and one blue ball among all balls taken such that the sum of the numbers of two red balls equals the number of the blue ball. What is the least possible value of $a+b$ so that Martin achieves his goal for sure? For such a minimum value of $a+b$, give an example of $a$ and $b$ satisfying the goal and explain why every $a$ and $b$ with smaller sum cannot accomplish the aim. It can be seen that, given positive integers $a, b$, if $a > b$ then $a$ is more useful than $b$ in terms of number of pairs that can be formed between the number and some other number that sums to a number in $\mathrm{B}$. Example - $1+99 = 100 \not\in \mathrm{B}$ and so $(1, 100)$ is the only pair containing $1$ that adds up to a number in $\mathrm{B}$, whereas $(9, 92), (9, 93) (9, 94) \dots (9, 100)$ all add upto w number in $\mathrm{B}$. Hence, if we are picking $a$ numbers out of $\mathrm{A}$, then the worst case possible is that $1, 2, 3 \dots a$ are chosen, and so maximum possible sum is $2a-1$, and from $\mathrm{B}$, $2a, 2a+1 \dots 200, k$ are chosen where $k \leq 2a-1$. Here, value of $a+b=a+200-2a+2 = 200-a+2$. Hence, the minimum possible value of $a+b$ is for $a= 100$, that gives an answer of $\boxed{102}$.