Hard problem from Bay Area Math Meet

[CantorSet]

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 N = 10^{2000}+2000 , 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

 

[micromass]

Hi CantorSet!

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 10^{2000}+2000 to S', but we also have to remove a value from S', say we remove 1. Then the average is

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

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

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

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

this is an integer, so this is a solution.

Try to find out what possible combination we can have!

 

[CantorSet]

Very nice.

I bow before a master.

:shy:

 

[uart]

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 80 - 40 \cos(18^{\circ}), or 40 + 80 \, \sin^2(9^{\circ}) if you prefer. None of the listed options are even numerically close to this ?

 

[disregardthat]

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 80 - 40 \cos(18^{\circ}), or 40 + 80 \, \sin^2(9^{\circ}) if you prefer. None of the listed options are even numerically close to this ?

I think they meant the sum of squares of lines connecting two points on the polygon. Pythagoras immediately yields 400.

 

[uart]

I think they meant the sum of squares of lines connecting two points on the polygon. Pythagoras immediately yields 400.

Ok yeah it was just me being stupid. For some reason I was only taking the diagonals that passed through the center.

 

[disregardthat]

For some reason I was only taking the diagonals that passed through the center.

I agree, I have never seen cords being called diagonals before. The problem text could be clearer.

 

[Dschumanji]

Hi CantorSet!

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 10^{2000}+2000 to S', but we also have to remove a value from S', say we remove 1. Then the average is

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

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

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

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

this is an integer, so this is a solution.

Try to find out what possible combination we can have!

The problem states that three consecutive integers must be removed from the set, so adding 10^{2000}+2000 and then removing 3 from S' does not give a solution. Adding the numbers 10^{2000}+1998, 10^{2000}+1999, and 10^{2000}+2000 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.

 

[Yuqing]

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: \{x,\ x+1,\ x+2\}. That is we consider

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

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

10^{2000}+1997\equiv1+2\equiv0\ (mod\ 3)

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

x_{3}=1

x_{2}=m+1

x_{1}=2m+1

x_{0}=3m+1

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.