How Can We Weigh Anything?

Sometimes in math we can intuitively understand the answer to something, know that it’s correct, and yet can’t lay out the proper reasoning in mathematical terminology. It’s a frustrating feeling to know that you have what normally comes at the end of the process, and yet have nothing to show for it. I think this problem captures the essence of this feeling quite well:

A few years ago, a king’s math professor purchased a small farm, a place where he could unwind on the weekends and grow some fruit and vegetables. The farm came with all kinds of tools and various implements, including a large balance scale. Next to the scale was an old (pre-metric) 40 lbs stone with some initials carved into it: apparently, a previous owner had used it to weight 40 lbs of feed.

One morning, while cleaning out his barn, the professor dropped the stone and it broke into four pieces.

The professor was a bit sad about his carelessness, as he had liked that curious old stone. But he soon discovered something interesting: He could use the four pieces of the broken stone to weigh items on the balance scale – as long as these items were in one pound increments, between 1 and 40 pounds.

How much did each of the four pieces weigh?

I’m going to outline my take on the problem in this post, so (as always) don’t scroll beyond the picture if you want to do it yourself.

rocks.jpeg

If you think about this long enough, you may soon come to the idea that the weights could be broken into 1, 3, 9, and 27. This sort of comes about intuitively through our understanding of the numeric system, which takes different powers of a certain base to express any intermediate number. Here, it’s a little different because we can subtract any of the weights, but it all comes around to the same logic. Now, how do we prove this? More importantly, how do we show how we can arrive at the answer without using it to prove its own validity?

Firstly, we know we can measure 40 different weights (1 – 40), but they can also be negative (on the other side of the balance), and we can have 0 as well. So we have 40 + 40 + 1 = 81 different weights we can measure. Now how can we make those combinations: of our 4 weights, each can be used on either side or not be used at all, so each can be used in 3 different ways. This comes around to 34 = 81 different combinations, the same exact number we just calculated. So what does this tell us? If we need to measure out 81 different combinations, and can create 81, that means that an distinct combination of the weights will result in a distinct integer weight (in mathematics this is called being a sharp condition).

Let’s assume our weights: a ≤ b ≤ c ≤ d. Now we know that each distinct combination will result in a distinct integer output, so we know that all of them combined will equal 40:

a + b + c + d = 40

The next smallest combination would be b + c + d, which would have to equal 39:

b + c + d = 39

Following this logic, we can go down next biggest combinations, which have to be:

b + c + d – a = 38

a + c + d = 37

As we form new equations, we can solve them simultaneously to arrive at our answer Only 4 simultaneous equations are needed for 4 variables, however we do need to use one more beyond these (these four will not give discrete values for c and d due to the common term c + d throughout).  The smallest equation which doesn’t contain +c and +d is:

a + b + d = 31

Solving all these equations simultaneously, we find our original answer of:

a=1, b=3, c=9, d=27

The way in math makes you prove something you already know is one of its interesting facets in my opinion, and I don’t think I could’ve found a better problem to display that. This aspect of math does however does make it the subject of many jokes:

A mathematician, a physicist, and an engineer are riding a train through Scotland. The engineer looks out the window, sees a black sheep, and exclaims, “Hey! They’ve got black sheep in Scotland!” The physicist looks out the window and corrects the engineer, “Strictly speaking, all we know is that there’s at least one black sheep in Scotland.” The mathematician looks out the window and corrects the physicist, ” Strictly speaking, all we know is that is that at least one side of one sheep is black in Scotland.”

How Many Tanks Did Hitler Have?

This blog’s very first post dealt with how simple mathematics was used to fight Nazis in World War II, and that has since become one of favorite applications of math.  While reading about the war, I recently came across the German Tank Problem, and I found it even more fascinating than that case with Abraham Wald (especially because it involves more Bayesian Theory).  One of the critical aspects of WWII was intelligence, which provided the basis for a country’s actions, and the Allies invested plenty of resources into trying to estimate the extent of German forces, and especially tanks. Captured or destroyed tanks always had a serial number, and therefore the number of tanks could be estimated through this data. Statisticians had been doing this for ages, but what made this case different was the employment of Bayesian inference rather than Frequentist inference to obtain much more accurate results. I saw a great explanation of Frequentist vs. Bayesian thinking on stackexchange:

Frequentist Reasoning — I can hear the phone beeping. I also have a mental model which helps me identify the area from which the sound is coming. Therefore, upon hearing the beep, I infer the area of my home I must search to locate the phone.

Bayesian Reasoning — I can hear the phone beeping. Now, apart from a mental model which helps me identify the area from which the sound is coming from, I also know the locations where I have misplaced the phone in the past. So, I combine my inferences using the beeps and my prior information about the locations I have misplaced the phone in the past to identify an area I must search to locate the phone.

The Bayesian reasoning allowed for a more substantiated estimate of the scale of the tank forces. In this way, the values of the serial numbers was used to ascertain the probability that the total number of tanks was a certain n, and then all these probabilities were compiled. The mathematics of this turns out to be very interesting, and I’m just going to outline it briefly.

Let us take the example of the 4 serial numbers of 19, 40, 42, and 60. We know that the highest number is 60, and therefore can find the probability that this is the highest number for different numbers of tanks. Given that there are 100 tanks, the probability that the highest number is 60 in 4 samples is the total number of possibilities with 60 as the highest divided by total possibilities, which is 59C3/100C4. This is because one sample has to be the maximum, and all the others have to be lower than that so our possibilities are limited to 59C3. This generalizes to:

1.png

The variable n is the number of tanks, m is the maximum serial number, and k is the number of samples. Now, the expected number of tanks is simply the expected value of the number of tanks when the probability is multiplied by n and added for all possible values of n, which is anything above m, the maximum. This can be summarized by the following:

2.png

This can be algebraically proven to equal:

3.png

This generalization of the series can be arrived at using some algebra and the following identity:

4.png

Now that we have the value for the mean, it is easy to find the standard deviation using the fact that the std. deviation is sq. root of the variance, where variance is:

 

5.png

Now this becomes an algebraic exercise, as we solve for σ where variance is σ2.

 

6.png7.png

 Plugging in the values of m, n, and k for the set of data of 19, 40, 42, and 60, we come to:

8.png

This estimate has a considerable uncertainty, however is objectively better than that of wartime intelligence agencies, which often came to wild numbers such as 1400. Yet again, we can see that just brute force didn’t win the war, but a steady supply of some of the Allies’ brightest minds to apply their mathematics ingeniously.

Who Should I Vote For?

Voting has got a lot to do with math, whether we like it or not.  Every vote matters they say, and it really does, because if everyone thought going to vote was not important, the result would be truly skewed and not reflective of what society wants. Well especially with the US presidential election just behind our backs, elections are everywhere on the news. We think that the voting system is fair, and that it mathematically gives the presidency, or whatever else to the best candidate in the public’s viewpoint. Yet the system used for voting is far from perfect, and in reality creating a voting system that produces a winner according to basic intuitive rules is impossible.

voting-paper-ballots.jpg

One example of the complexity of voting involves that of the presidential race with Bush, Al Gore, and Nader where Bush won by a mere 517 votes. Let us assume that the supporters of Nader, who was highly liberal, would have for the most part voted for Gore, a less liberal Democrat, had Nader not been running. Well that means that had Nader not been running, Al Gore would have won, because the extra votes from Ralph Nader supporters would have brought him more votes than Bush. That brings to table a major dilemma: The majority of people in the US would have preferred Gore to Bush, and yet Bush still won. The concept of this idea was first thought of by a man named Condorcet, who conjectured that if for any candidate A, if a majority of people prefer a candidate B to A, then A cannot be the winner. And this makes perfect sense.

The mathematics of voting systems is a quirky area which has had results that are discomforting to the everyday citizen who believes that the president should be chosen by real social choice, not a flaw in the system.

Given a set of society’s preferences, there are many ways to ascertain a winner. One is by plurality, which is the normal method of voting used in the US where the person with the most first place votes wins. Another is by plurality with elimination, which eliminates a person who has the least first place votes and then compares again and so on. Another is to see which candidate is preferred by the majority to any other candidate (which is not always possible). Here is a case, and the winners in each case.

499 people: A > B > C

3 people:     B > C > A

498 people: C > B > A

Winner under plurality: B

Winner under plurality with elimination: C

Condorcet Winner: A

See the problems? The unintuitive and complex nature of voting systems makes it all the more fascinating. Who ever knew you had to think so much before voting?

That Can’t Be Right?

While I was writing the previous post, the solution really got me thinking about what math really is when it comes down to our basic instincts, inspiring this post.

Some people think that math is something created by humans, and that there is no universal defined math but it is simply a man-made creation. And the other side takes the opinion that we are simply discovering new parts of something defined, as if created by god or part of the way the universe exists, somewhat like how the force of gravity appears to be ingrained in how the universe is held together and how life is possible.

I personally can’t take a side on this because I come somewhere in the middle, but to me it’s important to understand that math is created (or discovered) by human intuition. Everything seems to come down to the way we see the world, shaped by nearly everything in our past which can change that instinct. I thought it would be worthwhile to just skim through a few interesting facts (other than the infamous Monty Hall Problem!) which can show us that our intuition when it comes to applying math can often be completely skewed.

If we wrap a wire around the earth’s circumference and then add 2 meters to its length, how far off the ground can we expect it to be? My intuition tells me a negligible amount, but a simple calculation gives almost a third of a meter!

400px-Rope_around_earth_3 (1).jpg

Also, we have a jellyfish that weighs 100 pounds with 99% water by weight, and we leave it out to evaporate until it’s 98% water by weight (let’s say that it’s already dead to keep our conscience clean). What’s the new weight? It’s interestingly false to follow basic intuition here, and upon thinking we find that the non-water part is 1 pound, and therefore the answer is 50 pounds.

Moon_jellyfish_at_Gota_Sagher.JPG

Mathematics is about intuition, and that’s what makes it interesting, but sometimes I guess our intuitions can lead us into false visualizations.  Listening to intuition is something I think we should be slightly more wary of, at least in applying math to the world.

Shrink and Conquer

I recently came across this problem, and I knew it was one of the neatest problems I’d ever seen and had to write a post about it. The visual thinking necessary to come across its solution is pretty great. A seemingly intricate geometric situation, there is almost no formal mathematics required but simply a series of logical observations.

Given that there are 100 coins on a rectangular table such that there are no overlaps, and no additional coin can be placed on the table without causing an overlap, prove that using 400 coins and allowing for overlaps we can cover the whole table.

Some assumptions include:

– Each coin’s center is on the table

– The coins are normal and circular

– To cover the whole table every point needs to be at least one coin above every point on the table

As always, I have outlined my take on the problem after the picture, so don’t scroll!

2012-12-12-Coins.jpg

To first tackle the problem, I think it’s best just to visualize the situation. We have the 100 coins, with gaps in between them but no gaps which have the area of the coin (which we can take as a circle of radius 1 cm for simplicity’s sake.

Now, to start to prove why 400 coins would cover the table, we can directly see a relation between 100 and 400 – a factor of 4, which would be achieved in terms of area of the coins by doubling the radius. So let us theoretically expand each of the coins, in its same position, to a coin of radius 2 cm.

Now, what if there is a gap on the table, which is not covered by any coin? This would mean that originally all centers of the coins near that point were more than 1 cm away (in all directions). This means that there would have been a gap large enough to fit in a coin without causing overlaps, which is a contradiction.

Therefore it is not possible for a gap to exist, and all points on the table are covered. But the question wasn’t to show that 100 coins of 4 times the area completely cover the table, but that 400 coins of 1 cm radius cover it completely. But if we shrink the table’s dimensions and all the coins by a factor of 2, which see a table of size 1/4th the original size which is covered by 100 coins of radius 1 cm. 4 of these tables placed side by side achieve that same exact size of the original table, and we know that it is covered completely by 400 of the original coins because we proved each of the individual tables has to be covered completely.

I had to share this problem, because I love the way we have to take the concept of proving by contradiction and apply the idea that we have a larger version of the situation we desire. Basically, this is one of my favorite problems.

 

 

The Subterranean Fox

Some animals are especially evasive, and the cunning fox is definitely near the top of that list. In the dark woods there is a row of 5 holes, one of which contains a fox which moves either to its left or right everyday. Given that you can check one hole everyday, can you design a strategy such that you will definitely catch the fox? Of course you should try to make this strategy find the fox in the least amount of time possible, and it should catch this sneaky animal regardless of whatever it does.  Below this photo of Fantastic Mr. Fox, I have put my take on this problem.

572990_35da51317bf4f10253067f86f80824bf_large.jpg

Back to the basics, let’s try and work this out for less than 5 holes. What would you do if there was 1 hole? Just investigate that one hole, the fox has to be there. So what about 2? First you have to check one of the holes (you have to start somewhere), and if it is not in that hole, you know it is in the other one, so the next day it has no option but to move back to the hole you checked first. So the strategy would be to check one of the holes twice in a row. If we say that the holes are 1 and 2, the strategy could be 1, 1.

Let’s move onto 3 holes now. I think a sensible first move would be to check the middle hole, after which if we don’t meet our fox we know that it is in one of the two adjacent holes, and has to move back to the middle. Therefore a strategy for this could be 2, 2.

Now with 4 holes, we can start with hole 2 and then go to hole 3. To understand why this is a good start, let’s classify the fox’s starting position as either even or odd. If it is even, it’s either starting in hole 2 or 4. If it starts in 2, we have caught it, and if it starts in 4, it has to move to 3, and therefore the second day we catch it. So these two moves guarantee the capture given that the fox starts on an even hole. If it started on an odd hole, it will currently now be on an odd hole, as two days have passed and each day the fox switches from odd to even (or vice versa). So let’s check 3, as the fox has to be on either 3 or 1. And similar to before, but flipped on the symmetry of the holes, if the fox is at 1, it has to move back to 2, so we then check that hole. To sum up the strategy, we first take care of the case of the even starting position, and then odd, giving us the strategy 2, 3, 3, 2.

And we now arrive at our intended 5 holes. To keep our trend going, we’ll start with hole 2. If the fox was initially at an even position, after checking hole 2 it is either caught, or is at 3 or 5 (having moved from 4). So next turn we’ll check hole 3 to make sure that it doesn’t lurk off to the other side. Now, given that it started in an even position, we have either caught it or it had gone from 4 to 5, and now it has no option but to go to 4, and so we simply check this hole. The sequence 2, 3, 4 can therefore find the fox if it started in an even hole. But what about odd? Now after this sequence of 3 days, if the fox started in an odd position, it has to be in an even position. But we already found the strategy for catching the fox if it starts on an even hole. So let’s just repeat that. What do we get? This is our strategy which guarantee catching the fox: 2, 3, 4, 2, 3, 4.

Another way to approach this problem would be to write a program which finds all possible permutations so the fox’s routes and matches these to a solution.   In this answer, I have purposely only found one solution, and suggest you try and find all the possibilities, and perhaps try and extrapolate some trends by comparing the solutions for different numbers of holes. How do the solutions compare when there is even vs. odd total number of holes? Can you generalize this problem?

Races of Deception

Telling the truth is generally a healthy lifestyle. In our lives, we can often get infuriated by liars, and this anecdotal puzzle is a great example of the chaos one little lie can cause.

Luigi was cruising to the finish line on Rainbow Drive, and suddenly hit by a barrage of red shells, causing him to drop down to 7th place, behind Bowser, Peach, Waluigi, Mario, Donkey Kong, and Yoshi. Infuriated, he wants to know who did this, and asks everyone who did it. Using the statements that each of the others make, we are supposed to find out who the culprit really is, but the culprit is lying. Here are the statements:

Peach: It wasn’t Mario.

Bowser: It wasn’t me.

Mario: It was either Donkey Kong or Bowser.

Yoshi: It wasn’t Peach.

Waluigi: It was either Yoshi or Donkey Kong.

Donkey Kong: It was either Yoshi or Bowser.

Try working out the solution yourself, and continue scrolling once you’ve finished.

Mario-Kart-8-5.png

It’s a given that there are countless ways to approach this problem. But what is the most simplistic way? I think that because some of the characters claim that it was one of two characters who did it, this is a valuable route to follow.

So Mario says that it was either DK (Donkey Kong) or Bowser, Waluigi says that it was either DK or Yoshi, and DK says it was either Yoshi or Bowser. What if we left DK’s testimony out for now. So Mario: DK or Bowser, and Waluigi: Yoshi or DK. We know that either one of these characters have to be telling the truth, so the other is the culprit, or both are telling the truth. If one is the culprit, it means the other is telling the truth. But none of them mentions the other. Therefore both have to be telling the truth.

Now we know that both Marion and Waluigi are telling the truth, so both their statements have to be true. So it was “either DK or Bowser” and it was “either Yoshi or DK”. As you may be able to notice, the only overlap in these statements is Donkey Kong, and so we can conclude that Donkey Kong has to be the culprit.

To summarize, we saw that Mario and Waluigi had testimonies that implied that both are telling the truth as none implicated the other, and therefore found the common ground that would allow both to be truthful.

To me the most intriguing part about this puzzle frankly the countless innovative ways one can take to approach it. Which approach did you take?

Tired Monkeys On Typewriters

Infinity… What does it mean? The concept of something going on and on forever is certainly a perplexing one, and is unintuitive in the sense of our daily lives. Everything in our world is finite, completely limited in some way or form, and therefore imagining infinity as some sort of entity, which can be manipulated and used in various situations, is quite new (relatively…). Today I wanted to share a very interesting theorem that I recently read about on the topic of infinity known as the Infinite Monkey Theorem.

infinite_monkey_theorem_by_gremz-d4wmap8.jpg

Given enough time, this theorem says, an unlimited number of monkeys typing on typewriters will eventually reproduce every any work of writing, for example the entire Lord of The Rings book series. This is assuming that the monkeys hit keys at random We all know that when we have going big makes random a lot less random, for example winning lotteries after buying millions of tickets, but this theorem really stretches this idea.

My interpretation of this idea is kind of ambivalent. The main bewildering concept of infinity is that there is no real way to test it out, no function or program we can run to get the results which we want, and therefore it is also hard to visualize. In my mind, if there were to be a computer that ran “infinity” in every sense of the word, which is not possible, I would think that this theorem would be true. Yet at the same time, I think about how as time hurtles by, however unlikely it may be, the keys being hit could be simply a repeating set of letters which produce none of the books which we want them to. As time goes on, this could continue, and although it is probabilistically negligible, it is still possible, and there is nothing saying that this could not continue forever and ever.

What’s your take on this?

 

Flickering Bulbs

What makes me like mathematics so much is that sense of wonder when I learn some new concept or idea. I highly doubt any other field (at least for me) so strongly creates a feeling of everything making sense. Interesting problems are great ways to see the innate intricacy of mathematics, and here is one which I heard of just yesterday.

In a dark, dusty room there lie 100 bulbs switched off, numbered 1-100. A number theorist comes across this room and decides to try something interesting. He first goes though all the multiples of 1, which are all the numbers, and flicks the switch on them, which turns them on. He then goes to all the bulbs which have numbers which are multiples of 2, and turns the switch on them, which would turn them off. Now he visits the bulbs which have numbers which are multiples of 3, and turns the switch on them, and they correspondingly turn either on or off. He does the same for the multiples of all the numbers 1 through 100, and then observes which bulbs are on, and which ones are off. What does he see?

Definitely try this problem out yourself, and when you have solved it (or given up), scroll below the picture.

6a00d8341c630a53ef0134845bdba7970c-600wi.jpg

To solve this problem, we could indeed write a program which runs through every iteration and flip flops the switches to see which ones are on at the end. But we want to this the mathematical way (or in other words the real way), and so we will instead use simple reasoning.

Under what circumstances will a bulb be off at the end? Well all of them started as being off, and so if the bulb was switched an even number of times, it will be off at the end. What does it mean to be switched an even number of times? This means that the number has an even number of factors (including 1 and itself).

So now when will the number be on? If it has an odd number of factors. Now when will this occur? I suggest you try it out yourself.

Soon, you will realize that all factors are in pairs with the exception of square roots, and so numbers that are square numbers therefore are the only ones that have an odd number of factors. The bulbs which are square numbers, 1, 4, 9… are on, and all the others are off.

And that’s it. No calculations, no steps, nothing. Wasn’t that cool?

Some Pirates and Their Treasure

Studying the behavior and reasoning that humans have is a fascinating field, and trying to understand how situations unfold based on rational thinking is a highly relevant and interesting field of study.  It does happen to merge mathematics and the social sciences quite beautifully as well, and here I wanted to talk about one of the most fundamental examples in this area (which doesn’t happen to require much mathematics, but is intriguing nevertheless). This is the dilemma of the pirates and their gold, which if you haven’t seen already, will make you see the intricacy of game theory.

Upon a island in the Caribbean, 5 pirates have a sack of 100 gold coins which they ransacked from a nearby innocent town.  The most senior pirate is obviously in charge, and gets to decide the distribution of coins, but if more than half of the five pirates (which include the senior one) disagree, there is mutiny, and this senior pirate is killed, after which the next most senior pirate takes the same role.  These pirates are intrinsically clever and greedy, and therefore rational in every way.  What is the distribution that the senior pirate will employ to maximize his earnings, and also ensure his survival?  Think about it, and remember to think about it rationally.  I have laid out the analysis below this inspiring picture of a jolly pirate.

pirate7.jpg

Yet again, we will bring it down to the simplest situation and see what we can derive from there.  To make things easier, the most senior pirate will be Pirate 5, and next is 4, and so on until 1.

In the case of two pirates, Pirate 2 can simply allocate all the gold to himself, because even after doing so, at least half of the pirates are in favor of the allocation.

Pirate 2: 100        Pirate 1: 0.

Moving onto to three pirates, we can realize that Pirate 1 is in favor of anything at this point, because if Pirate 3 is killed and it is left to Pirate 2, Pirate 1 will be left with nothing based on the logic we just used above.  So Pirate 3 can give one gold to Pirate 1, and keep the rest, gaining Pirate 1’s vote of approval and getting 99 coins at the same time.

Pirate 3: 99        Pirate 2: 0        Pirate 1: 1

With four pirates, we can see that Pirate 2 is desperate for anything, as if Pirate 4 is killed and Pirate 3 is left in charge, Pirate 2 will be left with absolutely nothing (we just saw this with 3 pirates above).  So Pirate 4 can give one coin to Pirate 2, and so now two out the four votes are in favor, so this distribution is fulfilled.

Pirate 4: 99        Pirate 3: 0        Pirate 2: 1        Pirate 1: 0

Lastly, to our final situation of five jolly pirates, using the same reasoning we understand that Pirates 1 and 3 will get nothing if Pirate 5 is murdered and Pirate 4 is left under control, and therefore will be happy with anything.  So Pirate 5 simply appeases them with 1 coin each, and gains their votes, reaching a majority of 3 votes out of 5.  And so we have our final allocations.

Pirate 5: 98        Pirate 4: 0        Pirate 3: 1        Pirate 2: 0        Pirate 1: 1

If this is not what you thought it would be, join the club.  Analyzing purely rational decision-making in today’s information driven world couldn’t be more useful, and can help you make everyday choices and understand how situations unfold.  Now, to the moral question… where and when does this kind of rationality lead to injustice in our world? Oh and also, make the most of today, it only comes every 4 years…