2.5 Series Summation

Here is a famous story about the legendary mathematician/physicist Gauss: When he was a child, his teacher gave the children a boring assignment to add the numbers from 1 to 100. To the amazement of the teacher, Gauss turned in his answer in less than a minute. Here is his approach:

\begin{aligned}\sum_{n=1}^{100}n&=1+2+\cdots+99+100\\\sum_{n=1}^{100}n&=100+99+\cdots+2+1\\2\sum_{n=1}^{100}n&=101+101+\cdots+101+101=101\times100\end{aligned}

\Rightarrow\sum_{n=1}^{100}n=\frac{100\times101}{2}

This approach can be generalized to any integer $N$ : $\displaystyle\sum_{n=1}^{N}n=\frac{N(N+1)}{2}$

The summation formula for consecutive squares may not be as intuitive:

\sum_{n=1}^{N}n^2=\frac{N(N+1)(2N+1)}{6}=\frac{N^3}{3}+\frac{N^2}{2}+\frac{N}{6}.

But if we correctly guess that $\displaystyle\sum_{n=1}^{N}n^2=aN^3+bN^2+cN+d$ and apply the initial conditions

\begin{aligned}N=0&\Rightarrow0=d\\N=1&\Rightarrow1=a+b+c+d\\N=2&\Rightarrow5=8a+4b+2c+d\\N=3&\Rightarrow14=27a+9b+3c+d\end{aligned},

we will have the solution that $a=1/3,\ b=1/2,\ c=1/6,\ d=0$ . We can then easily show that the same equation applies to all $N$ by induction.

Clock pieces

A clock (numbered 1 – 12 clockwise) fell off the wall and broke into three pieces. You find that the sums of the numbers on each piece are equal. What are the numbers on each piece? (No strange-shaped piece is allowed.)

Solution: Using the summation equation, $\displaystyle\sum_{n=1}^{12}n=\frac{12\times13}{2}=78$ . So the numbers on each piece must sum up to 26. Some interviewees mistakenly assume that the numbers on each piece have to be continuous because no strange-shaped piece is allowed. It’s easy to see that 5, 6, 7 and 8 add up to 26. Then the interviewees’ thinking gets stuck because they cannot find more consecutive numbers that add up to 26.

Such an assumption is not correct since 12 and 1 are continuous on a clock. Once that wrong assumption is removed, it becomes clear that $12+1=13$ and $11+2=13$ . So the second piece is 11, 12, 1 and 2; the third piece is 3, 4, 9 and 10.

Missing integers

Suppose we have 98 distinct integers from 1 to 100. What is a good way to find out the two missing integers (within [1, 100])?

Solution: Denote the missing integers as $x$ and $y$ , and the existing ones are $z_1,\cdots,z_{98}$ . Applying the summation equations, we have

\sum_{n=1}^{100}n=x+y+\sum_{i=1}^{98}z_i\Rightarrow x+y=\frac{100\times101}{2}-\sum_{i=1}^{98}z_i

\sum_{n=1}^{100}n^2=x^2+y^2+\sum_{i=1}^{98}z_i^2\Rightarrow x^2+y^2=\frac{100^3}{3}+\frac{100^2}{2}+\frac{100}{6}-\sum_{i=1}^{98}z_i^2

Using these two equations, we can easily solve $x$ and $y$ . If you implement this strategy using a computer program, it is apparent that the algorithm has a complexity of $O(n)$ for two missing integers in 1 to $n$ .

Counterfeit coins I

There are 10 bags with 100 identical coins in each bag. In all bags but one, each coin weighs 10 grams. However, all the coins in the counterfeit bag weigh either 9 or 11 grams. Can you find the counterfeit bag in only one weighing, using a digital scale that tells the exact weight?⁹

Solution: Yes, we can identify the counterfeit bag using one measurement. Take 1 coin out of the first bag, 2 out of the second bag, 3 out the third bag, …, and 10 coins out of the tenth bag. All together, there are $\displaystyle\sum_{i=1}^{10}n=55$ coins. If there were no counterfeit coins, they should weigh 550 grams. Let’s assume the $i$ -th bag is the counterfeit bag, there will be $i$ counterfeit coins, so the final weight will be $550\pm i$ . Since $i$ is distinct for each bag, we can identify the counterfeit coin bag as well as whether the counterfeit coins are lighter or heavier than the real coins using $550\pm i$ .

This is not the only answer: we can choose other numbers of coins from each bag as long as they are all different numbers.

Glass balls

You are holding two glass balls in a 100-story building. If a ball is thrown out of the window, it will not break if the floor number is less than $X$ , and it will always break if 20the floor number is equal to or greater than $X$ . You would like to determine $X$ . What is the strategy that will minimize the number of drops for the worst case scenario?¹⁰

Solution: Suppose that we have a strategy with a maximum of $N$ throws. For the first throw of ball one, we can try the $N$ -th floor. If the ball breaks, we can start to try the second ball from the first floor and increase the floor number by one until the second ball breaks. At most, there are $N-1$ floors to test. So a maximum of $N$ throws are enough to cover all possibilities. If the first ball thrown out of $N$ -th floor does not break, we have $N-1$ throws left. This time we can only increase the floor number by $N-1$ for the first ball since the second ball can only cover $N-2$ floors if the first ball breaks. If the first ball thrown out of $(2N-1)$ th floor does not break, we have $N-2$ throws left. So we can only increase the floor number by $N-2$ for the first ball since the second ball can only cover $N-3$ floors if the first ball breaks…

Using such logic, we can see that the number of floors that these two balls can cover with a maximum of $N$ throws is $N+(N-1)+\cdots+1=N(N+1)/2$ . In order to cover 100 stories, we need to have $N(N+1)/2\geq100$ . Taking the smallest integer, we have $N=14$ . Basically, we start the first ball on the 14th floor, if the ball breaks, we can use the second ball to try floors $1,2,\cdots,13$ with a maximum throws of 14 (when the 13th or the 14th floor is $X$ ). If the first ball does not break, we will try the first ball on the $14+(14-1)=27$ th floor. If it breaks, we can use the second ball to cover floors $15,16,\cdots,26$ with a total maximum throws of 14 as well…