Counting Can Be Really Tough

Factorial, Permutation, and Combination

How do I count?

On most calculators, you can find a factorial button (displayed in the picture here as x!, however it may just be ! on other calculators), a permutation button (nPr), and a combination button (nCr).  

I'm going to attempt at explaining why you would ever need such buttons.  If you don't have a calculator handy with these buttons, open up the computational knowledge engine WolframAlpha and standby. 

Factorial First

Suppose you have 3 songs that you would like to listen to. Let's call those songs A, B, and C, and let's assume they are in a playlist on your smart device.  You push the random playback button.  How many ways can your smart device play back those songs for you?  

This question can be answered using factorials. Before I show you how this works, let's simply list all the possible ways and count them up:

{ABC, ACB, BAC, BCA, CAB, CBA} 

There seem to be only six ways the smart device can play the songs back to me.  What if there were 20 songs?  Listing them out is not an option anymore, so we need a clever way of counting when we have more than 3 songs. 

Here is how we could have obtained the 6 ways systematically.  Your smart device must choose from 3 songs randomly to play the first song.  Once that is chosen, the device must choose randomly from two remaining songs for the second choice.  There is only one song remaining to choose from for the final song.  Thus, the number of ways to play 3 songs randomly is 3*2*1 = 6.  To visualize why we multiply, here is a tree diagram. 

Descending products like these are factorials. Try it now.  Plug in 3! into your calculator by pushing 3 first and then the factorial button.  Or, simply type in 3! into WolframAlpha. 

Now, try 20! in WolframAlpha. You should get 2 quintillion, 432 quadrillion, 902 trillion, 8 billion, 176 million, 640 thousand.  Or 2,432,902,008,176,640,000. 

That would have taken a while to list out. 

Permutations

Suppose your playlist has 5 songs instead of 3.  Let's call the songs A, B, C, D, and E.  From the previous section, we learned that the number of ways our smart device can play them all back to us is 5! = 120.  

However, we have time to listen to only two of them.  How many ways can our smart device do this? We will first count them up the old fashioned way, by listing all the possibilities.  Here goes.

{AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED}

It looks like there are 20.  What if the playlist has 20 songs and you have time to listen to 6?  Do you want to list them out? Nope. So, let's find an easier way of getting that 20 and apply it to the more difficult problem.  

The smart device had 5 choices of songs for the first song.  Once it chose that song, it had 4 choices for the second.  So, the final count is 5*4=20.  Unlike the factorial, this product does not descend all the way down to 1.  It only considers permuting 2 of 5 values.  

On the calculator function, n=5 and r=2.  So, plug in 5 nPr 2 into WolframAlpha to see what you get.  

Likewise, 20 nPr 6 can be obtained by plugging this in OR by plugging 20*19*18*17*16*15 into the calculator.  One method is a little more quick and efficient.  You should confirm that this value is 27,907,200.  

Combinations

Suppose someone displays in front of you five gifts. Let's call them gift A, B, C, D, and E for simplicity.  You are given the opportunity to select two of these gifts for yourself.  How many ways can you do this?  How is this different from the previous problem with listening to 2 of 5 songs? 

If we have gifts AB or BA we have the same two gifts, and we don't really care about the order in which we select them.  We need a way of not counting BOTH of those.  So, refining the list above, we will get

{AB, AC, AD, AE, BC, BD, BE, CD, CE, DE}

This can be quickly obtained by using nCr.  Here again, n=5 and r=2 because you want to select 2 of 5 things.  Plug in 5 nCr 2 to confirm the value 10. 

How many ways can you be dealt two hole cards in Texas Hold 'Em?  How many ways can you be dealt five cards in Five Card Draw?  For these two examples, n=52.  For the first example r=2, and for the second, r=5.  

Use WolframAlpha again to find 52 nCr 2 and 52 nCr 5.  

These numbers are 1326 and 2,598,960, respectively.  

Congratulations! You've learned a few basics in counting!

Want to have more fun with WolframAlpha? Plug in your birthday to find out how old you are in days.  Plug in the city you live in for your city's demographics and income statistics among other things.  Type in "maximum value of y=x-x^2" to find out that the maximum value of y=1/4 is obtained when x=1/2. Cool, huh?  

The Price is Right Wheel: How to Spin it Optimally

Price Is Right Wheel has 20 sectors

The Problem

This is the 97th Riddle proposed by The Riddler from FiveThirtyEight.

The three contestants that win all go head to head at this wheel at a chance to advance to the Showcase Showdown.  The one with the least amount of money goes first (the worst position in this game), while the one that won the most goes last.  

The first player must get to as close to 100 as they can without going over. They are allowed a maximum of two spins.  The wheel has 20 slots, with the lowest being 5, and the last being 100, all the rest increase in increments of 5 and are distributed all around the wheel.  

If they go over, they are automatically out of the game. 

The second player must beat the first player's number, and have a number that the last player cannot beat. 

The last player, if the first two bust, automatically advances.  Otherwise, they have to beat whoever is in front of them.  

What strategy should the first player adopt to give them the best chance at advancing to the Showcase Showdown?  Specifically, at what value (or above) should the first player definitely not spin again, and therefore below what value should the first player definitely spin again?  

An Attempt at a Solution

To answer this question, we are interested in two conditional probabilities: 

1. Under the condition that we stay with this number, what is the probability that we win?
2. Under the condition that we spin again with this number, what is the probability that we will not bust? 

If the probability calculated in 1 is larger than the probability calculated in 2, than we should stay with that number.  Otherwise, we should spin again.  Our goal is to find the largest such number for which the probability of 1 is greater than the probability of 2.  

Before going any further, let's make calculations a little easier by assuming that the values 1-20 are on the wheel instead of 5-100 in increments of 5.  So now, we must try and add to 20 and not go over.  

Player 2's Perspective

Suppose for the moment that player 1 has busted, and that player 2 only has to worry about player 3.  Also, let's assume their first spin is a 10.  Then the conditional probability for #2 above is 50%, since they will not bust only if a 1-10 is spun again.  

The probability that player 3 will win is more than 50% since that is the probability that they win on the first spin. 

Thus, in this situation, they should spin again.  So, we will only consider values above 10.  Let the value of player 2's first spin be X. For probability 2, we will need to also consider S, the sum of their two spins.  

Let the value of player 3's first spin be Y and the sum of their two spins be S (if they end up spinning twice).  

The notation for the probabilities in #1 and #2 above are given as: 

1. P(Y < X) * P(S < X or S > 20 | Y < X) + 0.5*(P(Y = X)+P(Y < X)*P(S = X | Y < X))
2. P(S < 21 | X) = (X-20)/20

The first probability can be explained in this way. If I stay with X, then in order to win, player 3 must spin a value less than X, and then given that... when they spin a 2nd time, their sum must be lower than X or above 20, OR, their first spin must match X or their sum must match X given their first spin was lower and they win the spin-off.  

The second probability is easier.  If X is 15 for example, the probability of not busting, is the probability of spinning a 1, 2, 3, 4, or 5, which is 5/20.  This is the same as (20-X)/20 for when X=15. This works for all other values of X.

For those mathematically inclined, I hope you can confirm that

• P(Y < X) = (X-1)/20, and that 
• P(S < X or S > 20 | Y < X) = (X-1)^2/400, so that the product is 
• (X-1)^3/8000

This is then summed with 0.5 multiplied by

• P(Y=X) = 1/20, plus
• (X-1)/400

It is OK to skip that part. Let's compare these probabilities for some different values. 

When X=13, the probability in #1 is 0.276 while the probability in #2 is 0.35.  Therefore, player 2 should spin again. 

When X=14, the probability in #1 is 0.316 while the probability in #2 is 0.3. Therefore, player 2 should stay. 

Now, player 2 can only do this if player 1 has spun something less than or equal to 14, or has busted.  They must beat our value otherwise.  Assuming player 2 will play in this optimal way, let's continue with the calculations for player 1. 

Player 1's Perspective

From watching several YouTube videos involving spin-offs, it seems that spin-offs occur among two contestants at a time.  So, if the first two tie, they spin-off to go against the third contestant, on which another spin-off can occur.  

So, the probabilities for player 1 to win must be the probability for player 2 to win squared.  Player 1 must defeat both player 2 and player 3.  

So, for X=14, the probability of player 1 winning is now .0998 while the probability of not busting on a second spin is 0.3. Player 1 should spin again.  

For X=15, the win probability is .149 while the probability of not busting is .25.  Player 1 should spin again. 

For X=16, the win probability is .217 while the probability of not busting is .20. Player 1 should stay.  

This is equivalent to getting 80 or more on the wheel in the Price is Right.  

Escaping Prison

The Problem

Last Friday, The Riddler posed quite the challenging problem.  Here it is in my own words.  

You are in prison with 99 other inmates (there are 100 of you).  The warden presents you with a game. Prisoners are to be randomly selected with replacement and taken into Cell Zero.  Inside Cell Zero, there are two levers that could be in any of the following configurations: 

Each prisoner that is let into Cell Zero can either declare "All prisoners have now been in Cell Zero" or move exactly one lever (and they must move exactly one lever).  

If the prisoner declares and is wrong, all prisoners are executed. 

If the prisoner declares and is correct, all prisoners go free. 

Once the game has begun, there can be no communication between prisoners.  What strategy at the outset will ensure that all prisoners go free?  

Common Questions

Do the prisoners know the original configuration of the levers?  NO.

Do we know which prisoner will be selected first?  NO.

Can prisoners be selected multiple times before another prisoner has ever visited Cell Zero?  YES.

A Solution

I think I have a solution to this.  It may not be the best, but here goes.

Since I have strong leadership skills among all the prisoners, I declare myself "the counter." My job is to only move the left lever UP, and count each time I do it.  If it is already in the up position, I just move the right lever down or up, regardless of its orientation. 

All other prisoners' job is to move the left lever DOWN exactly twice.  Once they have moved the left lever from the UP position to the DOWN position twice, they forever will move only the right lever.  If the left lever is already in the down position, they leave it be and move only the right lever. 

Once I have counted to 198, I declare everyone has been in Cell Zero. 

So Why Twice? And why does this work?  

When I first visit Cell Zero and the left lever is down, I have no way of knowing whether it started that way or if another prisoner moved it down from the up position.  So, when I move it up, I don't know whether I'm starting at 0 or counting an actual prisoner.  

Therefore, once I count to 99, I'm in a state of uncertainty. Have I counted all prisoners, or am I perhaps missing one?  This uncertainty is just that, uncertainty. Since I cannot be certain, we should devise a different strategy.  

By having all the prisoners pull the left lever down exactly twice, then I will eventually lift the left lever up 198 times. There is still now an uncertain state, and that is whether all prisoners have pulled the left lever down twice (a prisoner visited Cell Zero the first time before me with the left lever up and pulled it down), or there is still one out there that hasn't pulled it down a second time yet (the left lever started in the down position).  But that gives us the level of certainty that we need: that all the prisoners have been in Cell Zero at least once.  

Meta Level Up

In David Allen's "Getting Things Done", he talks of next actions. 

Sometimes, what makes it on our To-Do list is too vague, or just too big a project to be jotted down so simply. To tackle such things, you need next actions. Sometimes, these are hard to come up with. 

Whenever I struggle with next actions, I remove myself from the situation and level up, metaphysically speaking. I think in terms of the writer of my life. Since I'm writing it at this moment, it doesn't have to be myself in the situation. For example, it can be Dirk Diggler. 

So, it is now my job to write about what Dirk Diggler is going to do next to get this job done. This frame of mind helps the brainstorming go a little easier. (Especially if it someone you aspire to be like, or simply a super version of yourself. The use of Dirk Diggler is not a good example at all here, and is used primarily for humor.)

This 'leveling up' method works great with other things in life besides next actions. 

In Adam Grant's "Give and Take", I read about someone who was able to become a good negotiator for himself and his family by leveling up. He was able to eventually make a break through and negotiate better raises, better rent, and better other things in life by playing a role of a mentor for himself. He asked himself how he would instruct someone else to negotiate for themselves in the same situation. Then he followed those instructions and played the part of the mentee.

Next time you have a chore on the to-do list and are having a hard time coming up with a next action, try leveling up. Ask yourself, "What would Dirk Diggler do?" 

Airplane Seating Etiquette

Unlucky you, to be the last person to board a 100 seat plane. This is the setting of this week's riddle from Ollie on FiveThirtyEight. 

Here's the problem. The first person to board is a complete asshole. This guy is to airplane boarding as Martin Shkreli is to pharmaceuticals.  When this guy boards, he could care less about what seat he is actually assigned to, so he just chooses one at random.  

Each person after will sit in their assigned seat if it is available. If it isn't available, instead of causing a scene, they choose any of the remaining seats at random. 

Finally, it is your turn. What is the probability that you get to sit in your assigned seat? 

This problem isn't too difficult, so I encourage a little thought on it before reading on.

Ready for a solution?

First, let us simplify the problem by thinking of each passenger as numbers from 1 to 100, where 1 represents the asshole, and 100 represents you. Or should we just call it the collective us? The "royal we" so to speak? 

OK, now go through the plane and label all the passengers seats to which they are assigned with the same number.  

Now, let's go through one simulation to see how this works. Number 1 chooses a random number between 1 and 100.  Let's say it is 37. 

Passengers 2-36 board and sit in their seats. Passenger 37 boards and finds a complete assface in her seat. (Let's mark seat 1 with 37* for simplicity). Passenger 37 chooses a random number between 37 and 100 inclusive. Suppose it is 84.  

Passengers 38-83 board and sit in their seats. Passenger 84 boards and finds an unfortunate lady whose seat was taken by a toolbag in his seat. Seat number 37* is now changed to 84* (remember, this is the original asshead's seat).  Passenger 84 chooses a random number between 84 and 100.  Say it is 97.  

Passengers 85-96 board and take their seats, seat 84* is changed to 97*, and passenger 97 chooses a random number between 97 and 100.  To get this show on the road, suppose it is 100.  Damn. We lost our seat.  Passengers 98 and 99 take their seat and we get to sit in which seat?  That's right. Douchy McDoucherson's seat.  

This is an important observation.  

If we play these scenarios to conclusion time and time again, we will notice there are only two possible results for us. We sit in our seat, or the dickhead's. It turns out that either scenario is equally likely, so the answer ends up being 50%.  But let's offer a little more explanation.  

Each time a passenger is faced with a random choice (including the first time), choosing seat 1 or seat 100 has the same probability every time this happens. If either is chosen, all randomness is removed, and the rest of the boarding is determined. If seat 1 was chosen, all remaining passengers including us, get to sit in their own seat.  If seat 100 is chosen, all remaining passengers excluding us, get to sit in their own seat. We have to sit in meaniehead's seat.  

If another seat is chosen besides seat 1 or 100, then we repeat the situation above. Again, each time this happens, seat 1 and 100 are equally likely to get chosen. Hence, the 50%.  

If you are still not convinced, analyze the situation with a 2 seat airplane and then a 3 seat airplane. If you're brave enough try a 4.  If you're really brave, go 5.  They all produce a 1/2 probability of getting to sit in our own seat when we're last to board.  This should convince you that it will remain that way.

The Extension 

Let's try and find the average number of passengers that will get to sit in their seats.  The reason I suggested it is because I noticed 1 person on average would get their seat on a 2 seat plane, while 1+1/2 people on average get their seat on a 3 seat plane, 1+1/2+2/3 on a 4 seat plane, and 1+1/2+2/3+3/4 on a 5 seat plane. This led me to guess that an average of 1+1/2+2/3+3/4+...+98/99 (which approximately equals 94.82262) people would get seated on a 100 seat plane. 

So, I simulated it 1000 times and plotted a moving average using the following code in R: 

This helped me feel very comfortable with my guess. Still not satisfied, I had to think about why this was working out the way it was. 

I'm not sure even if this is the correct intuition, but I'll give it a shot.  With probability 1/100, the asshole will select his own seat, which will produce 100 passengers sitting in their own seats.  Given he doesn't select his seat, there is a 1/99 chance that the next person will select the first seat and then leave 98 passengers sitting in their own seats.  Given that the first two didn't sit in their own seats, there is a 1/98 chance that the next person will select seat 1, leaving 97 passengers sitting in their own seats.  And so on. This, when written out, looks like 

1/100(100)+1/99(98)+1/98(97)+ ... + 1/2(1) = 1+98/99+97/98+...+2/3+1/2,

which is the same as the sum I described above.

This is far from rigorous, but hopefully it satisfies most of you.

 

Random Permutations of Cars in Traffic

You want to drive a little over the speed limit. The person in front of you wants to go exactly the speed limit. This is going to be a long day.

Riddle #9 made the long day much more enjoyable.  Here is the riddle quoted from FiveThirtyEight: 

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

For example, if the car in the very front happens to be slowest, there will be exactly one group — everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be N groups — no car ever gets stuck behind a slower car.

Suppose each car is given a number between 1 and N.  The number 1 means it is the slowest car, and the number N is the fastest car.  There are N! possible permutations (that is "N factorial") of  the cars along the road.  Let's begin with the lead car.

The lead car will define the first group of cars with 100% certainty.  Either it will be in a group by itself (if it is the fastest), a group with several cars (if those several cars are faster than it), or the entire group of cars (if it is the slowest car).  Thus, the lead car will add 1 group to the entire total.

Now, to the second car.  If there are N cars, for every way that you can choose the lead car being faster than the second car, you can flip that permutation so that the lead car is slower than the second car. In other words, there is a 1/2 probability that the second car will define a new group, and a 1/2 probability it will be part of the group that the lead car is in.  Thus, the second car will add 1/2 of a group to the total on average.

To the third car, and beyond!!  For every way you can choose a lead car, 2nd car, and 3rd car, you can order the fastest (F), middle fastest (M), and slowest (S) in the following six different ways:

FMS   FSM   MFS   MSF   SFM   SMF

There are only two of the six permutations in which the slower of the three cars is the 3rd car, in which case, it will create its own group.  That has a 2/6=1/3 probability.  If it is either the fastest or middle fastest, it will become part of a group already in existence.  Thus, the 3rd car will create 1/3 of a group on average.

This continues.  The 4th car will create 1/4 of a group on average, the ith car will create 1/i of a group on average.

If there are N cars, then the line of cars will create $\sum_{i=1}^N \frac{1}{i}$ different groups on average.

I've been trying to figure out how to do math equations on blogspot and have been unsuccessful. Especially if you see code between dollar signs in the previous line. If that is the case it is supposed to be the shorthand notation for:

1+1/2+1/3+1/4+...+1/N

Can I Cross? Let Me Flip a Coin.

Let's face it, I'm an addict of these riddles.

This week's riddle from Ollie at FiveThirtyEight is a longer one:

You’re on the north shore of a river, and want to cross to the south, via a series of 13 bridges and six islands, which you can see in the diagram below. But, as you approach the water, night falls, a bad storm rolls in, and you’re forced to wait until morning to try to cross. Overnight, the storm could render some of the bridges unusable — it has a 50 percent chance of knocking out each of the bridges. (The chance is independent for each bridge.)

 Question 1: What’s the probability you will be able to cross the river in the morning? (You have no boat, can’t swim, can’t fix the bridges, etc. No tricks.)

Now imagine a different, wider river, with many more islands — in fact, arbitrarily many. Specifically, imagine that the islands are arrayed in an N-rows-by-N+1-columns grid — similar to before, where N happened to equal two — and connected by bridges to each adjacent island in the same way. Each island adjacent to the shore is also connected by a bridge to the shore. It would look something like this:

 Question 2: What’s the probability you’ll be able to cross this river in the morning, after the same storm — with the same independent 50 percent chance of knocking out each bridge — rolls through?

There is also some Extra Credit, but I'm skipping that.

So, first we'll deal with Question 1.  I wondered for a while what was special about the N x N+1 pattern, but it became clear rather quickly.

We would like to solve for p, the probability that we will make it across the river.  There is also q = 1-p which is the probability that we do not make it across the river.

To solve this let's first imagine that all of these bridges are low enough that motor boats cannot go underneath them.  Motorboat Billy has been really pissed about this whole island and bridge system for a very long while now because every time he wants to go from the East River to the West River, he has to go through the long painstaking process of dragging his boat ashore and pulling it all the way beyond this pesky bridge system.

Needless to say, he is excited about this storm.  He will finally have some probability that the storm will take away enough bridges that he will get to pass!

Notice that the potential places he can pass are lined up exactly like the bridges.  This would not be the case if it were not N x N+1.

We are looking at the same exact problem!  What does this mean?  The probability that Motorboat Billy will be able to pass from the East River to the West River is q, the probability that we will not be able to pass from the North to the South shore, and the probability that he will not be able to pass is p, the probability that we will get to pass.

Since both problems are equivalent, p=q, and q=p, and the only way that this can happen is if p=q=0.5.

Hence, the probability is 50%.  You can add as many islands and bridges as you want. As long as it remains in the N x N+1 pattern, the probability will remain 50%.

How do you like them apples?

A Neurotic Free Throw Shooter

This riddle hit the internet as I was leaving on my 6th Annual Michigan Beer Tour.  Being the minimalist that I am, I wasn't about to bring my laptop and type up anything on the road. However, that didn't stop me from thinking about it.

Here is the riddle for this week quoted for convenience:

A basketball player is in the gym practicing free throws. He makes his first shot, then misses his second. This player tends to get inside his own head a little bit, so this isn’t good news. Specifically, the probability he hits any subsequent shot is equal to the overall percentage of shots that he’s made thus far. (His neuroses are very exacting.) His coach, who knows his psychological tendency and saw the first two shots, leaves the gym and doesn’t see the next 96 shots. The coach returns, and sees the player make shot No. 99. What is the probability, from the coach’s point of view, that he makes shot No. 100?

I was proud to say I was able to come up with the correct answer right away. Because of this, however, I naturally thought I was missing something and would have to rigorously analyze it.

My initial thinking was as follows.  The coach has seen three shots, two of which he has made, so from the coach's perspective, the player has a conditional probability of 2/3 of making his next shot. This is correct.

But doesn't knowing that it is the 100th shot coming up give you extra information?  It turns out that it doesn't.

Let X3 be a random variable that will be 0 if shot 3 is missed and 1 if shot 3 is made.  Define X4-X100 analogously.  

Let p3 be the probability of making the 3rd shot, and q3 = 1-p3 the probability of missing the 3rd shot.  Define p4-p100 analogously.  We know from the problem statement that p3=q3=1/2.

If we are given that X3=1 (that he makes the 3rd shot), then the expected value of p4 is 2/3.  In fact, it is a sure thing.

Suppose the coach didn't see the 3rd shot, but saw that the player made the 4th shot (X4=1).  Given that, what is the expected value of p5?

What could have happened?  There is a 1/2 probability that he made the third shot, leading to a 2/3 probability that he made the fourth shot. Multiplying these together gives us that the probability that he made the 3rd AND 4th shots is 1/3.

There is also a 1/2 probability that he missed the 3rd shot leading to a 1/3 probability that he made the 4th shot.  Multiplying these together gives us that the probability that he missed the 3rd and made the 4th is 1/6.

So, the conditional probabilities of each of these events if (1/3)/(1/3+1/6)=2/3 and (1/6)/(1/3+1/6)=1/3 respectively.

All the coach knows right now is that one of those two events happened since he only knows that the 4th shot is made.  If the first of these had occurred, then there is a probability of 3/4 that he will make shot 5 (since 3 of 4 shots have been made thus far).  If the second of these had occurred, then there is a probability of 1/2 that he will make the shot 5 (since 2 of 4 shots have been made thus far).

So, the conditional expectation of the probability he will make his 5th shot given he made his 4th is found by taking a weighted average of these probabilities: (2/3)(3/4)+(1/3)(1/2) = 2/3.

Missing what happened on the third shot and witnessing the 4th shot made had no effect of the probability of making the 5th shot from the coach's perspective. This is the bizarre nature of conditional probabilities.

Let's explore one more just for kicks.  Suppose the coach missed shots 3 and 4 and came back in to witness that he made shot 5.   There are four possible scenarios: (X3=1,X4=1,X5=1), (X3=1,X4=0,X5=1), (X3=0,X4=1,X5=1), or (X3=0,X4=0,X5=1).  These four scenarios have probabilities (1/2)(2/3)(3/4)=1/4, (1/2)(1/3)(1/2)=1/12, (1/2)(1/3)(1/2)=1/12, and (1/2)(2/3)(1/4)=1/12  respectively.  Their sum is 1/2.

Since we are under the condition that one of them has occurred we can find the conditional probabilities by dividing them all by 1/2.  This gives 1/2, 1/6, 1/6, and 1/6 respectively.

In the four scenarios, the probability that he will make the 6th shot is 4/5, 3/5, 3/5, and 2/5 respectively.  Taking the weighted average gives the conditional expectation of the probability he will make the 6th shot given that he made the 5th: (1/2)(4/5)+(1/6)(3/5)+(1/6)(3/5)+(1/6)(2/5)=2/3.

Missing what happened on the third and fourth shot and witnessing the 5th shot made had no effect on the probability of making the 6th shot from the coach's perspective.

Still not convinced?  Then you're stubborn.

The Sadistic Car Salesman, Part 2

I can shave off 1.67 since I was wrong the first time.  Let's be a little more rigorous in defining the optimal strategy.  The optimal strategy is the one that will end with the least amount over the fair price on average.

There are 5!=120 different possible arrangements of the cards, each of which is assumed equally likely.

Note that if we are in the situation of having been shown the smallest and largest card before the last card is shown, we have complete information and can make an informed decision on when to stop.

Let's start with analyzing the case that we have been shown 4 cards that have consecutive values, and hence, still do not have complete information.  What should we do in this case?

4.1. If we are currently on the smallest card, then we are looking at either N or N+100.  This means we would pay 50 over on average if we stop.  If we continue, then the next card will be either N+400 or N respectively, meaning we would pay an average of 200 over if we continue. Stopping is in our best interest.

4.2 If we are currently on the second smallest card, then we are looking at either N+100 or N+200.  This means we would pay 150 over on average if we stop.  Since 200 over is the average if we continue, we should stop in this situation.

4.3. If we are currently looking at the second largest card, then we are looking at either N+200 or N+300, paying an average 250 over if we stop. Continuing in this case is in our best interests.

4.4. Looking at either N+300 or N+400 means we pay an average of 350 over. Again, continuing is in our best interests.

Let's now explore some 3 card scenarios.  Let's start with the situation in having seen 3 cards that have consecutive values. That is, you are either looking at N, N+100, N+200, or N+100, N+200, N+300, or N+200, N+300, N+400.  If we decide to continue in this situation, let's see what would happen.

3.1 Given the N, N+100, N+200 situation, we would either see the sequence N+300, N+400 or N+400, N+300 next.  In either case, we continue to the end given 4.4 above or complete information respectively.

3.2 Given the N+100, N+200, N+300 situation, we would either see the sequence N, N+400 or N+400, N next.  In either case we stop at N given 4.1 and 4.4 above.

3.3 Given the N+200, N+300, N+400 case, we would either see the sequence N, N+100, or N+100, N.  We would stop at the fourth card given complete information or case 4.1. 

Given these 6 permutations, we are paying an average of (400+300+0+0+0+100)/6=133.33 over if we elect to continue.  So, let's look at each case.

3.1.1. We are currently looking at the smallest of the three cards, which means we are either looking at N, N+100, or N+200.  If we stop, we pay an average of 100 over fair price.  Compared to the 133.33, this is the better deal.  It is beneficial to stop.

3.2.1. The current card is middle card: either N+100, N+200, or N+300.  Stopping means we pay an average of 200 over.  When compared to 133.33, we elect to continue in this situation.

3.3.1. If our current card is the largest card of either N+200, N+300, or N+400, we pay an average of 300 over, and so continuing is a no-brainer.

Now let's explore 3.4, the situation in which we are looking at 3 cards in the form N, N+100, N+300, or N+100, N+200, N+400, and 3.5, the situation in which we are looking at 3 cards in the form N, N+200, N+300, or N+100, N+300, N+400.

Suppose we continue in case 3.4.  

3.4.1. Given the N, N+100, N+300 case, we either see N+200, N+400 or N+400, N+200.  We go to the end in either case given 4.3 or complete information.

3.4.2. Given the N+100, N+200, N+400 case, we either see N, N+300 or N+300, N.  In either case, we stop at 0 over given complete information or 4.3.  

This produces an average of (400+200+0+0)/4=150 over if we elect to continue in this situation.  So, let's look at each case.

3.4.3. We are currently looking at the smallest of the three cards, meaning we're looking at either N or N+100.  This is an average of 50 over.  It is beneficial to stop when compared to 150.

3.4.4. We are on the middle card of either N+100 or N+200 paying an average of 150 if we stop.  This is the only case in which we could stay or continue and have the same average.  Since the variance is lower for staying, let's assume we stay in this case.

3.4.5. If the current card is the largest of either N+300 or N+400, then the average of 350 is much more than the average of 150 if we continue. Continuing here is a no-brainer.

What if we continue in case 3.5?

3.5.1. Given the N, N+200, N+300 case, we either see N+100, N+400 or N+400, N+100.  In either case, we stop at N+100 given 4.2 or complete information.

3.5.2. Given the N+100, N+300, N+400 case, we either see the sequence N, N+200, or N+200, N. We'll stop at the fourth card using complete information or 4.2 respectively.

This produces an average of (100+100+0+200)/4=100 over if we elect to continue. Let's quickly examine each case.

3.5.3. If we are looking at the smallest of the three cards we have seen this averages 50 over. We stay.

3.5.4. The middle cards of N+200 or N+300 has us paying 250 over on average. Continue!

3.5.5. We're on the largest of these three?!? Continue!!

Now comes the largest part of analyzing the two card scenarios.  However, with the analysis above, it isn't too daunting.

If the first two cards are N+400 and N, then we stop with the complete information and pay 0 over.  There are 6 permutations of 5 cards where these are the first two cards.  T=0, P=6. 

If the first two are N+300 and N or N+400 and N+100, we should stop.  (I've analyzed this on a previous blog, but the idea is that stopping has you pay an average of 50 over while continuing has you pay an average of 100 over).  This has you paying 0 over for 6 permutations and 100 over for 6 permutations.

Our current total and number of permutations is T=600 and P=18. 

If the first two are N+400, N+200, or N+300, N+100, or N+200, N, we pay an average of 100 over if we stop.  If we continue?

2.1.1. Continuing with N+400, N+200, if we see N next we'll stop. We pay 0 with the two permutations associated with that.  If we see N+100 next we'll stop by 3.4.3 and pay 100 over with the two permutations associated with it.  If we see N+300 next, we continue by 3.2.1.  We'll pay 100 if we see the N+100, N permutation and 0 if we see the N, N+100 permutation.  T=900, P=24

2.1.2. Continuing with N+300, N+100, if we see N next we'll stop by 3.4.3 and pay 0 with those two permutations. Seeing N+200 next will have us continue by 3.2.1 and see either N+400, N or N, N+400, both of which end at paying 0 over by 4.4 or 4.1 respectively. Seeing N+400 next has us continue by 3.5.5 to see either N+200, N or N, N+200, both of which has us stop at the 4th card by 4.2 or complete information. T=1100, P=30

2.1.3. Continuing with N+200, N, if we see N+100 next we'll continue by 3.2.1 and see either N+300, N+400, or N+400, N+300, both of which we will see to the end by using 4.4 or complete information. If N+300 is next, we continue by 3.5.5 and see either N+100, N+400, or N+400, N+100 both of which we stop at N+100 by 4.2 or complete information.  If N+400 is next, we have complete information and will stop a N+100 with those two permutations.  T=2200, P=36

If we were to have stayed given those three cases then we would have paid an average of 100 over for the 18 permutations associated with it bringing our total up to 2400 instead. Continuing is better.

Analyzing the case of seeing N+200, N+400, or N+100, N+300, or N, N+200 is completely analogous, except for the fact that it is easier to see you should continue in this case.  Adding another 1600 to the total and another 18 permutations gives us T=3800, P=54.

Let's now look at the cases when the first two are N+400, N+300, or N+300, N+200, or N+200, N+100, or N+100, N.  We pay an average of 200 over if we stop.  Continuing is best.

2.2.1. If we continue with N+400, N+300, we will stop on N+200, N+100, or N given 3.1.1, 3.5.3, or complete information.  T=4400, P=60.

2.2.2. Continuing with N+300, N+200, we will stop on N+100 or N if they are next by 3.1.1 or 3.5.3. If N+400 is next we continue by 3.3.1 to see either N+100, N or N, N+100 stopping on the fourth card.  T=4700, P=66. 

2.2.3. Continuing with N+200, N+100, we will stop on N by 3.1.1. If we see N+400 or N+300 next, we continue and stop at N in either case.  T=4700, P=72. 

2.2.4. If we see N+100, N we'll explore all 6 cases.  The permutations (N+100, N, N+200, N+300, N+400), (N+100, N, N+200, N+400, N+300), (N+100, N, N+300, N+200, N+400), (N+100, N, N+300, N+400, N+200), and (N+100, N, N+400, N+300, N+200) will all have us going until the last card. The permutation (N+100, N, N+400, N+200, N+300) will have us stop at the 4th card because of complete information.  T=6400, P=78. 

Going from 3800 to 6400 was a 2600 bump with 24 more permutations.  This is important only in that analyzing the cases N+300, N+400 or N+200, N+300, or N+100, N+200, or N, N+100 is the exact same.  T=9000, P=102. 

We're almost there. Now, to look at the two cases N, N+300 and N+100, N+400.  We should definitely continue in these cases.

2.3.1. For N, N+300, if we see N+100 next we stop because of the assumption in 3.4.4. If N+200 is next, we continue by 3.5.4 and conclude on N+100 for either permutation.  If N+400 is next, we will stop at N+100 because of complete information.  T=9600, P=108. 

2.3.2. For N+100, N+400, if we see N next we stop with complete information.  If N+200 is next, we will stop because of my assumption in 3.4.4. If N+300 is next we continue by 3.5.4 and will stop on the very next card of N+200 (by 4.2) or N by complete information.  T=10200, P=114. 

And finally, the last 6 permutations associated with N, N+400.  These all will lead to N+100 no matter what because we have complete information. The final tally: T=10800, P=120. 

This averages to 10800/1200 = 90.

Given the amount of time these riddles are taking me to solve, along with the fact that I get them wrong, I probably will stop writing them up.

The Sadistic Car Salesman

This has some people stumped. I'm a little hesitant to put this out there because it may not be optimal yet, but I'm somewhat confident.  Here is the riddle quoted from FiveThirtyEight: 

You go to buy a specific car, whose fair price we’ll call N. You have absolutely no idea what N is and the dealer, sadistic capitalist that he is, won’t tell you. The dealer enjoys a good chase, though, so without directly revealing the value of N, he takes five index cards and writes down a number on each of them: N, N+100, N+200, N+300 and N+400. Important: the guy’s sadistic but not a math major. The numbers on the cards are numbers, not algebra equations.

He presents the cards to you, one at a time, in random order. (For example, if the price on the second card is $100 more than the first, you can’t be sure if those are the two smallest prices, the two largest, or somewhere in between.) Each time he shows you a card, you must either pay the price on that card, or ask to see the next card. You cannot go back to previous cards. If you make it to the fifth and final card, then that is what you must pay. If you play the dealer’s game optimally, how much should you expect to pay on average above the fair price N?

If we use a naive strategy in taking the first card presented to us, then we will be overpaying $200 on average.  We would like to bring that down a bit.

We know that 4/5 of the time, there will be a smaller card in the remaining 4 cards not yet shown.  So, it seems worth our time exploring a strategy beyond just stopping at the first card.

Let's explore the 20 possible cases of being shown 2 cards in order in a condensed version.  Let N0 be the card with the smallest value, N1 the card with N+100, and so on, up to N4.

Let's look at the difference between the first two cards.

When the order is (N4,N0), we've lucked out and have been shown the largest and smallest card in order with a difference of 400.  We stop here and pay the fair price!

With the order (N4,N1) or (N3,N0), we have a difference of 300.  It doesn't take long to figure out that in this scenario, you should stop. This gives us an average of $50 over if the difference is 300.

With the order (N4,N2), (N3,N1), or (N2,N0), we have a difference of 200. Given a difference of 200, you will have an average of $100 over fair price if you stop.  If we use the strategy of having more cards shown to us until the first time we see something smaller we will end up only paying $94.44 over the fair price on average.  Let me try to explain.

Given the (N4,N2) scenario, we have a 50/50 chance of spending 0 or 100 over using this strategy.  Given the (N3,N1) scenario, we have a 100% chance of spending 0 over.  The (N2,N0) case is a bit tricky, since we are given all information if N4 comes up before N1.  This will happen half the time for a payment of only 100 over.  One-sixth of the time you will pay 300 over, while 1/3 of the time you will pay 400 over.  This averages out to $233.33.

Since these three cases are equally likely (1/3 a piece), we have an average of (50+0+233.33)/3=94.44.

We can have a difference of 100 with the orders (N4,N3), (N3,N2), (N2,N1), or (N1,N0).  Again, employing the strategy of taking the next lowest valued card is to our advantage.  It will have us pay $108.33 over the fair price on average.  This takes a similar analysis to the one above.

When we take the reverse order of those above, we can find an average of $108.33 and $94.44 over the fair price by using the same strategies for -100 and -200 as we do for 100 and 200 respectively.

For a difference of -300 with (N1,N4) or (N0,N3), we should take the card that is either next higher or next lower than our first card as the optimal strategy.  This leaves us with an average of $100 over.

If we happen to get (N0,N4) with a difference of -400, then we can be absolutely sure that we will pay only $100 over.

In summary, we pay fair price (0 over) with probability 1/20, we pay an average of $50 over with probability 2/20, an average of $94.44 over with probability 6/20, an average of $108.33 over with probability 8/20, and an average of $100 over with probabilities 2/20 and 1/20 (or a total of 3/20).

This gives us a total average of $91.67 over the asking price, or 275/3 to be exact.

Calendar Math

One of my favorite questions to ask my statistics students is "What is a leap year?"  Many of them get a general idea, but don't actually know. 

A leap year is any non-century year divisible by 4, and any century year that is divisible by 400.  

What is nice about determining whether a year is divisible by 4 or not, is that you only have to pay attention to the last two numbers.  For example, 2016 will be a leap year since 16 is divisible by 4.  However, 2100 will not be a leap year. Even though it is divisible by 4 it is a century year, and needs to be divisible by 400, which it is not.  

This is the second time I've run across a problem involving calendar math this month. I first encountered one when solving Problem 19 on Project Euler.  It had me determine the number of times during the twentieth century that January 1st was a Sunday.  I won't spoil that one. 

FiveThirtyEight posted their 4th riddle which asks a series of questions about calendars.  They are reprinted below for convenience. 

1. How many different calendars would you need to represent all possible years — accounting for all day and date combinations? (Don’t forget about leap years!)
2. Now that we have all the calendars we could possibly need, it’d be nice to know how often we’re using them. When is the next time we’ll use the 2015 calendar?
3. What is the smallest total number of years that will pass between using the same non-leap-year calendar twice?
4. What is the largest?
5. What is the smallest total number of years that will pass between using a leap year calendar twice?
6. What is the largest?

Every calendar can be completely defined by the day of the week on which the first day (Jan 1) and the last day (Dec 31) falls.  Using Su, M, T, W, R, F, and Sa for the days of the week, we can represent our 2015 calendar as (R,R) since the first and last day of the 2015 calendar were both Thursdays.

The 2016 calendar will be (F,Sa) because the extra day during this leap year will shift the last day forward one.  The 2017 calendar will then be (Su,Su).  There are 7 calendars in which both days are the same, and you can quickly see that there are also 7 calendars in which the the first day is one day of the week, while the last day is the next day of the week.  This gives us a total of 14 possible calendars.  It doesn't take much analysis to notice that we do indeed use every one of those 14 possible calendars.

If we follow the pattern from 2017 for a while, we find that 2023 will be another (Su,Su) calendar, suggesting the potential answer to #3 being 2023-2017=6.

With 2023=(Su,Su), 2024=(M,T), and 2025=(W,W), we find that 2026=(R,R) will be the next time we use our 2015 calendar, a difference of 11 years, which gives our answer to #2 and suggests a potential answer to #4.

When we explore leap years for a while, we see 2016=(F,Sa), 2020=(W,R), 2024=(M,T), 2028=(Sa,Su), 2032=(R,F), 2036=(T,W), 2040=(Su,M), which brings us back to the 2016 calendar in 2044, a difference in 28 years.

If one were not careful, and forgot about skipping a leap year 3 out of every 4 centuries, we may think that the answer to #5 and #6 were the same number 28, being both the smallest and largest number of years that will pass between using a leap year calendar twice.  

So, let's move up closer to 2100.  We'll take the leap year 2032=(R,F) that I analyzed above and add 28 years to it twice to get us to 2088=(R,F).  Let's observe the next several years beyond 2088.

2088	(R,F)		2092	(T,W)		2096	(Su,M)		2100	(F,F)		2104	(T,W)
2089	(Sa,Sa)		2093	(R,R)		2097	(T,T)		2101	(Sa,Sa)		2105	(R,R)
2090	(Su,Su)		2094	(F,F)		2098	(W,W)		2102	(Su,Su)		2106	(F,F)
2091	(M,M)		2095	(Sa,Sa)		2099	(R,R)		2103	(M,M)		2107	(Sa,Sa)
												2108	(Su,M)

The interesting thing that happens here is that we go 8 years between leap years from 2096 to 2104.  What does this do to the calendar?  It allows us to see a (T,W) leap year calendar in 12 years rather than the usual 28, and the (Su,M) calendar of 2096 again in 2108.  

When will the next leap year calendar of (R,F) from 2088 be seen?  Usually, it would be 28 years later, or 24 years from the next (T,W) leap year calendar.  Because of the century year in between, we see that the (T,W) leap year calendar repeats on the other side of the century year, and will need another 24 years until a (R,F) calendar. So, a total of 40 years will pass before we see the leap year calendar of (R,F) again.  

Also worth observing is the 2090 calendar (Su,Su). Why?  Because we don't see it again until 2102 which is 12 years later.  This increases the maximum number between non-leap year calendars I had previously guessed by 1.  So, it would appear that the answers to #4 and #5 are the same.  

So, my answers for this riddle are as follows. 

1. 14
2. 2026
3. 6
4. 12
5. 12
6. 40

As always, it is very possible that I've missed something. Please chime in if I have. 

Those Distracting Smartphones

The most recent Riddle from FiveThirtyEight has me stumped and feeling what it is like to be a frustrated graduate student again.  No matter how much I worked through different probabilities using different approaches, I couldn't find a pattern that would simplify the problem.  And what's worse, there is no professor I can go visit in office hours. I've even tried Tweeting the writers of the problem for a hint, but to no avail.

The Riddle is quoted below for convenience.

You’ve just finished unwrapping your holiday presents. You and your sister got brand-new smartphones, opening them at the same moment. You immediately both start doing important tasks on the Internet, and each task you do takes one to five minutes. (All tasks take exactly one, two, three, four or five minutes, with an equal probability of each). After each task, you have a brief moment of clarity. During these, you remember that you and your sister are supposed to join the rest of the family for dinner and that you promised each other you’d arrive together. You ask if your sister is ready to eat, but if she is still in the middle of a task, she asks for time to finish it. In that case, you now have time to kill, so you start a new task (again, it will take one, two, three, four or five minutes, exactly, with an equal probability of each). If she asks you if it’s time for dinner while you’re still busy, you ask for time to finish up and she starts a new task and so on. From the moment you first open your gifts, how long on average does it take for both of you to be between tasks at the same time so you can finally eat? (You can assume the “moments of clarity” are so brief as to take no measurable time at all.)

 By using a random uniform number generator in R, I created two sequences of random integers from 1 to 5, call them X and Y.  To illustrate, suppose the first set of random sequences were given as X = {4,3,4,1,5,...} and Y={3,5,1,2,5,...}.

I would then ask R to compare the first two values of 4 and 3.  If they happened to match, I would ask for that matching number. If one was smaller than the other (as is the case with this example), I would ask R to take the smaller value and add to it the next number in the sequence.  In this case, we get 3+5=8.

Now, I ask R to compare 4 and 8.  No match?  Then 4+3=7 in the X sequence. Compare 7 and 8.  No match?  Then 7+4 = 11 still in the X sequence.  Compare 8 and 11.  Still no match, so now jump back over to the Y sequence and get 8+1=9.  Compare 9 and 11, and find no match, so 9+2 =11 in the Y sequence.  Finally! Since 11 and 11 match, I have R report that number.

Then, I asked R to do that 1,000 times and give me a mean of all the lengths it produced.  Again.  Again.  Again.

The pattern that results makes me want to guess that 9 is either the correct answer or very close to the correct answer.

Please, please, please, somebody chime in with the trick to solving this problem without simulation.  I'm going insane.

For the coding geeks out there, this is what I did:

Gushing Geysers

It's Friday!! Time for "Riddle" 2, which isn't much of a riddle, but that's OK.  It is titled, "Which Geyser Gushes First?"  The riddle is quoted below.

You arrive at the beautiful Three Geysers National Park. You read a placard explaining that the three eponymous geysers — creatively named A, B and C — erupt at intervals of precisely two hours, four hours and six hours, respectively. However, you just got there, so you have no idea how the three eruptions are staggered. Assuming they each started erupting at some independently random point in history, what are the probabilities that A, B and C, respectively, will be the first to erupt after your arrival?

Here is a quick explanation of how independence works.  If there is a 50% chance of rain today, and a 50% chance of rain tomorrow, and the events of rain today and/or tomorrow are independent, then the chance that it rains both today and tomorrow is (0.5)(0.5)=0.25, or a 25% chance.  In other words, independence allows us to multiply probabilities together.

So, to our problem.  We know for a fact that we will definitely see one of the three geysers erupt within 2 hours of our arrival.  So, let's focus on that 2 hour interval.

Case 1: All three geysers erupt within this 2 hour interval.  There is a 100% chance that geyser A will erupt in this interval, a 50% chance geyser B will, and a 33.3% chance that geyser C will (or 1/3 probability).  Thus, the probability that all three will erupt within 2 hours of arrival is 1(1/2)(1/3)=1/6.
Now, if all three are within that interval, they can erupt in the following six orders: ABC, ACB, BAC, BCA, CAB, CBA.  Each of these are equally probable (given the condition), so the probability that A is the first geyser you see is 1/3, and likewise for B and C.  So, the probability that all three geysers erupt in the first two hours AND any one of them go first is (1/6)(1/3)=1/18.

Case 2: Geysers A and B erupt in the first two hours, and C erupts after 2 hours.  There is a 100% chance A will erupt within the first two hours, a 50% chance B will, and a 66.7% chance (or 2/3 probability) that C will not.  Thus, the probability of of this case is 1(1/2)(2/3)=1/3.

Now, if geysers A and B erupt in the first two hours, they can erupt in order AB or BA with the equal conditional probability of 1/2.  So, the probability of Case 2 occurring AND A or B going first is (1/3)(1/2)=1/6.

Case 3: Geysers A and C erupt in the first two hours, and B erupts after 2 hours. There is a 100% chance A will erupt within the first two hours, a 33.3% chance (or 1/3 probability) that geyser C will, and a 50% chance that geyser B will erupt after 2 hours.  Thus, the probability of this case is 1(1/3)(1/2)=1/6.

Analogous to Case 2, we have a 1/2 conditional probability that either A or C goes first. So, the probability of Case 3 occurring AND A or C going first is (1/6)(1/2)=1/12.

Case 4: Geyser A is the only geyser to erupt in the first two hours.  There is a 100% chance that A will erupt within the first two hours, a 50% chance that B will erupt after 2 hours, and a 66.7% (or 2/3 probability) that geyser C will erupt after 2 hours.  Thus, the probability of this is 1(1/2)(2/3)=1/3.

Now, summing the cases that A goes first, we get (1/18)+(1/6)+(1/12)+(1/3)=23/36.  Summing the cases that B goes first, we get (1/18)+(1/6)=8/36.  Summing the cases that C goes first, we get (1/18)+(1/12)=5/36.

And you thought you understood probability.

Smartphone Droppings

On December 11, 2015, FiveThirtyEight began The Riddler!  This is going to be fun.

This week's riddle is quoted below:

You work for a tech firm developing the newest smartphone that supposedly can survive falls from great heights. Your firm wants to advertise the maximum height from which the phone can be dropped without breaking.

You are given two of the smartphones and access to a 100-story tower from which you can drop either phone from whatever story you want. If it doesn’t break when it falls, you can retrieve it and use it for future drops. But if it breaks, you don’t get a replacement phone.

Using the two phones, what is the minimum number of drops you need to ensure that you can determine exactly the highest story from which a dropped phone does not break? (Assume you know that it breaks when dropped from the very top.) What if, instead, the tower were 1,000 stories high?

Think on it a little bit if you want to solve it yourself, but the rest of this post is devoted to explaining the evolution of a solution.

The wording of the problem is a little confusing, but I think I get the jist.  There are two adjacent floors of this tower the lower of which, when the smartphone is dropped it will not break, the higher of which, the smartphone will break.  Our job is to find these floors so that we can report the highest story from which a dropped phone does not break.

Obviously, we could get lucky and guess the correct floor right away, drop a phone that doesn't break, walk up a flight and drop a phone that does.  The minimum number of drops would then be 2. But that isn't what the riddle is really asking.

What it is really asking is that if we were the most unlucky as unlucky can be, and we had an optimal way of dropping smartphones out of building, what is the maximum number of drops that will take place before we get the answer?  That answer I believe is 18.  Here's my train of thought.

A 100 story building has a nice number of stories, since it is a perfect square (10 * 10 = 100).

Drop the first smartphone from the 10th story.  If it breaks, you have a potential nine droppings to go from stories 1-9 (technically, we could skip story 1 since the assumption is that there exists a floor from which the phone doesn't break) with your only remaining smartphone for 10 total droppings before finding your answer.

If it doesn't break, make your 2nd drop from the 20th story.  If it breaks, you have a potential nine more droppings to go with your only remaining smartphone for 11 total droppings before finding the answer.

This process continues.  If you are unlucky, and the answer is the 88th or 89th floor, then you will need 18 droppings.  This is because your 9th drop will be from the 90th story, on which the first smartphone breaks.  Your 10th through 17th drop will be from stories 81-88, none of which will result in a break.  On your 18th drop, if the second phone breaks, the answer is the 88th story.  If it doesn't break, the answer is the 89th story.

You may wonder what if the story is the 98th or 99th floor.  It turns out, because of the assumption that a smartphone will break on the 100th floor, it will take more droppings if it is the 97th or 98th floor.

Remember that your first phone hasn't broken yet after the 9th dropping from the 90th floor.  So, we can enter another optimal subroutine of dropping from the 93rd, 96th, and 99th until a break, and then going though two more droppings with the last remaining smartphone until we find our answer.  Thus, if it is the 97th or 98th floor, the first phone breaks on the 99th floor, which would be your 12th dropping, then you will need 2 more droppings for only 14.

There may be a more optimal solution, so please chime in if I'm wrong.

Using the same idea for 1000 stories, I get a potential 62 total droppings (if we are unlucky and it happens to be on floor 990 or 991).
____________________________________________________________________________

And.... I was wrong.  Instead of rewriting the entry above, let's learn from my mistake and correct it.  Using the idea of doing a subroutine if you get to 90 without having it break, if we instead enter a subroutine each time, we can end with fewer droppings.

To illustrate, here are the first 15 potential droppings: Story 10, 20, 29, 38, 46, 54, 61, 68, 74, 80, 85, 89, 93, 96, 98.  Using this routine, you will only need 16 droppings if the solution is one of floors 92, or 94-99.

I built a program in R to accomplish the task for any number of floors.

_________________________________________________________________________________

This third portion has been added after the first comment below which reveals the correct answer. However, I was lucky enough to think of this solution before reading his comment.  As I was drinking coffee on the morning after giving the solution above, I began thinking that now that I know that 16 drops is all that it takes, why not start at the 16th floor, or better yet, the 15th or 14th to try and get a smaller solution.  

By beginning on the 14th floor, you will have at most 14 drops if the phone breaks on the 14th.  With a second drop 13 floors higher on floor 27, you will again have at most 14 drops if the phone breaks on the 27th.  Continue this process and you will find that you need only 14 drops for even a 105 story building.  

Since summing 1 through 44 gives 990 and summing 1 through 45 gives 1035, it appears that you need 45 drops for a 1000 story building.  

Now, for the generalization.  What if you were given x smartphones, where x ranges from 1 to the number of floors?