MathJax

Saturday, November 11, 2017

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?  

Wednesday, November 8, 2017

The Price is Wrong. Or, Ego is Never On Your Side

The Price is Wrong


Last week, I published an analysis of spinning the wheel on The Price is Right.  Even if my original assumption was correct, there are still mistakes in my analysis.  However, the logic in my original assumption was not sound.  Here was my assumption last week:
If the probability that you will not bust on the next spin exceeds the probability that you will win by staying where you are at, then you should spin again. 
 This was incorrect. Instead, the assumption and logic should have been as follows:
If the probability that you will not bust on another spin AND you end up winning exceeds the probability that you will win by staying where you are at, then you should spin again.  
Under this assumption, the calculations are more difficult, but doable.

Ego is the Enemy


I'm currently reading Ego is the Enemy by Ryan Holiday. This fits perfectly with what I was trying to accomplish with the last few posts.

When I posted about how to escape from prison, I had thought about that problem all week, bouncing ideas with a colleague who checked my work and kept me in line.  When I finally stumbled upon the solution, he confirmed it worked before I wrote it out.  In other words, I was able to keep my ego in check.

Now, guess what happened with the post about the Price is Right?  I didn't confirm with my colleague, and get a second opinion.  I was confident in my answer and let my ego take control.  My ego is not on my side, and it would be very good for me to remember that. 

Posting an incorrect solution for the world to see was a great reminder.

Thursday, November 2, 2017

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.  



Thursday, October 26, 2017

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.  

Tuesday, October 17, 2017

A Day Without an X

Not Breaking the Chain


Previously, in my blog post Homebrew Daily, I referred to the habit building technique that requires you to keep track of each day that you devote to building the habit.  This can be done by marking an X on the calendar, thereby building a chain of days which you psychologically do not want to break.  It is a great method.

Not stated in that blog post, but something I started on that same day, was learning Norwegian on Duolingo.  According to Duolingo, I'm on a 66 day streak today.  

However, I started this 67 days ago. I missed a day.  

I also missed a day of my Homebrew Daily ritual.  

The Day Without the X


On my last blog post, I wrote about choosing your suffering.  I wrote about how I chose to suffer through a 100 mile bike ride one Saturday.  What I didn't write about, was that on that same day, I couldn't mark an X on the calendar. I missed studying Norwegian. I missed learning anything about homebrewing. 

Somewhere between 20 and 30 miles into the bike ride, my phone died. Even using it in airplane mode, my phone went to the dark side.  Little did I know, it would be for good.  

Upon finishing the bike ride over an hour later than I thought I would (I took a wrong turn at one point that took me 5 miles out of my way), I was not going to make the 6 pm dinner that Erin and I had planned with friends Ed and Mary in Lawrence.  

I was able to shower at the facility where we started the ride, and get on my way.  However, my phone would not charge. Not only could I not contact Erin to let her know I was OK, but I couldn't ask for directions to Ed and Mary's place. Although I had been there twice, and could have probably got myself in the general vicinity, I didn't know exactly where it was. 

Using someone's phone at the first gas station I pulled into in Lawrence, I let them know everything was fine and got directions. 

There was much fun and wine drinking at the dinner party.  Eventually, it was determined that we should stay the night instead of driving back to Topeka.  

Up until that point, I had a plan of working from my iPad or desktop computer as soon as I had arrived back home to complete my daily habit ritual. I began thinking of alternatives. Maybe I could ask to borrow their computer for a little while?  

Or maybe I shouldn't worry about it.  Maybe I've built a great habit, and am going to stick with it, and don't need another X in a calendar day to do that. Maybe I should enjoy the moment that has been dealt to me.  

Perhaps we should allow ourselves a "Weekend Amulet" that can be used to put a temporary freeze on your streak of days.  You remember those days when you did a little extra work building your habit?  Maybe you were earning yourself "lingots" that can be used to purchase "Streak Freeze Amulets" for when they are needed.  

It is important to completely own a great new habit that you have built.  But it is probably just as important for that habit not to own you.  

Tuesday, September 26, 2017

Choose Your Suffering

A pretty view during a recent bike ride around Shawnee Lake

A Subtle Art


In Mark Manson's book, The Subtle Art of Not Giving a Fuck, he presents a counter intuitive approach of looking at life.  For some it may work.  It worked for me last weekend. Here is how it works.

We all suffer on some level. In fact, life can be alternatively viewed as just a long time of unavoidable suffering.  With each decision you make, you choose some level of suffering. 

Earlier last week, I was informed of the Buffalo Bill Century Ride in Leavenworth, KS.  The ride had 25, 60, and 100 mile road options, along with a 50 mile gravel ride. The 60 and 100 mile rides grabbed my interest.  

When the weekend came, I was under no obligation to choose to get up at 5:45am to get ready and travel to Leavenworth to begin riding 60 or 100 miles at 8:00am.  I could have chosen a lesser form of suffering.  Sitting on the couch, reading, studying, or maybe watching some TV could have been my choices.  I only would have suffered my own feeling of guilt for not having taken advantage of such an adventure. 

I chose a higher level of suffering, because that was easier in my mind. I would suffer the open roads of eastern Kansas.  

Along the route, there was a fork in the road. To choose right would mean only 60 miles, and to be done with the ride in a more reasonable time frame. To choose left would mean a commitment to 100 miles, and more suffering.  I chose left.  

The pains that one goes through in a 100 mile ride are really not all that bad when compared to other forms of discomfort. I'll take the swollen underside over a guilty conscience. I will take the sore quads and aching back over the simple discomfort of more decisions that would need to be made in a normal day (like, what beer I should have next? Or, should I leisure read longer or take a break and do some push-ups? Perhaps I should go to the library and rent some movies.) 

For me, framing it in terms of suffering helped me get out there and on my bicycle.  I like to have a full calendar, and to schedule each moment of my day.  This requires a lot of decisions, and as such, a small amount of suffering. I didn't want that suffering.  I wanted the decision free kind of suffering of an increasingly stiffening neck and shoulders as the day wore on.

The next time you need to make a decision on doing something difficult, you might give this method of framing your decision in terms of suffering a try. 

Tuesday, September 19, 2017

Pushing a 2 Ton Baby Giant on a Swing

You can't push all at once. Use the momentum of the swing, silly!

Imagine a 2 ton baby giant on a swing, and it is crying at you to push her.  You feel obliged since it could possibly crush you with a swat of her arm.

Although difficult, when your hard pushes are timed just right, the giant will begin to swing higher and higher. However, it takes quite a mighty push, and it takes a mighty push at a specific time during the swing. Specifically, on the apex of its back swing. 

Learning Something New and Very Difficult


When you are first learning something that is really hard to grasp, it will take a lot of your time. In fact, it better take some of your time every day. Otherwise, you will lose what you've gained. 

Say you want to pass a class with an A. That is equivalent to getting the baby giant up to some high level on her swing. Trying to cram everything in the night before the test is like pushing the baby giant to that level with one push.  It isn't going to happen.  

If we think as each swing forward and back as a day, then we can reach that A level with a timely push every day. Skipping a push, and the giant will quickly lose its momentum and it will take an extra day to get back on track.  

A quick review of notes is the equivalent of giving a simple maintenance push, that will keep the giant at her same level. Anything extra, and you can gain a little more toward your goal. 

This idea came to me while listening to a similar analogy in Mind Hacking by Sir John Hargrave on my way back and forth to work. I hope it provides an avenue for you to hack your own mind, and perhaps conquer that difficult challenge that looms in front of you.