Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x.

Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y.

Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binary string) must contain at least one 1. So there is some digit where the binary representation of x differs from the binary representation of y. Let this digit be the ith digit.

Let's say that a number is good if the ith digit of its binary representation is a 1. Let's call numbers that aren't good bad. Observe that exactly one of x, y is good, and the other one is bad.

Let S be the number that we get by doing this:

  S = 0

  for j in 1..n:

    if j is good: S = S + j

    if j is bad: S = S - j

Let T be the number that we get by doing this:

  T = 0

  for j in our_list_of_numbers:

    if j is good: T = T + j

    if j is bad: T = T - j

We find that S - T = x + y or -(x + y). Since x + y is positive, we can find x + y in either case.

We have x + y and x - y, so we can find x and y.

Solution to problem 3: imagine that we have a car, car 1, that has a really big tank with a bunch of gas in it. Put car 1 somewhere on the track and have it drive one complete revolution. The amount of gas G in the tank of car 1 varies over time, but at some point P on the track, G reaches its minimum value. P has to be at a gas station. (Otherwise G would be lower at a point right in front of P.)

If we take our regular car and start it (with an empty tank) at point P, it's pretty easy to see that it'll make it all the way around the loop.

Because if it didn't, then at some point Q it would run out of gas. Q wouldn't be a gas station, otherwise our car would refuel; so there's some point Q' in between Q and the next gas station from Q. Then driving a car from P to Q' results in a net loss of gas. Then when car 1 drove around the track, it should have had less gas at Q' than it had at P. (That's not 100% obvious in the case where car 1 drove past point Q' before it drove past point P, but it follows from the fact that car 1 had the same amount of gas when it finished as when it started.) Contradiction.

Fuck yeah, I'm a badass.