For a set of red, blue and yellow cards, we receive the points according to the following system:
What is the maximum number of points we can receive for a set of 15 cards?
This problem is posed by Minimario M.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Good argument, though the though process could be much clearer. The argument has to be slightly involved to deal with the edge cases, which were overlooked in the other solutions.
Note that you still have to explain the edge cases, instead of simply claiming that "we cannot have a maximum value for B=0 or B=1".
points caused by yellow cards are not they supposed to equal : Y * 3 * B * 2 * R ??
The key is to find the biggest point. And the biggest point is when the point of yellow card is maximum and how to maximum the point of yellow card? is to maximum red card.
we got if
a = r e d c a r d
b = b l u e c a r d
c = y e l l o w c a r d
a + b + c = 1 5
point a = a
point b = b × a × 2
point c = c × a × 3
so like what i said how to maximum p o i n t a + p o i n t b + p o i n t c is when card a and card c is 7 so the number for b must be 1 (Why 7 is maximum for card a and card c? remember how to find point c! is a × c × 3 and 7 × 7 × 3 is the biggest for c! why not 7 × 8 × 3 ? because the yellow card must be exist!
p o i n t a + p o i n t b + p o i n t c = 7 + 1 4 + 1 4 7 = 1 6 8
For a good verifiable mathematical solution, it is important to introduce some variables and to formally apply inequalities whenever appropriate. Otherwise, it is hard to impossible to check if the solution is correct and complete. In this particular problem the main sticking point is why 168 is the best possible.
point c = 3 * b * c !!!
I'm sorry because i missed word on the problem, if i make a change to my solution so the biggest solution for them is 1 6 2 . What's wrong with my solution way anyway?
Log in to reply
What's wrong with my solution way anyway?
I'm not sure. But I would suggest using the fact that, if b>0, then
r + 2 r b + 3 y b ≤ 3 b ( r + y )
That makes it a lot easier to prove that 168 is optimal.
Log in to reply
I still don't get it to find how to create the inequalities. I never learn to create inequalities from something like this question. Can someone help me to find a good link?
I guess you already realize that your c×a×3 should be c×b×3. But I don't think you considered all possibilities, like a=0.
Log in to reply
a=0 is impossible! since point b=b×a×2 and point c=c×b×3, it will comes point b and point a becomes zero.. and point c not comes to 168.
the point is i still claim that 162 is the biggest using my method..
Log in to reply
a=0 is impossible!
That's the issue. The problem doesn't say there must be at least one of each color, it just says "set of 15 cards". So a=0 is possible.
Log in to reply
@Peter Byers – I pull my word back.. i have try it! and you right. Thanks :)
Anyway now i'm trying to understand another method using inequalities. Like yours that i don't understand how you find it.
r + 2 r b + 3 y b ≤ 3 b ( r + y )
Can you help me please spell what is name for create it? i never learn it before. or explain it maybe? thanks before.
Log in to reply
@Hafizh Ahsan Permana – Okay, so Part 1: If you take a=0, b=7, c=8 then there's 168 points.
Part 2: We need to show that it's impossible to get more than 168 points. So consider,
Case 1: b=0 means that a + 2 a b + 3 c b ≤ 1 5
Case 2: b>0 a + 2 a b + 3 c b ≤ a b + 2 a b + 3 c b = 3 b ( a + c ) = 3 b ( 1 5 − b ) Now try to convince yourself that 3b(15-b) cannot be more than 168. (Picture a parabola.)
this is wrong because point c=3bc not 3ac
Red cards give 1 + b points. Blue cards can give at most 2 r points. Yellow cards give 3 b points. Clearly, the points are maximized when there are a certain number of blue and yellow cards such that there are enough blue cards to make yellow cards worth many points, but at the same time enough yellow cards to multiply that gain. Thus, there must also be no red cards.
If x is the number of yellow cards, this can be modeled as x ( 3 ( 1 5 − x ) ) . In an expanded form, this is − 3 x 2 + 4 5 x . This is simply a parabola whose maximum is at its vertex. The x-coordinate of the vertex can be found by 2 a − b , which in this case is 7 . 5 .
Since a parabola decreases at an equal rate on both sides, the solution is maximized at either x = 7 or x = 8 . Substituting this in as an answer, we get a maximum point value of 1 6 8 .
While this offers a slightly better explanation, "Thus, there must also be no red cards. " is still not a valid conclusion from the arguments stated.
For a clear solution, one should avoid using the word "clearly", if it is followed by a complicated sentence.
using namespace std;
int main() { int a,b,c,d,e; int max=0; for(a=0;a<=15;a++) { d=15-a; for(b=0;b<=d;b++) { c=15-a-b; e=a+b 2 a+c 3 b; if(max<e) max=e; } } std::cout << max << std::endl;
return 0;
}
R is number of red cards. B is number of blue cards. Y is number of yellow cards. P is point total of cards.
R + B + Y = 1 5 = ϕ P = R + 2 R B + 3 B Y
Because we have the boundary condition R+B+Y=15 its a good idea to try using a Lagrange multiplier. However, the straight forward method does not give a maximum or minimum. Apparently, without imposing the three remaining boundary conditions, the function P does not have a maximum or minimum. The three remaining boundary conditions are R ≥ 0 , B ≥ 0 , Y ≥ 0 . I worked the Lagrange method out separately with each of these conditions.
For R = 0
F = P + λ ϕ F = 3 B Y + λ ( B + Y )
∂ B ∂ F = 3 Y + λ = 0 , λ = − 3 Y
∂ Y ∂ F = 3 B + λ = 0 = 3 B − 3 Y , 0 = B − Y , B = Y
B + Y = 1 5 = 2 B , B = 7 . 5 = Y
Since the calculated maximum is between integers the actual maximum will be at one of the two closest integers. B is 7 and Y is 8, or vice versa.
P = 3 B Y = 1 6 8
Using the same method with B=0 does not yield a maximum. Using the method with Y=0 gives a maximum of 120. Therefore the maximum score possible with fifteen cards is 168.
Because we are restricted to looking at integers, we cannot naively differentiate the function to obtain the maximum. IE
Since the calculated maximum is between integers the actual maximum will be at one of the two closest integers.
need not be true. This is akin to integer programming, which is an NP hard problem.
If you wanted to take this calculus approach, what you could do is to "Fix R and B. Determine the value of Y that minimizes the expression. Determine the minimum over all values of R, B".
If there were two minima and one maximum between 7 and 8 then neither integer would have to be the location of a maximum, but that is not the case. Also if P were constant everywhere except between 7 and 8 then neither integer would be the location of a maximum, but that is not the case. The function isn't differentiable because its discontinuous at every point. However, it works to pretend like its continuous.
Let the number of red cards be x, the number of blue cards be y, the number of yellow cards be (15-x-y).
So the number of points received can be expressed as x+2xy+3(15-x-y)y =-3(y-7.5)^2+675/2+x(1-y) For this value to be maximum, it is obvious that x=0 and y=7 or 8. So the maximum number of points is 7 8 3=168
When people say "it is obvious that ...", it usually causes me to re-read their solution more often.
While this solution is essentially correct, several steps of explanation is needed to justify why we want x = 0 and y = 7 or 8 .
this is a set of red , blue , yellow card so there must be at least 1 red card so the maximum value is standing 162
Good solution. I formatted your post to make it more pleasing to the eye, if you don't mind.
Let the number of red cards be x , the number of blue cards be y , the number of yellow cards be ( 1 5 − x − y ) .
So the number of points received can be expressed as ( x + 2 x y + 3 y ( 1 5 − x − y ) = − 3 ( y − 7 . 5 ) 2 + 2 6 7 5 + x ( 1 − y ) For this value to be maximum, it is obvious that x = 0 and y = 7 or 8 . So the maximum number of points is 1 6 8
Log in to reply
it must be 675/4 :|
It's much clearer, thanks!
somehow i don't understand this solution..
where do you got " the number of points received can be expressed as "
(x+2xy+3y(15−x−y)=−3(y−7.5)2+675/2+x(1−y) ??
Log in to reply
At the first step, x + 2 x y + 3 y ( 1 5 − x − y ) is correct, because it indicates the points received. But he made a mistake, which were detected by Minh Quan. x + 2 x y + 3 y ( 1 5 − x − y ) = x + 2 x y + 4 5 y − 3 x y − 3 y 2 = − 3 y 2 + 4 5 y − 4 6 7 5 + 4 6 7 5 + x − x y = − 3 ( y − 7 . 5 ) 2 + 4 6 7 5 + x ( 1 − y )
On the final row, it must be 4 6 7 5 , not 2 6 7 5 .
That's why the line make some confusions.
Problem Loading...
Note Loading...
Set Loading...
Let the number of Red,Blue and Yellow cards be R, B, Y respectively. Points, P = R + 2 ∗ R ∗ B + 3 ∗ B ∗ Y Lets write this as an function of 2 variables Y,R for various values of B which will determine the coefficients, P = ( 1 + 2 ∗ B ) R + ( 3 ∗ B ) Y . It can be seen that for all values of B above 1, The coefficient of Y is greater than the coefficient of R. Hence logically we can conclude that R has to be 0 since we cannot have a maximum value for B=0 or B=1. The task reduces to maximizing the product of B*Y which occurs at (R,B,Y)=(0,8,7) or (0,7,8). On substituting the values we get P = 1 6 8 .