Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hard problem from Bay Area Math Meet

  1. Jun 20, 2011 #1
    Hi everyone,

    For fun, I decided to check out some problems from a math competition designed for advanced high school students. I came across this problem that I can't seem to figure out. The contestants are suppose to be able to get it in 3 minutes (it's part of a 20 question test given in an hour). It's a multiple choice problem:

    18) Let [itex]N = 10^{2000}+2000[/itex] , and let S be the set of consecutive integers from 1 to N. In how many different ways can three consecutive integers be removed from S so that the average of the remaining numbers is an integer?

    A) 1
    B) 2
    C) 3
    D) 4
    E) 6


    Here is the link to the original problem. It's number 18.
    http://webserver.forest.org.uk/resource.aspx?id=27123
     
    Last edited: Jun 20, 2011
  2. jcsd
  3. Jun 20, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Hi CantorSet! :smile:

    That's quite a fun question, actually.

    Anyway, let us call S' the set of values {1,...,N-3} (so we removed the last three values. The average of this set is an integer.

    Now, to form all the possible set with three values, we may add some (maximum 3) values to S', but we have to make sure we substract the same number of values from S'.

    For example, we might add the value [itex]10^{2000}+2000[/itex] to S', but we also have to remove a value from S', say we remove 1. Then the average is

    [itex]Average(S')+\frac{(10^{2000}+2000)-1}{10^{2000}+1997}[/itex]

    This is not an integer, since the last term is not an integer.

    However, if we add [itex]10^{2000}+2000[/itex] and remove 3, then we get

    [itex]Average(S')+\frac{(10^{2000}+2000)-3}{10^{2000}+1997}[/itex]

    this is an integer, so this is a solution.

    Try to find out what possible combination we can have!
     
  4. Jun 20, 2011 #3
    Very nice.

    I bow before a master.

    :shy:
     
  5. Jun 21, 2011 #4

    uart

    User Avatar
    Science Advisor

    Sorry to bring this off topic but does anyone else think that the correct answer is not included in the multiple choice options for Q17 (the one about the regular 20-gon preceding the the OP's question).

    Maybe I'm misreading the question, maybe I'm doing something stupid, but it seems very easy with the answer being [itex]80 - 40 \cos(18^{\circ})[/itex], or [itex]40 + 80 \, \sin^2(9^{\circ})[/itex] if you prefer. None of the listed options are even numerically close to this ????
     
    Last edited: Jun 21, 2011
  6. Jun 21, 2011 #5

    disregardthat

    User Avatar
    Science Advisor

    I think they meant the sum of squares of lines connecting two points on the polygon. Pythagoras immediately yields 400.
     
  7. Jun 21, 2011 #6

    uart

    User Avatar
    Science Advisor

    Ok yeah it was just me being stupid. For some reason I was only taking the diagonals that passed through the center. :blushing:
     
  8. Jun 21, 2011 #7

    disregardthat

    User Avatar
    Science Advisor

    I agree, I have never seen cords being called diagonals before. The problem text could be clearer.
     
  9. Jun 22, 2011 #8
    The problem states that three consecutive integers must be removed from the set, so adding [itex]10^{2000}+2000[/itex] and then removing 3 from S' does not give a solution. Adding the numbers [itex]10^{2000}+1998[/itex], [itex]10^{2000}+1999[/itex], and [itex]10^{2000}+2000[/itex] then removing 1, 2, and 3 will give the second solution. The process you are using in your post shows that this combination works. According to the link in the OP, the solution is that there are four different ways this can be done. I have absolutely no idea how to solve for the other two.
     
  10. Jun 22, 2011 #9
    Building off what micromass suggested.

    Starting with the average for S', let us add the three terminating numbers back to the average and also subtract three consecutive numbers: [itex]\{x,\ x+1,\ x+2\}[/itex]. That is we consider

    [itex]\bar{S'}+\frac{3\cdot10^{2000}+3\cdot1999-(3x+3)}{10^{2000}+1997}= \bar{S'} + \frac{3(10^{2000}+1998-x)}{10^{2000}+1997}[/itex]

    the quotient of the latter fraction varies from 3 to 0 since x varies from 1 to 10^2000+1998 and so there can be a maximum of four integral values, namely 0, 1, 2, 3. Notice also that

    [itex]10^{2000}+1997\equiv1+2\equiv0\ (mod\ 3)[/itex]

    so the denominator is divisible by 3. We can attain all four values as follows: Let [itex]m=\frac{10^{2000}+1997}{3}[/itex]. Since the term 10^2000+1998-x varies continuously from 0 to 10^2000+1997 we can take the following values for x:

    [itex]x_{3}=1[/itex]

    [itex]x_{2}=m+1[/itex]

    [itex]x_{1}=2m+1[/itex]

    [itex]x_{0}=3m+1[/itex]

    which will give the quotients of 3, 2, 1 and 0 respectively. Thus there are four and only four ways to remove three consecutive numbers from the set so that the average of the remaining set is an integer.
     
    Last edited: Jun 22, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Hard problem from Bay Area Math Meet
  1. Very HARD maths question (Replies: 18)

  2. Hard Math Problem (Replies: 5)

  3. Area problem (Replies: 11)

Loading...