Topic awaiting preservation: Need help with a math trick question (Page 1 of 1)

Hi guys, 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?

You crossposter, you.

the way you describe it, I can't follow how this machine is supposed to work. Does it add digits or numbers?

I think he means numbers, although digits would work too, you'd just be limited by what base you're working in (base 10 gives you a max of N=9 {1,2,...,9}, base 16 gives you a max of N=15 {1,2,...,F}).

Seems like a pretty simple problem though, unless I'm misunderstanding something (definitely a possibility )

int[] numbers = {2, 3, 5, 2, 1, 4};
int N = numbers.Count -1; // 5 (Count includes the duplicate)
int sum = 0;

for(int i=0; i<=numbers.Count; i++) {
  sum += numbers[i];
  sum -= i;
}

Whatever value sum is at the end is the duplicate value.

--

Any sufficiently advanced bug is indistinguishable from a feature.

ok, if you have the n+1 numbers it's trivial
Seriously, what information do you have at the end, parity?

quote:

---

You are given an adding machine that sums a set of N+1 digits consisting of positive integers 1 to N

---

quote:

---

One (and only one) of the digits is repeated

---

From those two statements, you know what all the numbers are (except the duplicate).

For N=2
- you have 3 digits/numbers (N+1 = 2+1), and all must be between 1 and 2 inclusive
- 1, 2, X (where X is the duplicate)

For N=4
- 5 digits/numbers between 1 and 5 inclusive
- 1, 2, 3, 4, X (again X is the duplicate)

Forgive me if I'm being dense and reading something that isn't there, but I think with the way it's worded, it is trivial. Of course it doesn't necessarily mean something wasn't lost in translation though...

--

Any sufficiently advanced bug is indistinguishable from a feature.

Hmm, the problem does seem a tad odd. I would say, up to rearrangement, you have a sum of the form 1+...+N+x, and you want x.

So just subtract off 1+...+N=N(N+1)/2 ?

[edit]

greatest possible sum for N = 1+...+N+N < 1+...+(N+1)+1 = least possible sum for N+1

Therefore the following works independent of N (paste it into your address bar):

javascript:numberToTest=13;for(n=1,m=numberToTest;(m-=n)>n++;){};alert(m?m:'Impossible Sum')

(Edited by wrayal on 09-29-2010 00:50)