-1

My one friend Alex has r red, g green and b blue balloons. To decorate a single table for the banquet he needs exactly three balloons. Three balloons attached to some table shouldn't have the same color.

What maximum number t of tables can be decorated if he knows number of balloons of each color? Alex gave me this problem to solve. For given values r, g and b how will I find the maximum number t of tables, that can be decorated in the required manner.

My another friend joy solved it and found this information. If r=5,b=4,g=3,his result is 4.

But I can't understand how he solved and found this result.Can anyone tell me joy's process and reasoning behind it?

Shahed Al Mamun
  • 71
  • if all 3 must be of different color then answer is minimum of r,g,b; if color does not matter then answer is integer part of (r+g+b)/3 – Vikram Oct 17 '14 at 07:19
  • For r=5,b=4,g=3 you can decorate the tables with the following balloon sets: "rgg", "gbb", "brr", "rrg", where "r", "g" and "b" represent the red, green and blue balls, respectively. – Shahed Al Mamun Oct 17 '14 at 07:42
  • Or also one table of "rrb" and three tables of "brg". – Greg Martin Oct 17 '14 at 07:55
  • Taken from http://codeforces.com/problemset/problem/478/C – JRN Jul 21 '15 at 01:58

1 Answers1

0

Let $x,y,z$ be the numbers of blue, green, and blue balloons. If $\max\{x,y,z\} > \frac23(x+y+z)$, then the maximum number of tables is $x+y+z-\max\{x,y,z\}$: Supposing that the max is achieved by blue balloons, than this number of tables can be achieved by making each table either "bbg" or "bbr", and no more tables are possible because each table has to have at least one green or red balloon.

If $\max\{x,y,z\} \le \frac23(x+y+z)$, then I believe you can use essentially all the balloons and decorate $\lfloor \frac13(x+y+z) \rfloor$ tables. To do so, use the following algorithm: if $\max\{x,y,z\} - \min\{x,y,z\} \ge2$, use two balloons of the most numerous color and one balloon of the second-most numerous color (breaking ties arbitrarily); $\max\{x,y,z\} - \min\{x,y,z\} \le1$, use one balloon of each color.

Greg Martin
  • 78,820
  • why max{x,y,z}>2/3*(x+y+z)?.I can't fully understand your method,need better explanation. – Shahed Al Mamun Oct 17 '14 at 13:21
  • This wasn't intended to be a complete proof; it was stating the answer explicitly, with an outline of some thoughts intended to guide you as you work through the details. For example, try running the algorithm from the second paragraph on various examples, and see how things change depending on whether $\max{a,b,c}$ is larger or smaller than $\frac23(x+y+z)$ (equivalently, whether the largest number is more or less than twice the sum of the other two). – Greg Martin Oct 17 '14 at 21:40