1
$\begingroup$

I wasnt sure where to ask this but since this is an algorithmic question here it goes. I've come face to face with a math problem and can't seem to get over it for the last couple of days. It goes like this:

You are given an adding machine that sums a set of N+1 digits consisting of positive integers 1 to N as it's given the numbers (e.g. the machine is given 3 as the first number and outputs 3. It's then given 6 as the second number and outputs 9. It's given 11 as the third number and outputs 20. Etcetera until it has processed N+1 numbers). One (and only one) of the digits is repeated. How do you determine which number is repeated?

It seems like a trick question and I'd be really pissed off it is just that a question to which the answer is 'not possible' - any ideas here?

  • 1
    Why use the word digit at all?2010-09-16

1 Answers 1

5

We know that $1+2+\ldots +N = \frac{1}{2}N(N+1)$. Suppose the end amount is $T$ then the repeated number is $T-\frac{1}{2}N(N+1)$.

  • 0
    WHat is this branch of mathematics called btw?2010-09-16
  • 0
    The numbers of the form $\frac{1}{2}N(N+1)$ are triangle numbers. See http://en.wikipedia.org/wiki/Triangular_number2010-09-16
  • 0
    @Ali: I would say it falls under arithmetic. Lookup Arithmetic Progressions on the web.2010-09-16