Beer Pong Riddle

I’m sure many of you have played, or at least heard of, Beer Pong. For those of you who haven’t, read this first.

Remember the word problems you had to solve and that you hated? Well, I have one for you, except it’s a bit more complex than anything you’d have to solve in elementary school. I also think it’s slightly more intriguing as well, and you never know who you can impress at a bar by being able to solve this puzzle.

First, we’ll do a quick warmup.

How many cups would you need to build a beer pong triangle if the largest row of cups contained 3 cups? Well, that’s simple enough. The last row would be 3 cups, the middle row is 2 cups, and the first row is 1 cup. So, we would need 1 + 2 + 3 = 6 cups. What if the largest row contained 5 cups? Well, now we have 5 cups in the back, 4 cups in the next row, …, all the way down to the first row which always contains 1 cup. Thus, we would need 1 + 2 + 3 + 4  + 5 = 15 cups.

Nice warmup. It’s time for the real question.

Plugging in numbers is fun and all, but what if I asked you how many cups are in a beer pong triangle where the last row contains N cups (where N is an integer)? Hmmm. That’s a bit trickier! If you wish, have a crack at solving this problem on your own. Regardless, I’ll give you some insight some general problem solving techniques, as well as walk you through a solution.

An equivalent problem is asking how to compute the sum 1 + 2 + 3 + ... + (N-2) + (N-1) + N. Let’s define F(N) = 1 + 2 + ... + (N-1) + N. We don’t know what F(N) is yet, but it refers to the sum of the integers from 1 up to N, and it’ll save me a lot of typing throughout this post.

Where do we even start? One place that I like to start is by drawing a picture. This is a classic problem solving technique. But what would I even draw? Maybe some beer pong triangles with their respective total cups:

From these drawings, we can deduce that there is a recurrence relation here. Observe that the “next” triangle in the sequence is built by using the previous triangle (represented by F(N-1)), and adding N cups to the bottom of the triangle. Hence, F(N) = F(N-1) + N.

Another picture you can draw is a plot:

It’s certainly not linear. It appears to be quadratic, meaning there is a good possibility that an N^2 will be floating around somewhere in the formula, but that’s just guesswork.

Another good strategy is to make a table of inputs and outputs. We’ll obviously include N and F(N). While we’re at it, let’s just add a column for F(N-1) since we know how it relates to F(N) (recall from above). Furthermore, since we have a hint that N^2 might be on of our terms, we’ll add that to the table too. Here’s the table:

Hmmm. Do you see a pattern? Take a good look at the table before reading on, see if you can spot anything.

It looks like if I take N^2 - F(N - 1), I get my answer, F(N)! So, that means F(N) = N^2 - F(N - 1). We also have a way of relating F(N) and F(N-1). We noticed in our earlier picture that F(N) = F(N-1) + N. With a bit of algebra (subtract N from both sides), this implies F(N-1) = F(N) - N. So, now we know that F(N) = N^2 - (F(N) - N), which simplifies out to F(N) = N^2 - F(N) + N. If we add F(N) to both sides, we get 2*F(N) = N^2 + N, which implies F(N) = (N^2 + N) / 2 = N*(N+1) / 2.

Let’s check the formula F(N) = N*(N+1)/2 works. We can do this by plugging in some values. Here’s the same table as before, but with N*(N+1)/2 as a column:

So,  if we need to make a beer pong triangle with 10 cups in the back row, then we’d need 10*(10+1)/2 = 10*11/2 = 55 cups. If we need 100 cups in the back row, then we’d need 100*(100+1)/2 = 100*101/2 = 5050 cups. Alternatively, 1+2+...+10 = 55, and 1+2+3+...+98+99+100 = 5050. Okay, we’re done, we’ve clearly shown that the sum of integers up to N is equal to N*(N+1)/2 for all N.

Just kidding! Haha. We haven’t shown crap. We’ve only shown it to be true for 1<=N<=6 (and maybe N=10 and N=100 for those of you who double checked). So in order to prove it for the rest of the integers, we can just keep plugging in values, right? No, no we can’t. The integers are infinite! If we keep trying to plug and chug, we will never be finished. Maybe, with a powerful computer and a couple hours of time, we could show the formula to be true for 1<=N<=1,000,000,000,000. We could do this by writing a program that computes 1+2+...+N and computes N*(N+1)/2, and then compare the results. But what about 1,000,000,000,001? It might not be true for 1,000,000,000,001. We have to come up with a better way than just checking the formula.

There are many ways you can show this to be true, but we’ll stick to the algebraic proof. When Gauss was in elementary school, he actually solved this problem. His teacher decided to punish his bad behavior by making him sum up the numbers from 1 all the way up to 100. But it didn’t take Gauss very long to come up with a solution. He didn’t add all the numbers from 1+2+...+100 manually, he came up with the formula we came up with, albeit in a slightly different fashion.

Note that we can write the sum from 1 to N as 1+2+3+...+N, or we could write it as N+(N-1)+(N-2)+...+1. One just counts up from 1 to N, the other counts down from N to 1, but their sum will be the same. This observation is key, and it’s what allowed Gauss to solve the problem when he was only a small child. Here’s an algebraic proof:

Now, we are done! That’s an algebraic proof, not a good guess with evidence.

Whenever you have a problem to solve, do yourself a favor and try something. Anything! I can’t tell you how many times I’ve tutored someone who has been “stuck” on a problem, and I ask what they’ve tried, and they don’t say anything! Drawing a picture is almost always a good place to start. It’s really the only tool we needed (plus high school algebra) to solve this problem.