Monday, December 12, 2011

Is this problem too hard for a HS Math Competition

The Univ of MD HS Math Competition has two parts. Part I is 25 multiple choice questions in 2 hours (4 points for a correct answer, -2 for an incorrect answer). If you do well on it (the threshold changes from year to year) then you can do Part II which is 5 problems in 2 hours, 30 points each. The winner is the person who does best on the sum of the two parts.

This year I submitted a problem for Part II. The people on the committee who tried it couldn't do it so we decided to NOT put it on the exam. I only knew the answer because I read a theorem and build a problem around it. The people who couldn't do it are very sharp. Since they could not do it the problem was too hard. But... lets see what you think?

I would like YOU to try it without consulting any resources, (and don't look at the comments- someone might post questions that lead to a hint, or the answer) and keep in mind that you can't use advanced techniques (I'm do not think they would help anyway). See if you can do it so I can get a sense if it really is too hard. Post your opinion on if its too hard for a HIGH SCHOOL math competition. Here is the problem:
Prove or disprove: there exist natural numbers x1,...,x10 such that
  1. 2011=x1+... +x10 and
  2. 1=1/x1+... +1/x10
(ADDED LATER- A commenter thought that the xi's in the first and second condition could be different. They are not. We want x1,...,x10 that satisfy both of these simultaneously.)

I'll post a pointer to the solution next time I post. (Probably Wednesday.) ADDED LATER- a commenter wants to know if there is a solution or not and can't wait until WED. Also wants to know if there is a solution is it constructive or proof of existence. To answer the question but NOT ruin it for others, I put it in a file you can click on (or NOT) over here: here.)

51 comments:

  1. 1) Several correct answers exist and one of them is: x1=x2..= x9 = 202 and x10 = 193
    2) x1=x2..= x10 = 10

    Its easy for HS Students

    ReplyDelete
    Replies
    1. It is not a solution. The condition 1 = 1/x1+...+1/x10 does'n hold

      Delete
  2. I believe they have to be true simultaneously.

    ReplyDelete
  3. There do not exist any such numbers. Take the product of the two expressions. Then you get:

    2011 = x1 + ... + x10 + sum_{i != j} x_i/x_j

    We know x1 + ... + x10 = 2011, so we have:

    sum_{i != j} x_i/x_j = 0

    Which cannot be true if the x_is are non-negative.

    ReplyDelete
  4. YES, they have to be true simultaneously.

    ReplyDelete
  5. If you take the product you get

    (x1 + x2 + ... + x10)( 1/x1 + 1/x2 + ... + 1/x10)

    = 10 + sum_{i!=j} x_i/x_j

    NOT

    x1 + ... + x10 + sum_{i!=j} x_i/x_j

    ReplyDelete
  6. no, i don't think it exists... since 2011 is a prime number:

    ReplyDelete
  7. Why is 2011 being a prime relevant?
    We want (x1 + ... + x10) = 2011, NOT

    x1 times x2 times .... times x10 = 2011.

    ReplyDelete
  8. I think that it should be quite easy for a good HS student. E.g., you just need to note that you can ignore 8 numbers (e.g. set them to 1) and then solve for the remining two using a quadratic equation.

    ReplyDelete
  9. Your solution does not yield NAT NUMBERS.
    Set x1=...=x8=1 and let x9=x and x10=y.
    Note that 1/xi = 1 for 1\le i\le 8.

    8+x+y = 2001

    8+ 1/x + 1/y = 1

    Multiply second equation by xy

    8xy + y + x = xy

    x+y = -7xy

    SUB this into first equation

    8- 7xy = 2001

    -7xy = 1993.

    BUT 7 does not divide 1993. So there is no
    solution in natural numbers.

    PERHAPS there is some way to set x1,...,x8 so
    that the remaining set of equations in 2 vars
    has a solution, but you have not shown that.

    ReplyDelete
  10. you need to consider the relationship between arithmetic mean, geometric mean and harmonic mean, and next use the fact that 2011 is prime. I think a good HS student will be able to solve it.

    ReplyDelete
  11. Anon who wants to use 2011 prime and AM, GM, HM---
    I am skeptical but curious- so as to not give away a solution to others, please email me your
    solution.

    gasarch@cs.umd.edu

    ReplyDelete
  12. Primality of 2011 is not enough for a negative answer, as for another prime 113 the answer is positive:

    4 * 1/(2*4) + 5 * 1/(3*5) + 1/6 = 1
    while
    4 * 2 * 4 + 5 * 3 * 5 + 6 = 113

    I have a feeling that 2011 is too big and tried to find maximum possible sum x1 + ... + x10 when 1/x1 + ... + 1/x10, for example

    1/2 + 1/4 + 1/8 + ... + 1/512 + 1/512 = 1
    and 2 + 4 + 8 + ... + 512 + 512 = 1534

    perhaps there is a way to show that the best decomposition of 1 into unit fractions uses powers of 2, I have failed to to this.

    Anyway the problem seems to hard for a HS competition, I'm a graduate math student with a small bit of success in mathematical olympiads and did not solve it in 1.5 hours.

    ReplyDelete
  13. Sorry didn't realize the answer has to be with integers.

    But I still think it is not hard. That's what you do: Notice that 1/1 + (1/2a) + (1/2a) + (1/-a) =1 and 1+(2a)+(2a)+(-a)=1+3a. So, if a=670 we get that the sum is 1+2010=2011. For the rest of the numbers, since we have 6 left, we can pick another integer b and let half of them be b and the other -b.

    ReplyDelete
  14. My gut instinct tells me that a solution exists. This problem is too hard only for SOME HS competitions (no offence). I'd seen way harder problems when I was doing math olympiad back in HS.

    But in general I do not enjoy these random diophantine equations.

    ReplyDelete
  15. Anon who begins `Sorry didn't realize that the answers has to be integers'

    actually they have to be natural numbers.

    However, your misinterpretation of the problem
    IS a good problem.

    Anon whose gut says there IS a solution- fair point
    about WHICH HS competitions. This one is open to
    ALL high school students in Maryland. Olympiad problems are harder. However, is my problem
    too hard for an Olympiad problem? I don't know---
    I do think its too hard to be an easy Olympiad problem.

    ReplyDelete
  16. Anon above with the a=670 solution: the blog post says natural numbers, so negative integers aren't allowed.

    ReplyDelete
  17. A solution does not exist. The first equation implies that an odd number of them most be odd, so there is at least one even. When you take that to the bottom equation, and multiply both sides by the combined product you see that at least 2 terms must be even. going back to the first equation if there are 2 even there must be at least 3, going back to the bottom equation you get at least 4 must be even [going through an infinite descent with increasing powers of two](I think) and I suspect so on and so forth, I haven't taken the time to write it out. which ultimately gets you that all must be even which is a contradiction.

    ReplyDelete
  18. Anon who thinks its false using an even-odd argument.
    Your argument intrigued me so I tried to work it out
    (see below).
    I CAN get that 3 of the terms are even, but I can't
    get beyond that. I am skeptical-but-curious---
    please email me your solution so that others can
    still enjoy working on it.

    2011=x1 + ... + x10

    YES, at least one of the terms is even, say x1=2a

    2011 = 2a + x2 + ... + x10

    1= 1/2a + 1/x2 + ... + 1/x10

    Multiply both sides by 2a x2 x3 ... x10 to get

    2a x2 x3 x4 ... x10 = (x2 x3 ... x10) + 2a STUFF

    (x2 x3 ... x10) = 2a x2 x3 x4 ... x10 - 2a STUFF

    So YES, at least one of x2, x3, ..., x10 has to be even.
    Say its x2= 2b

    So now we have


    2011 = 2a + 2b + x3 + ... + x10

    If all of x3,...,x10 are ODD then ae have even=odd
    so YES, one of x3,...,x10 must be even
    say x3=2c

    2011 = 2a + 2b + 2c + x4... + x10

    1= 1/2a + 1/2b + 1/2c + 1/x4... + 1/x10

    Multiply both sides by (2a 2b 2c x4 x5 ... x10) to get

    8 a b c x4 x5 x6 x7 x8 x9 x10 = 4bc STUFF + 4ac STUFF + 4bc STUFF + 8 STUFF

    divide by 4 to get

    2 a b c x4 x5 x6 x7 x8 x9 10 = bc STUFF + ac STUFF + bc STUFF + 2 STUFF

    bc STUFF + ac STUFF + bc STUFF is EVEN.

    From that I can't see how you get that more of the xi's are even.

    ReplyDelete
  19. This does not look solvable. From the first eq, avg(x_i) = 201.1 whereas from the second avg(1/x_i) = 1/10 i.e., avg(x_i) =10. Of course, this is not the whole proof, but I believe some thing can be worked out along this line.

    ReplyDelete
  20. Ok, lets substitute Y=max(x_2,...,x_10). Then we can re-write x1+9Y >= 2011 and 1/x1 + 1/(9Y) >= 1, this will yield, that at least one of them has to be more than 1/2, i.e., x1<= 2. However, none of this will yield a solution.

    ReplyDelete
  21. So, x1,...,x10 doesn't imply they are all different numbers? I thought they must be different, otherwise why make a distinction between x1 and x2 if x1=x2?

    ReplyDelete
  22. Responses to the last three comments:



    1) Avg(x_i) = 201.1

    Avg(1/x_i) = 1/10 hence Avg(x_i)=10. Contradiction
    (The commenter does say that this is NOT a complete proof
    but something like it can be worked out.)

    This raises a good question- how much does AVG(x_1,...,x_n)
    and 1/AVG(1/x_1,...,1/x_n)) differ? I think they can differ by a lot.

    I am skeptical but curious- if you make this into a complete proof
    then please email me so that others may still enjoy working on this.

    2) Y=max(x_2,...,x_10).

    x1+9Y >= 2011

    1/x1 + 1/(9Y) >= 1 NO- as numbers go up their reciproacls go down

    EXAMPLE: 1/2 + 1/3 + 1/6 = 1

    but
    1/2 + 1/6 + 1/6 <= 1

    3) YES, you can have x_1=x_2.

    ReplyDelete
  23. Say that a number n is k-doable if there are k positive integers whose reciprocals sum to 1 and that add to n.

    The only 1-doable is 1, and the only 2-doable is 4 = 2+2.

    The only three 3-doables are 9 = 3+3+3, 10 = 2+4+4, and 11 = 2+3+6

    There are 13 4-doables if I've counted right, the smallest being
    16 = 4+4+4+4 and the largest being 54 = 2+3+7+42.

    In general the smallest k-doable is k^2 and the largest is what you get
    by greedily taking the smallest k that won't make the sum of reciprocals
    equal 1:

    2+2 = 4
    2+3+6 = 11
    2+3+7+42 = 55
    2+3+7+43+42*43 = 1861
    2+3+7+43+(42*43 + 1) + (42*43*(42*43 + 1)) = a lot

    So there are 10-doables _much_ larger than 2011, contrary
    to someone's suggestion above. It looks like the largest
    k-doable grows like 2^{2^k} because it roughly squares each time.

    But I am not that much closer to getting the answer to the original
    problem...

    ReplyDelete
  24. Given the above, it would be too laborious to ask anyone to actually produce x1, x2, ... x10 so that the conditions hold; so maybe such numbers don't exist?

    Parity mod 2 arguments very easily fail. Parity mod 3?

    1/2k --> 1/3k + 1/6k; 2k mod 3 goes to 0.
    1/n --> 1/n+1 + 1/n(n+1) (Dave's example):
    n |--> n^2 + 2n + 1 = n^2 - n + 1.
    where, (mod 3) 0 goes to 1, 1 goes to 1, 2 goes to 0.
    2 mod 3 is missed.

    Does this help? I don't see any mod 3 argument. 2011, sadly enough is 1 mod 3.

    ReplyDelete
  25. one correction to Dave's comment:
    2 + 3 + 7 + 42 = 54

    (still no light of a modulus argument).

    ReplyDelete
  26. 2297 is a prime number of approximately the same size, and can be solution of analogous equation (take 2297=2+3+12+24+48+96+192+384+768+768). It appears that numbers that can be represented in this way are rare and so the assumed answer is no, but the impossibility cannot be proven by simple congruences.

    Now we tinker a bit. A good sequence seems to be 2 3 14 28 28 84 168 336 672 672 which gives 2007, pretty close call. We could also get 2013 with 11 entries.

    The only way this problem is not going to be too tough for HS students is for it to have a solution. But I sense TCS bias in making construction, which is not so easy for HS students. Not a lot of HS students will solve this.

    ReplyDelete
  27. solution found with 7 instead of 10 elements

    2+3+14+14+86+86+1806=2011

    ReplyDelete
  28. Anon with 7 instead of 10- interesting, but
    not the answer to the question we are asking.

    ReplyDelete
  29. 2011 is a prime. Do the standard algorithm for fractions and you get 2011 over a composite. Can't be one.

    ReplyDelete
  30. 2009=2+9+9+9+24+27+27+27+75+1800

    ReplyDelete
  31. Anon- ALAS, if only I had though of the problem in 2009 instead of 2011, then you would have gotten it right!

    ReplyDelete
  32. 60sdieting- an earlier comment noted that the prie
    2297 CAN be written as the sum of numbers whose
    recips add up to 1. So your train of thought cannot work. (It would be enlightening for you to
    do the argument and see where it breaks down.
    I learn LOTS from failed proofs.)

    ReplyDelete
  33. The theorem must be something like - every odd number greater than X can be represented with Y elements, say every number greater than 1000 can be represented by 10 or so entries. We already have 2009, 2007 - so it seems that all numbers are representable like this, if sufficiently large. There is some freedom in choices but it seems that you "built" your problem around some theorem of this sort.

    The proof possibly goes by induction, building from a pool of numbers that are all representable. Also, possibly, you perhaps need C+log (n) entries to rerpresent each number of size <n, starting with some number.

    We can see heuristics, there are exponentially many representations of 1 as sum of k reciprocials (exponential in k), so that largest number does not rise more than exponentially; then by some sort of covering we can get all representations.

    But this is not a fair problem for HS. They have to guess representation, which is NP problem (in number of digits, that is, in log (n)). Probably the simplest way to check this is brute force search with some simple optimizations, so it is not particulary enlightening as a HS problem.

    ReplyDelete
  34. x1 -> (1370685 -
    3 sqrt[208548352065])/1370,
    x2 -> 6, x3 -> 10, x4 -> 15, x5 -> 6,
    x6 -> -3, x7 -> -7, x8 -> -16, x9 -> -1,
    x10 -> 2001 + (-1370685 + 3 sqrt[208548352065])/1370

    ReplyDelete
  35. It would seem a good approach is to figure out which theorem was used to construct the problem.

    An obvious candidate is the Arithmetic-Geometric Mean Inequality but in this case (as I understand it) it only tells us Harmonic mean =< Geometric Mean =< Arithmetic Mean, and since Harmonic Mean = 10 and Arithmetic Mean = 201.1 this is not very useful.

    So there must be a stronger inequality that was used probably one that involves the Harmonic Mean, the Arithmetic Mean and maybe integrality conditions.

    ReplyDelete
  36. ok no more dispense here ... Bill plz post solution!

    ReplyDelete
  37. I think you mean `no more suspense''

    Anyway, on WED I will post three solutions
    (the one I intended, the one a BRIGHT HS
    student emailed me, and one that a reader
    emailed me). I may post more if more people
    send them to me.

    Problems worth of attack prove their worth by hitting back (Piet Hein quote)

    ReplyDelete
  38. > This raises a good question- how much does AVG(x_1,...,x_n)
    > and 1/AVG(1/x_1,...,1/x_n)) differ? I think they can differ by a lot.

    Yes. There is one constraint on their relationship, which is that if all the x_i are positive, their harmonic mean cannot exceed their arithmetic mean. It follows that the product of the two series is at least n^2. (For a nice proof, see Proofs from the Book. Their proof uses the Cauchy-Schwarz inequality.)

    So if you were to replace 2011 with 199 in your question, it would be impossible even for real numbers.

    ReplyDelete
  39. If x is represented by k numbers, than 2x+8 and 2x+9 are represented by k+2 numbers. If x is represented by k numbers than 3x+8 and 3x+6 are representable by k+2 numbers. Such is a number of reductions. From 1= 1/4+1/4+1/4+1/4 and 1=1/2+1/4+1/6+1/12, we get that if x is representable by k numbers than 4x+12 and 4x+20 are representable by k+3 numbers.

    Now let us try use these reductions on 2011. 2011=2*1001+9
    1001=3*331+8
    331= 2*161+9
    161= 3*51 +8
    51 is divisible by 3, so we can apply either of the two reductions.
    51=2*21+9
    or
    51=3*15+6
    Now we are a bit stuck, but this method can help.
    For instance if we can do 331 in 6 moves or 1001 in 8 moves we are done.

    ReplyDelete
  40. The answer by one of the last anons is pretty correct to me :

    x1 -> (1370685 -
    3 sqrt[208548352065])/1370,
    x2 -> 6, x3 -> 10, x4 -> 15, x5 -> 6,
    x6 -> -3, x7 -> -7, x8 -> -16, x9 -> -1,
    x10 -> 2001 + (-1370685 + 3 sqrt[208548352065])/1370

    this constitutes a proof by explicit construction. voila!

    ReplyDelete
  41. Solution can wait till WED, but could you tell us the answer? I think many of us worked a lot on the problem and we deserve it...

    What I really enjoy is that I still have no clue whether the statement is true or false... I think the nicest would be an existential argument for the existence of a solution without finding one. Is this the case?

    ReplyDelete
  42. Anon two back: sqrt(208...) is not rational,
    so not a solution.

    domotorp- I have added to the post a POINTER
    to the answer to just the question of IS there
    a solution or not. So you can click on that,
    but people do not have to if they want to keep working on it without knowing.

    ReplyDelete
  43. Dear Anon who send me correct solution which I blocked (to allow others to not be spoiled):
    I will include your solution (which is different
    from mine and my HS students and someone else who emailed me) in what I post on WED. If you email me your name and proof that you are you (e.g., the
    solution) then I will include your name.

    ReplyDelete
  44. A couple hours of programming and a some computing yielded an answer to the question. Doesnt mean I could do it during an exam. Wont spoil it before Wed by saying what the answer is.

    ReplyDelete
  45. In the second equation,
    (x_1)*(x_2)*(x_3)*...*(x_9) + (x_2)*(x_3)*...*(x_10) + ... = (x_1)*(x_2)*(x_3)*...*(x_10),
    RHS divides x_1, so in LHS (x_2)*(x_3)*..*(x_10) must divide x_1 ( and same for the rest of the terms ). If x_1 is a prime, then there should be an x_2 that divides x_1. RHS divides x_1*x_2, so in LHS, (x_3*x_4*x_5*...*x_10)(x_1 + bla*x_2) must divide (x_1)^2, which means one of x_3, x_4 etc must divide x_1, and so on. Primes have to proliferate. If x_1 is not a prime, then the same applies to it's prime factors.
    So, x_i are either primes themselves, or they are multiples of product of all prime factors of all x_i. ( Not entirely true, for ex. 3, 4, 12, 12, 12, 12, 12 is possible...4 is not a prime, but enough for the argument )

    Applying...
    If 2 is the only prime, then in the binary-expansion it doesn't fit. Only 3 obviously doesn't work as 2011 is quite close to twice 2^10.
    If both 2 and 3 have to exist, then as Anon pointed out 2297 happens : 2 + 3 + ( can't have 6 ) + 12 + (can't have another 12 ) + ...
    If both 2 and 5 have to exist, then you'll only get numbers ending in 10.
    In case of 3 and 4, you'll get (1/3) + (1/4) which makes 7/12 leaving 5/12 for the rest, but minimum is 12 for the remaining numbers, and 5 12s only go to 60. Similar issues with (2,7), (3,5), (3,7), and the higher you go ( for the initial numbers ), the more trouble you'll have adding up the inverses to 1.

    Not a nice argument, doing it case-by-case, but any errors?

    ReplyDelete
  46. If it is allowed to use electronic devices, then the problem is very easy:
    2+10+11+17+17+20+20+22+22+1870 = 2011,
    1/2+1/10+1/11+1/17+1/17+1/20+1/20+1/22+1/22+1/1870 = 1.

    ReplyDelete
  47. I have found another solution. I killed one work day programming this problem, most of the time I was moving in wrong direction:
    [704, 4, 4, 4, 8, 704, 352, 176, 44, 11]

    ReplyDelete
  48. Will I get extra points if I found more than 10 solutions for the problem?

    [704, 4, 4, 4, 8, 704, 352, 176, 44, 11]
    [864, 3, 6, 8, 8, 8, 16, 18, 864, 216]
    [912, 3, 4, 4, 19, 24, 912, 57, 38, 38]
    [920, 10, 5, 10, 23, 23, 920, 92, 4, 4]
    [1080, 4, 4, 6, 9, 12, 12, 20, 432, 432]
    [1188, 3, 4, 6, 9, 9, 297, 297, 99, 99]
    [1232, 2, 7, 11, 14, 14, 16, 22, 616, 77]
    [1260, 2, 6, 12, 21, 630, 20, 20, 20, 20]
    [1440, 3, 5, 8, 12, 18, 480, 15, 15, 15]
    [1500, 6, 10, 10, 10, 10, 12, 375, 75, 3]
    [1560, 3, 6, 10, 10, 10, 10, 12, 312, 78]
    [1584, 2, 4, 24, 33, 36, 16, 264, 24, 24]
    [1680, 2, 4, 14, 14, 35, 35, 35, 96, 96]
    [1700, 2, 5, 10, 10, 34, 100, 50, 50, 50]


    I have virtually zero knowledge in the area and I don't know any theorems which can help me in this case. So, I have written a python program which tries to solve the problem with the starting number in 2.2000 range. Than, I subtract 1/n where n is one of divisors of the initial number with some extra magic.

    I wasted a working day trying to find the right approach for the problem. That's my third one and it worked. I can send the source code if you interested: vol at google.com

    ReplyDelete
  49. That's a few last solutions found by my program, which I wasn't patient enough to post in the previous post. I really enjoyed solving this problem.

    [1760, 2, 5, 11, 11, 40, 40, 32, 55, 55]
    [1800, 2, 6, 12, 18, 20, 20, 40, 18, 75]
    [1820, 2, 10, 14, 26, 26, 28, 65, 10, 10]
    [1840, 4, 5, 8, 8, 10, 10, 23, 23, 80]
    [1848, 4, 7, 8, 11, 22, 84, 9, 9, 9]
    [1872, 3, 8, 8, 8, 13, 13, 16, 18, 52]

    Surprisingly, it didn't found the [1870,...] solution posted by Anonymous above, so it seems there are much more solutions to the problem.

    ReplyDelete
  50. I am here to discuss about a simple topic in mathematics that is rational expression,Rational expressions is known as an expression that is the ratio of two polynomials.It is called as rational because one number is divided by the other that is like a ratio.
    quadratic formula calculator

    ReplyDelete