Handshakes

10 handshakes were exchanged at the end of a party. Assuming that everyone shook hands with everyone else at the party, how many people were at the party?

I saw the above problem posted in set of problems and it caught my interest. My approach was guess and check. I used pictures to help organize my thoughts.

What if there were only 2 people at the party? Naturally, they would only shake hands with each other and only 1 handshake would occur. We can represent this with a picture:

picture 1

For those of you who remember my brainteaser post, this is a graph! The dots represent the people at the party and the line between them represents a handshake.

Ok, let’s try a more interesting party, 3 people. Person 1 and 2 will shake hands, person 1 and 3 will shake hands, and person 2 and 3 will shake hands. Here is a picture:

picture 2

Clearly 3 handshakes take place at this party. The 3 lines represent this fact.

For a party of 4 people the verbiage is going to get complicated. I am going to let the picture do the talking:

picture 3

And 5:

picture 4

Sweet! We found our answer. We need 5 dots to get a total of 10 lines. Or in the language of the problem, we need a party of 5 people to get 10 handshakes. It is amazing to me that the framework of graph theory can have so many applications. This one of the strengths of mathematics; abstract structures can have a multitude of useful applications.

Leave a comment

Filed under Uncategorized

Probability Sums

The other day as I was perusing the MTBoS, I found an interesting problem.

“5 distinct numbers are chosen at random from {1,2,3,4,5,6,7,8,9}.

P(k) = probability their sum = k.

What are some of the ways you can find this in general?

What sum is/are the least likely?

Which sum is/are most likely?”

http://matharguments180.blogspot.ca/2014/10/269-probability-sums.html

At first, I started trying to make different numbers with different sums. For example: choose 2,3,5,6,7 and you get 2+3+5+6+7 = 23.

Then I realized there would be many possible sums. 126 in fact.1

I didn’t really feel like working with all 126 of those different sums so I wrote a quick script in Python to do it for me. Here are the results:

sums table

You can clearly see that 25 is the most likely sum with 12 ways of making 25. For fun, here are all 12 ways of making 25:

[1, 2, 5, 8, 9]
[1, 2, 6, 7, 9]
[1, 3, 4, 8, 9]
[1, 3, 5, 7, 9]
[1, 3, 6, 7, 8]
[1, 4, 5, 6, 9]
[1, 4, 5, 7, 8]
[2, 3, 4, 7, 9]
[2, 3, 5, 6, 9]
[2, 3, 5, 7, 8]
[2, 4, 5, 6, 8]
[3, 4, 5, 6, 7]

 

Also, 15, 16, 34, and 35 are the least likely sums. Since the table is symmetric about 25, this also means that, on average, your sum will be 25. Problem solved.

 

1You have to select 5 numbers from the set of 9 total. This corresponds to the mathematical idea of “choose.” We have 9 choose 5 = 126 possible options

Leave a comment

Filed under Uncategorized

Seats and Grades

I often have ideas for research questions that would be interesting but very impractical. My most recent question was how do seating arrangements affect student grades?

I would allow my students to pick their seat but they would have to stay in the same seat throughout the year. At the end of the year, I would record each student’s final grade in a spreadsheet along with his or her seat choice. After years of data, I could analyze how grades are correlated with seat choice!

Sadly, this idea is at least a few years away. Therefore, in the meantime, I created some fake data to display how this concept could, in theory, play out. Below is a heat map of the grades of a fictitious class. The cells are greener if the mark is higher and redder if the mark is lower:

rand1

My hope would be that out of the randomness, some type of pattern would emerge. Maybe the stereotype is true and the strong students sit at the front while the weak students sit at the back. If I condensed the years of data into a graphic, it might look something like this:

heat map gif

At first, the data seems random, but as the years progress you can clearly see that the higher grades are clustered near the front and the lower grades at the back. Maybe this is true, maybe it’s not, maybe one day I’ll know for sure. Until then.

2 Comments

Filed under Uncategorized

Odd Sums Re-Revisited

In my previous post you may have noticed that I neglected to prove one of the important results. One of my readers requested I post a formal proof. So here it is. Be warned, this is some serious stuff.

Consider the sequence of odd numbers:

1, 3, 5, 7, …

We want to prove:

\displaystyle\sum_{i=1}^{k} a_i \div \displaystyle\sum_{i=k+1}^{2k} a_i = \dfrac{1}{3}

Let’s start with something easier. For any arithmetic sequence:

a1, a2, a3, …, an

The sum of the first n terms is:

S_n = \dfrac{n(a_1+a_n)}{2}

Instead of giving a proof for this lemma, I will elect to show a conceiving example.

How would we add up the numbers 1 to 100?

Write the sum:

S = 1 + 2 + 3 + … + 98 + 99 + 100

Write the sum in reverse:

S = 100 + 99 + 98 + … + 3 + 2 + 1

Add these two sums together:

2S = 101 + 101 + 101 + … + 101 + 101 + 101

Simplify:

2S = 100 * 101

Solve for S:

S = 100 * 101 ÷ 2

So in general:

S_n = \dfrac{n(a_1+a_n)}{2}

Now using this formula we can prove the general result.

\displaystyle\sum_{i=1}^{k} a_i = \dfrac{k(1+(2k-1))}{2} = \dfrac{k(2k)}{2} = k^2

\displaystyle\sum_{i=k+1}^{2k} a_i = \dfrac{k((2k+1) +(4k-1))}{2} = \dfrac{k(6k)}{2} = 3k^2

Hence:

\displaystyle\sum_{i=1}^{k} a_i \div \displaystyle\sum_{i=k+1}^{2k} a_i = \dfrac{k^2}{3k^2} = \dfrac{1}{3}

Leave a comment

Filed under Uncategorized

Odd Sums Revisited

In a previous post, I investigated the sequence of odd numbers:

1, 3, 5, 7, 9, 11, \ldots

In particular, I investigated the ratio between the sum of the first “k terms” and the sum of the next “k terms.” I found that the ratio was always 1/3. I attempted this investigation with the sequence of even numbers and the ratio failed to be constant.

I recently had a brain wave to continue the investigation. Here was my question: “what sequences of numbers have consistent ratios when you sum the first k terms and the next k terms?”

After a bit of investigation, I found another sequence!

2, 6, 10, 14, 18, 22, \ldots

Here is the ratio of the first term and the second term:

\dfrac{2}{6} = \dfrac{1}{3}

The ratio between the first 2 terms and the next 2 terms:

\dfrac{2 + 6 }{10 + 14} = \dfrac{8}{24} = \dfrac{1}{3}

The ratio between the first 3 terms and the next 3 terms:

\dfrac{2 + 6 + 10}{14 + 18 + 22} = \dfrac{18}{54} = \dfrac{1}{3}

We have a constant ratio! What is even more interesting is that this ratio is 1/3, just like before! Below is another sequence that works:

3, 9, 15, 21, 27, 33, \ldots

And another:

4, 12, 20, 28, 36, 44, \ldots

Here is one that uses decimals:

1.1, 3.3, 5.5, 7.7, 9.9, 12.1, 14.3, \ldots

 Or how about negative numbers?

-5, -15, -25, -35, -45, -55, -65, -75, \ldots

In fact, there are an infinite number of different sequences. All of these sequences share the exact same consistency as the original sequence. The ratio will always be 1/3.1 Insights like this are what make mathematics truly beautiful.1

 

 

1Below is the method I used to generate these new sequences. First, we need to represent the sequence in general. We will restrict ourselves to arithmetic sequences for this post. Hence, the general sequence can be written as:

a, a+d, a+2d, a+3d, a+4d, \ldots

We want our arithmetic sequence to have a constant ratio. We could rephrase this requirement as “the ratio of the first and second term must be equal to the ratio of the first 2 terms and the next 2 terms.” In symbols, this means:

\dfrac{a}{a + d} = \dfrac{a + (a + d)}{(a + 2d) + (a + 3d)}

Simplifying:

\dfrac{a}{a + d} = \dfrac{2a + d}{2a + 5d}
a(2a + 5d) = (a + d)(2a + d)

2a^2+ 5ad = 2a^2 + 2ad + ad + d^2

2a^2 + 5ad = 2a^2 + 3ad + d^2

5ad = 3ad + d^2

0 = -2ad + d^2

0 = d(d - 2a)

Since we want our sequence to be interesting, d ≠ 0 and a ≠ 0. Thus, d = 2a. Hence, any sequence that satisfies the condition d = 2a will exhibit our desired property.2

Now our general sequence looks like this:

a, a+2a, a+4a, a+6a, a+8a, \ldots

a, 3a, 5a, 7a, 9a, \ldots

From this, we see that the ratio will be:

\dfrac{a}{3a} = \dfrac{1}{3}

Since the a’s cancel, our general sequence reduces to our original sequence of odd numbers. Thus, all the properties that we discovered about the sequence of odd numbers will apply to all these new sequences. This also means that the only ratio ever possible is 1/3. Amazing!

 

2 I have another footnote for two reasons. First, I think it is pretty meta to put a footnote inside a footnote. Second, I actually only showed that the condition d = 2a will force the ratio of the first and second terms equal to the ratio of the sum of the first 2 terms and the next 2 terms.

I neglected to prove that this generalized to the sum of the first k terms and the sum of the next k terms. In other words, I didn’t prove that:

\dfrac{a + (a + d) + (a + 2d) + \ldots + (a + (k - 1)d)}{(a + kd) + (a + (k + 1)d) + \ldots + (a + 2kd)} = \dfrac{1}{3}

It should be obvious to the reader that if you replace d with 2a and factor out an a, the above ratio will reduce to:

\dfrac{1 + 3 + 5 + \dots + (2k - 1)}{(2k + 1) + (2k + 3) + \dots + (4k + 1)}

This is equivalent to the original ratio investigated in the first post.

If anyone is still reading at this point, they may notice that in the original post I didn’t prove that the above ratio was equal to 1/3. You would be correct. The proof is left as an exercise for the reader ;)

Leave a comment

Filed under Uncategorized

Non-Transitive Dice Follow up

Yesterday I asked you to pick the best die. If you guessed Blue, you would be wrong. Red is all wrong. Likewise, Green is incorrect. The correct answer is that…

There is no best die!

As crazy as this might sound, you have all experience this type of situation before. Consider rock-scissors-paper:

pic1 other

In the above game, there is no best choice. Each symbol beats one symbol and loses to the other. The dice are similar. Consider the following diagram:

pic2

This is a chart displaying the possible outcomes between for Blue vs Red. It is clear that he Blue die will win more often, 21 times out of 36. The red die will only win 15 times out of 36. You can construct similar tables for Red vs Green and Green vs Blue. The results are summarized in the following diagram:

pic 3

These dice are called “non-transitive” because the ability to win does not transfer. Red is better than Green, and Green is better than Blue, but Red is not better than Blue.

Warren Buffett is known to be a fan of non-transitive dice. Buffett once attempted to win a game of dice with Bill Gates using non-transitive dice. Buffett suggested that each of them choose one of the dice, then discard the other. They would bet on who would roll the highest number most often. Buffett offered to let Gates pick his die first. This suggestion instantly aroused Gates’s curiosity. He asked to examine the dice, after which he demanded that Buffett choose first.

 

1 Comment

Filed under Uncategorized

Non-Transitive Dice

A normal die has 6 sides with the numbers 1 through 6. However, different dice can have different numbers

Ex: 2, 4, 6, 8, 10, 12

Which die is the best for highest rolling in a head to head match?

Blue: 0, 3, 5, 7, 7, 7

Red: 2, 2, 4, 4, 6, 9

Green: 1, 1, 1, 8, 8, 8

I will post the answer tomorrow.

Leave a comment

Filed under Uncategorized