The smallest possible positive value of 1 − ( w 1 + x 1 + y 1 + z 1 ) where w , x , y , z are odd positive integers, has the form b a , where a , b are coprime positive integers. Find a + b .
Note: The problem does not state that w , x , y , z must be distinct.
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.
This is essentially a simple case checking exercise. Solutions which failed to present all the cases (esp (3, 5, 5, 5) and (5, 5, 5, 5) ) were marked wrong. This is especially true for solutions that used the greedy algorithm - a construction argument often doesn't prove extremity (in this case, showing that it is the smallest).
Sometimes, it is easier to state the minimal value and check cases against it. This is a clean cut, direct solution, which is much neater than any others submitted.
It is also not true that "to maximize a fraction, we minimize the denominator." It depends on what the numerator is, especially if the numerator changes as you change your denominator.
Log in to reply
Calvin, isn't it okay to, firstly, maximise (1/w) such as it is less than 1 (w=3 in this case), then do the same with (1/x), such as it is less than (1-(1/3))=2/3 (like w, x=3) and so on to get {3, 3, 5, 5} in the end ?
Log in to reply
No it is not. Your procedure is akin to the greedy algorithm , which only gives us a local maximum which may not be a global maximum. To find the maximum of f ( w ) + f ( x ) + f ( y ) + f ( z ) , it does not imply that we have to first maximize f ( w ) and then f ( x ) , so on and so forth.
As a counter example, suppose the question was to find the smallest positive value of 0 . 4 5 1 − ( w 1 + x 1 ) . Then, your procedure will yield w = 3 , x = 9 with 3 1 + 9 1 = 0 . 4 4 4 … . However, it could have been possible to use a slightly larger w and a much smaller x to obtain a better value. In this case, we have w = 4 , x = 5 with 4 1 + 5 1 = 0 . 4 5 giving us a value closer to 0.451.
Note that our goal is to maximize 1/w + 1/x + 1/y + 1/z such that this value is less than 1. What we are going to do is consider all the possible candidates for maximum value through casework and find the actual largest one.
Without loss of generality, assume that w \leq x \leq y \leq z $.
Case 1 If w \geq 5, then 5 \leq x \leq y \leq z. 1/w + 1/x + 1/y + 1/z therefore has a maximize value of 4/5. This is still less than 1, and therefore a possible candidate for maximum value.
Case 2 If w is not \geq 5, then w = 3. It remains that we have to maximize 1/x + 1/y + 1/z for which this is less than \frac{2}{3}.
Case 2.1 If x \geq 5, then 5 \leq y \leq z. Therefore 1/x + 1/y + 1/z has a maximum value of 3/5. This is less than 2/3, and thus a possible candidate for being maximum value.
Case 2.2 If x is not \geq 5, then x = 3. It remains to maximize 1/y + 1/z for which this value is less than \frac{1}{3}.
Case 2.2.1 Note that y = 3 will make 1/y + 1/z > \frac{1}{3}, which is not valid. Therefore we will go straight to y = 5. If y = 5, then the smallest possible z that makes 1/y + 1/z > \frac{1}{3} is z = 9. This yields a maximum value of 1/y + 1/z = 14/45 for when y = 5. Note that 14/45 < 1/3 and so it is a valid candidate.
Case 2.2.2 If y \geq 7, then z \geq 7. 1/y + 1/z \leg 2/21.
If we look at all our candidates for maximum value, we have w = 3, x = 3, y = 5, z = 9 yielding the largest possible value of 1/3 + 1/3 + 14/45 = 44/45
a/b = 1/45. Hence a + b = 46
Let S = 1 − ( w 1 + x 1 + y 1 + z 1 ) . Let's assume, WLOG, that w ≤ x ≤ y ≤ z . If w ≥ 5 , then S ≥ 1 − 4 × 5 1 = 5 1 . Clearly there are no possibilities for w = 1 , so let's assume w = 3 .
If x ≥ 5 , then S ≥ 1 − ( 3 1 + 3 × 5 1 ) = 1 5 1 . Now, we assume x = 3 .
If y ≥ 7 , then S ≥ 1 − ( 2 × 3 1 + 2 × 7 1 ) = 2 1 1 . As S < 0 for y = 3 , we assume y = 5 .
Since S < 0 for z ≤ 7 , we must have z ≥ 9 . So S ≥ 1 − ( 2 × 3 1 + 5 1 + 9 1 ) = 4 5 1 , and that's the lowest value we found so far.
We analyzed every possible case, so the smallest positive value for S must be 4 5 1 (that occurs for ( w , x , y , z ) = ( 3 , 3 , 5 , 9 ) ), therefore the answer to this problem is 1 + 4 5 = 4 6 .
If w , x , y , z > 3 , then w 1 + x 1 + y 1 + z 1 ≤ 5 1 + 5 1 + 5 1 + 5 1 = 5 4 is the maximum value of the sum, which is clearly not the best case, since we can take w = 3 and x = y = z = 5 to get w 1 + x 1 + y 1 + z 1 = 3 1 + 5 3 = 1 5 1 4 , which is closer to one. Therefore, the best case scenario comes from taking at least one of w , x , y , z equal to 3 .
Suppose without loss of generality that w = 3 , so that we need to find the smallest positive value of 1 − ( 3 1 + x 1 + y 1 + z 1 ) = 3 2 − ( x 1 + y 1 + z 1 ) . Suppose again that x , y , z > 3 , so that x 1 + y 1 + z 1 ≤ 5 1 + 5 1 + 5 1 = 5 3 . However, we can again get closer to 3 2 by taking x = 3 and y = z = 7 , so that x 1 + y 1 + z 1 = 3 1 + 7 2 = 2 1 1 3 , which is again closer to 3 2 than 5 3 . Therefore, again, the best case scenario comes from taking another one of x , y , z to equal 3 .
Again without loss of generality, say x = 3 , so that we again need to find the minimum positive value of 3 2 − ( 3 1 + y 1 + z 1 ) = 3 1 − ( y 1 + z 1 ) .
Clearly y , z ≥ 5 , otherwise the value would be negative. Suppose without loss of generality that y ≤ z . Now suppose that y = 5 , so that we must minimize 3 1 − 5 1 − z 1 = 1 5 2 − z 1 . This minimum positive value occurs at z = 9 , which causes the value to be 4 5 1 . If y > 5 , then y 1 + z 1 ≤ 7 1 + 7 1 = 7 2 , and the minimum value in this case is 3 1 − 7 2 = 2 1 1 . However, the value 4 5 1 is smaller than this, so the minimum possible value is 4 5 1 , which occurs at ( w , x , y , z ) = ( 3 , 3 , 5 , 9 ) . The answer is therefore 1 + 4 5 = 4 6 .
Denote 1 − ( w 1 + x 1 + y 1 + z 1 ) as S ( w , x , y , z ) . We know that \S ( 3 , 3 , 5 , 9 ) = 4 5 1 . We show that this is the minimum positive value. (Note that S ( w , x , y , z ) is competely symmetric, i.e. the value is constant regardless of the permutation of w , x , y , z ).
First, we know that min { w , x , y , z } ≥ 3 , otherwise one of them will be 1 , so S ( w , x , y , z ) < 0 . We show that at optimal condition, (i.e. the S ( w , x , y , z ) is minimal possible positive real), exactly two of { w , x , y , z } is 3 .
Suppose on the contrary, the claim is false, that means at most one of them, or at least three of them is 3 . If three (or more) of them is 3 , (Without loss of generality let w , x , y = 3 ) then S ( 3 , 3 , 3 , z ) = 1 − 3 ( 3 1 ) − z 1 = − z 1 < 0 , a contradiction. Next, if at most one of them is 3 , then the other three variables is at least 5 since none of w , x , y , z can be 1 . Hence, S ( w , x , y , z ) ≥ S ( 3 , 5 , 5 , 5 ) = 1 − 3 1 − 5 3 = 1 5 1 > 4 5 1 , so S ( w , x , y , z ) is not optimal. Hence exactly to of w , x , y , z is exactly 3 , and the other two is at least 5 .
Now, by the claim above we only need to consider S ( 3 , 3 , y , z ) , and hence S ( 3 , 3 , y , z ) = 1 − 3 2 − ( y 1 + z 1 ) = 3 1 − ( y 1 + z 1 ) ≥ 0 , hence y 1 + z 1 ≤ 3 1 .
By T2's lemma, 3 1 ≥ y 1 + z 1 ≥ y + z ( 1 + 1 ) 2 = y + z 4 . Hence y + z ≥ 1 2 . If y + z = 1 2 , y 1 + z 1 ≥ 3 1 by T2's lemma again, with equality if and only if y = z = 6 which is impossible since y , z are both odd. So y + z ≥ 1 4 . For y , z = 5 , 9 we get the optimal value of S ( w , x , y , z ) .
It remains to show that if w , x = 3 , then min { y , z } = 5 , otherwise, as we know that y , z ≥ 5 by previous claim, we know that if none of them is 5 then y , z ≥ 7 . So S ( 3 , 3 , y , z ) ≥ S ( 3 , 3 , 7 , 7 ) = 2 1 1 > 4 5 1 . So one of them must be 5 and let it be y . Since y + z ≥ 1 4 , z ≥ 9 . It can be seen that if z > 9 then S ( 3 , 3 , 5 , z ) > S ( 3 , 3 , 5 , 9 ) = 4 5 1 .
Therefore, the minimal positive value of S ( w , x , y , z ) is 4 5 1 . Hence a + b = 4 6 .
maximum value of 1/w + ... = 4 (w=1) none of them can be 1 else the result is negative ; next possibility all are 3; sum = 4/3; when any 3 of them = 3 sum is already 1; result negative; to obtain maximum : 2: 3's 2:5's not possible; 1:3 3:5's answer 1/15; possible bigger than this implies: 2:3's 2:5's ; result negative; 2:3 1:5 1:7 : result negative; 2:3 1:5 1:9 ; result :1/45;smaller than any 2:3 1:5 1:x--> odd numbers 2:3 2:7 : result 1/21; smaller than any 2:3 2:x X-->odd numbers all other cases will give a bigger result than 1/45
Without loss of generality, we can assume that w ≤ x ≤ y ≤ z . We consider several cases.
Case 1. If w ≥ 5 , then ( w 1 + x 1 + y 1 + z 1 ) ≤ 5 4 , and subtracting this from one gives value at least 5 1 .
Case 2. If w = 3 and x ≥ 5 , then ( w 1 + x 1 + y 1 + z 1 ) ≤ 1 5 1 4 , and subtracting this from one gives value at least 1 5 1 .
Case 3. If w = 3 , x = 3 , and y ≥ 7 , then ( a 1 + b 1 + c 1 + d 1 ) ≤ 2 1 2 0 , and subtracting this from one gives value at least 2 1 1 .
Case 4. If w = 3 , x = 3 , and y = 5 , then for the difference to be positive we must have z ≥ 9 . Then ( w 1 + x 1 + y 1 + z 1 ) ≤ 4 5 4 4 , with the equality attained for z = 9 . Subtracting this from one gives value at least 4 5 1 , and the equality is possible.
Thus, the answer is 1 + 4 5 = 4 6 .
Simple, for w<=x<=y<=z, keep try to lower value of all 4 from left. First try (w,x,y,z) = (3,3,3,z) which is not possible, so then (3,3,5,5) which is not also possible, then (3,3,5,7) is not possible also, then (3,3,5,9) which is possible and that should be the answer.
Unfortunately, the greedy algorithm doesn't guarantee that we have the maximum / minimum value. It only gives us one possibility, and we still have to compare it against others.
For example, it is not clear why (3, 3, 6, X) cannot give us a better result that (3, 3, 5, 9). Also, why did you skip those of the form (3, 3, 4, X)?
Log in to reply
Since 4 isn't an odd number. If even number allowed there, answer should be (2,3,7,43). But i should have mention there that (3,3,5,7) is not also possible.
Ok, here we actually should work i think, first try with w=1 not possible since then others should be infinite. Then w=2, that's possible, so next x can't be 1 or 2 but can be 3. Next y must be >6, and immediate next integer 7 should be taken. Now z must be > 42 and should be 43.
To give us a better result by (3, 3, 6, z) than (3, 3, 5, 9) z should be less than 3 0 + 9 3 0 × 9 = 6 . 9 2 3 that means <= 6, but that will lead to a no possible solution.
Log in to reply
Ooops, I forgot that we only wanted odd numbers, which made this problem easier to work with. But still, the same idea applies. How do you know that (3, 5, 5, X) cannot do better, or (3, 3, 7,X)?
See my solution to understand how to justify why those cases do not yield the minimium that we want. It's just ensuring that you've covered all the possible cases.
The four addition in the bracket ( say=S) must be less than 1 but as near to 1 as possible. Any one =1 or and any three =3 gives S>1.
Next is any two =3 would be the best choice.
Next best is remaining two = 5, but than S>1.
But w=3, x=3, y=5 gives S<1.
Next best would be z=7, but S>1.
So the next is z=9. This gives the value as 3/135=1/45. a+b =
4
6
There can not be any option to this the way we have picked up the values.
As stated in problem w, x, y and z could and could not be distinct. That allows to choose w and x both being 3. /frac {1}{3} + /frac {1}{3} = /frac {2}{3} . You can not choose y or z to be 3, because then you would end up with value /leq 0 which disobeys rules of the task. By choosing y = 5 you can easy add up all the fractions /frac {2}{3} + /frac {1}{5} = /frac {13}{15} . You can not choose z = 7 because then you will end up with walue /leq 0 again. So next number which fits is z = 9 . Sum all the fractions and you get /frac {1}{3} + /frac {1}{3} + /frac {1}{5} + /frac {1}{9} = /frac {44}{45} . Subtract 1 - /frac {44}{45} = /frac {1}{45} where a = 1 and b = 45. By adding 1 + 45 = 46 you now have the desired result.
We have to take into account that we need the closest number to 1 we can inside the brackets, without making it bigger than 1. That's what is most important in all of this. But what really made the click for me was reminding about what I wrote in the key technique. I didn't want the biggest number I could, but the smallest, since I was looking for denominators and not for the whole fractions.
Then, it was a simple use of trial and error. First, I tried using 1 as the denominator for all the fractions. It didn't work because even one sent the all the calculation automatically to zero, and the other ones would make the result negative. Next, I used 3 for the denominators. Now, I could use two of them, before I faced the same problem as with 1. So, two of the fractions were 1/3. Then I moved on to 5, but I could only use one before the result became negative. Finally, 7 didn't work at all for the last fraction, leaving only 9 to fit in it.
So, in the end, the fractions were 1/3 + 1/3 + 1/5 + 1/9. Then, it was only a matter of solving the calculation and presenting the solution the way it was asked.
Since none of w, x, y, z can be 1 (resulting in 0 - a/b which will end up in a negative), therefore the largest fraction has to be 1/3. As w, x, y, z are not required to be distinct, w, x equals 3 to maximize their sum. We are left with 1/3 - (1/y + 1/z). If y equals 3, it will be 0 - 1/z. As z have to be a positive integer, either a or b will be negative, thus y equals 5. Now we have 2/15 - 1/z left. As 2/15 = 1/7.5, if z equals 7, the result will be negative, thus z equals 9 and the result is 1/45. Adding them up gives 46.
We want to find the smallest possible value for b a . In order to do that, we want the ( w 1 + x 1 + y 1 + z 1 ) to be the largest fraction possible.
We have the restriction that w , x , y , and z must be odd, positive integers. Since the integers do not need to be all different, we start with w and x as 3. This gives us
1 − ( 3 1 + 3 1 ) + ( y 1 + z 1 )
1 − ( ( 3 2 ) + ( y 1 + z 1 ) )
3 1 − ( y 1 + z 1 )
(We could not have had y = 3 because z, a, and b all have to be positive integers)
This leaves us with
( y 1 + z 1 ) less than but as close to 3 1
The next odd positive integer that y could be is 5. Thus
z 1 less than but as close to 3 1 − 5 1
z 1 less than but as close to 1 5 2
The decimal expansion for 1 5 2 is 0 . 1 3 3
The next odd number for z is seven. The decimal expansion for 7 1 is approximately 0 . 1 4 2 8 5 7 .
0 . 1 3 3 < 0 . 1 4 2 8 5 7
Thus resulting in b a becoming negative.
Since seven did not work, we continue to 9. The decimal expansion for 9 1 is 0 . 1 1 1 .
0 . 1 1 1 < 0 . 1 3 3
Thus 9 is a valid value for z. Going back to the original...
1 − ( 3 1 + 3 1 ) + ( 5 1 + 9 1 )
4 5 1 = b a
The problem asked for a + b .
1 + 4 5 = 46
The problem is equivalent for maximizing w 1 + x 1 + y 1 + z 1 . We know that to maximize a fraction, we minimize the denominator. WLOG, w ≤ x ≤ y ≤ z . Then w = x = 3 first, because we cannot replace any other two fractions of odd denominator greater than 1 to make it bigger. So let A = y 1 + z 1 < 3 1 , y , z > 3 . The first maximal values of A are 5 2 , 3 5 1 2 , 4 5 1 4 . . . . Note that 3 5 1 2 > 3 1 > 4 5 1 4 . A = 4 5 1 4 when y = 5 , z = 9 . So the answer is 1 − ( 3 1 + 3 1 + 5 1 + 9 1 ) = 4 5 1 . a + b = 1 + 4 5 = 4 6 .
Problem Loading...
Note Loading...
Set Loading...
Without loss of generality we can assume w ≤ x ≤ y ≤ z . For ( w , x , y , z ) = ( 3 , 3 , 5 , 9 ) we have b a = 4 5 1 . We now seek to do better than this.
If w > 3 , x , y , z ≥ 5 , b a > 4 5 1 , so w = 3 .
If x > 3 , y , z ≥ 5 , b a > 4 5 1 , so x = 3 .
If y > 5 , z ≥ 7 , b a > 4 5 1 , so y = 5 .
If w > 9 , b a > 4 5 1 , so z = 9 .
This proves that ( w , x , y , z ) = ( 3 , 3 , 5 , 9 ) is the best solution.