The Grass Keeps Growing

What mathematics sometimes provides for us is a templet to think with.  Essentially the unnecessary details are stripped away when we consider something mathematically, and what we see are the bare innards of the problem itself.  This problem is one which exemplifies this concept, and brings to light just how basic math can make situations sometimes hilariously straightforward.

Far away in the lush green fields of Switzerland, lies a field of grass with some quantity of grass on it.  Of course, there are cows, and 60 of them take 30 days to finish off all the grass.  On the same exact field with the same grass, somewhere in another Swiss city, a set of 30 cows take 80 days to ravage the field of all its grass.  How can this be?  Well grass grows…  We know the grass does grow at a uniform rate, and that the cows are all the same, and each consume the same amount of grass every day.  Now how many days would it take for 20 cows to finish eating this same field of grass, and what’s the maximum number of cows could live on the field happily, sustaining themselves for an infinite amount of time (until of course they reproduce and overwhelm the supply).

I do implore you to try this question out yourself, because it really is quite simple.  A kid with no mathematical experience past the fourth grade has the tools to solve this one, which makes it all the more interesting.  The solution lies beneath this lovely picture of a healthy Swiss cow.

img4388.jpg

Notice that the question is as ambiguous as possible regarding the grass itself, and so to simplify things, let us assume that each cow eats one “unit” of grass every day.  We know that there was initially the same number of grass units in each case, which we can take as Y.  We also know that the rate of the grass growing in each case is the same, which we will take as X. What do we have now:

Situation 1:  60 cows finish the grass in 30 days

Situation 2: 30 cows finish the grass in 80 days

 

Therefore the total number of grass units eaten in each case was:

Situation 1:  60 x 30 = 1800 units totally eaten

Situation 2:  30 x 80 = 2400 units totally eaten

The total number of units eaten in each case is simply the units of grass which we had at the beginning, which was Y, which is the same for both, plus the extra grass which was grown in that time, which is simply the rate of growing x the time period.  So now let’s put this into equations:

1800 = Y + 30X

2400 = Y + 80X

These are basic simultaneous equations, which we know how to solve easily.  If you subtract the first equation from the second, you get:

50X = 600

X = 12 units per day

Therefore, upon substituting X back into one of the original equations:

Y = 1800 – 30 x 12 = 1440 units

Now we know the starting units of grass on the field is 1440, and that the grass grows at a rate of 12 units/day. To answer to the first question, we will just take the total number of units eaten as 20X, which makes sense, because it is the number of cows x the number of days.  This equals the initial grass, 1440, plus the extra growth, which is just 12X:

20X = 1440 + 12X

X = 1440/8 = 180 days

We come to our answer, which is that 20 cows would take 180 days to finish off the field of grass.  As for the number of cows which could sustainably live on this field: that would be the rate of growing, as each day the growing would replenish the needs of the cows, so 12 cows could live on this field forever.  On and on they will live, killing off the oldest cow every time a new calf is born, in order to sustain their renewable structure of living.  Maybe humans should learn a little something from this basic problem, and realize that we are really not going to be able to keep exploiting the Earth’s resources without inevitably disastrous consequences…

Advertisements

The Rats of The Dungeon

Regardless of whether you like math or not (though if you’re reading this blog, I’m quite sure you’re interested), I’m sure you’ll enjoy this intricately woven riddle.  I found this gem online while simply browsing the depths of the internet, and had realized that I had to share it.

It is 7pm. A jubilant king has just defeated the enemy kingdom, and wants to throw a lavish banquet at 8pm with his subjects to celebrate. He has a large stash of 1000 bottles of wine for this feast, but knows that exactly one of the wine bottles has been poisoned by one the other kingdom’s spies. There are rats in the dungeon which will die within an hour if given the poison, and the king frantically needs to find out which bottle is poisoned before the feast, which is in one hour.

How many rats are needed to find out which bottle has been poisoned? Remember that since there is one hour, there is no possibility of waiting for rats to see if they die and then accordingly proceed. Therefore all the rats need to be fed at the same time, and the results need to determine the poisoned bottle. Also take into account the fact that one rat can be fed the wine of many wine bottles at once.

This puzzle is an extremely interesting one, and I have outlined the solution below the picture, but I wouldn’t suggest you look at it until you have given the problem a full day of thought.

ratz-wine.jpg

One fundamental procedure to solve such problems is always to start out simply, and then to work upwards from there. For the purposes of this problem I will be using the integer n to represent the nth wine bottle. So what would we do in the case of 2 wine bottles? Only one rat would be needed, as we would simply feed it 1, and if it dies, we know 1 is poisoned, and else 2 is.

Now let’s move onto 4 wine bottles. A logical set of wines for a rat would be 1 and 2 by the same logic. We want at the end for the outcomes to distinguish which one bottle is poisoned, and with the least number of rats, so the next rat could be fed 2 and 3. Now based on which rats die we will know the poisoned wine bottle. Remember that First and Second for the rats has no meaning as we have to feed all the rats at once, and is just for understanding:

Wine Bottles: 1, 2, 3, 4

 

First Rat: 1 and 2

Second Rat: 2 and 3

 

Only First Rat Dies: 1 is poisoned

Only Second Rat Dies: 3 is poisoned

Both Rats Die: 2 is poisoned

No Rats Die: 4 is poisoned

This makes sense, right? The next step will be to try 8 bottles. Again, let’s feed the first rat the first four: 1, 2, 3, 4, and feed another rat 3, 4, 5, 6. From just these two rats, we will be able to narrow it down to two wine bottles. But we need a way to know which one of the two it is. So let’s feed another rat the wine of one of the two wine bottles in each pair: 1, 3, 5, 7. This will tell us which of the two wine bottles it is. Here is a breakdown of what happened:

Wine Bottles: 1, 2, 3, 4, 5, 6, 7, 8

 

First Rat: 1, 2, 3, 4

Second Rat: 3, 4, 5, 6

Third Rat: 1, 3, 5, 7

 

Only First Rat Dies: 2 is poisoned

Only Second Rat Dies: 6 is poisoned

Only Third Rat Dies: 7 is poisoned

First and Second Rats Die: 4 is poisoned

Second and Third Rats Die: 5 is poisoned

First and Third Rats Die: 1 is poisoned

All Rats Die: 3 is poisoned

No Rats Die: 8 is poisoned

I think you’re probably starting to get the idea. Now think about what would happen for 16 wine bottles. One rat with the first 8 and one with the middle 8, first of all. From these we would know which 4 it lies in. Another rat would take the first 2 from each of the sets of 4, so we would know which pair of two within the four it lies in. And another rat would be fed the wine of one in each pair of two, so we would know which one it is. It would be like this:

First Rat: 1, 2, 3, 4, 5, 6, 7, 8

Second Rat: 5, 6, 7, 8, 9, 10, 11, 12

Third Rat: 1, 2, 5, 6, 9, 10, 13, 14

Fourth Rat: 1, 3, 5, 7, 9, 11, 13, 15

I don’t think I need to write all the permutations for this one. If you are starting to see the pattern in this, you will realize that for a set of 2n wine bottles, n rats are needed. Since 1000 > 29, we will need at least 10 rats to find out which dreaded bottle contains the contaminated fermented grape juice. When I first saw this problem, I wouldn’t have thought that there would have been only 10 rats needed.

The unique aspect of this problem is that it is not sequential, as in it does not have you check if a rat dies, and then try another rat, and so on. In its essence you are trying to find a set of sets of particular numbers in which each number appears as a unique set of rats. A very well-known formula in set theory is that if you have k objects in a set, there are 2k possible unique subsets. This idea is inherently connected to the problem, and makes it all the more intriguing to explore further in terms of various mathematical ideas including combinatorics as well.  This problem is also a binary one, where each rat is uniquely identified by a binary number represented by the rats that die.

To end, I would like to thank the valiant rats which gave up their lives. Now we can drink our wine in peace…

A Horde Of Horses

Whoever thinks math is plain old boring numbers is missing out on the whole set of ideas that math encompasses. Logical thinking is synonymous with math, and to do this question, we will use just that. How many races would it take to determine the top 3 horses, given 25 horses, wherein each race consists of 5 horses? This does assume that the only information one can obtain from each race is the ordering, and not the times of the horses. This question really makes you think, and is quite involved, so get a piece of paper, and start doing it! The solution lies below the picture, and so scroll only once you’re ready to see it.

images (1).jpeg

In the start, we will simply have 25 unknown horses, and so the only possible thing that we can do is do 5 races with all the horses. For the purposes of this problem, I will take the letters of the alphabet A-Y to represent the horses. Let’s say that we do five races, and obtain the following results.

1st place 2nd place 3rd place 4th place 5th place
Race 1 A B C D E
Race 2 F G H I J
Race 3 K L M N O
Race 4 P Q R S T
Race 5 U V W X Y

What is it that we want at the end? We want to find out the top three horses, and so any horse that comes 4th or 5th in any race is automatically not needed anymore. So we now come to this.

1st place 2nd place 3rd place 4th place 5th place
Race 1 A B C D E
Race 2 F G H I J
Race 3 K L M N O
Race 4 P Q R S T
Race 5 U V W X Y

Now let’s have a race between the 5 horses which came in first place: A, F, K, P, and U. We have the results of this race here:

1st place 2nd place 3rd place 4th place 5th place
Race 6 K P F A U

Now we have some more observations to make. If A is 4th, we know that it is out of contention, and the same applies for 5th place U. But what we can also eliminate are the horses which are behind A and U in their respect races, as we know they are slower than A and U. The new updated table comes to this:

1st place 2nd place 3rd place 4th place 5th place
Race 1 A B C D E
Race 2 F G H I J
Race 3 K L M N O
Race 4 P Q R S T
Race 5 U V W X Y

We found that among the first place horses, F was third, which means it is still in contention. But what about the horses behind F in Race 2? They have no possibility of getting in the top 3, as they are behind F, and F is already third in at least one race, so they are out. Similarly, we found that P was second in the race of first horses, so the horse directly behind it in Race 4 is possibly third place. But the one behind that is most definitely not in the top 3 (this is 3rd place in Race 4, so R). After eliminating these horses we can see the updated table:

1st place 2nd place 3rd place 4th place 5th place
Race 1 A B C D E
Race 2 F G H I J
Race 3 K L M N O
Race 4 P Q R S T
Race 5 U V W X Y

K won the race between the first place horses, and so is guaranteed to be the overall champion. So K can be left out of any further races. How many horses are we down to now? We only have 5 horses other than K left, and so a race between them will decide the whole ranking:

1st place 2nd place 3rd place 4th place 5th place
Race 7 L P Q M F

We now know that the top 3 ranking of the 25 horses is: K, L, and the P. How many races did we use? We only used 7. This is quite interesting, as we had to do 5 races just at the get-go, and so by only doing 2 races after that we were able to obtain the ranking that we desired. I don’t know how you feel, but something about this problem is extremely satisfying to me.

Nobody Knows

Everybody has some things that they want to keep secret, and here’s a question based on just that. I stumbled upon this fascinating little puzzle just yesterday, and wanted to share it, as I found it quite extraordinary. What would you say if there were 3 people who wanted to know the average salary of their trio and yet wanted their individual salaries to remain anonymous?  This is assuming that there is no intermediary person or machine which can operate on the individual salaries of course, and there are just the three people and their communication. Well, as unlikely as it seems, there is a pretty awesome way to do this. As always, I have explained the solution below the picture, and so do scroll below only when you are ready to see the answer.

3 People Even.jpg

If each person doesn’t want their salary to be revealed, they will have to lie, or at least tweak their salary. First of all, let’s assume the three people as A, B, and C, and their real salaries a, b, and c respectively. What now?

To start with, A will tell B his salary a plus a random value xa. This maintains the anonymity that A wanted, and now B will take this fake salary, and add his salary b and again another random value xb, and tells it to C. C now takes this total and again adds his salary c as well as the random value xc, and then tells it to A. This total salary we now have (a + b + c + xa+ xb + xc) is completely off the target, and A has this useless total in his hands.

3PeopleCircle.png

Now what does A do? He will now just subtract the random value xa that he had added before, which he remembers, and send this new total to B. B then subtracts his random value xb and send this total to C. What is this total? It’s simply a + b + c + xc. So now all C has to do is subtract his xc and now sends that to A, who now can reveal the true total of their salaries, and therefore the average salary of the trio. We now have found the average salary without any of the people having to disclose their salary to any of the others.

As you may be able to see, this can be generalized to any number of people for any such situation which requires people to remain anonymous. So next time a group of your parents are having a discussion about their weights… maybe you can try this out!

Just Keep Moving

It’s always so beautiful when a problem which seems to be so arcane, and appears to require advanced techniques such as differentiation at the very least, breathes new life in a simplistic and sleek solution. This is one such problem.

Consider an equilateral triangle of side length 1m with 3 insects sitting at the vertices. These insects have a speed of 1/3 ms-1, and all are pointed in the direction of the insect clockwise to it, and begin moving with their constant speed of 1/3 ms-1, however they maintain their direction as directly pointing towards the next insect in the triangle. How long do they take to meet, and what distance do they travel? Do take your time and think and try this one through before scrolling below this picture, where you’ll see the solution. The picture should give you an idea of how the situation unfolds.

The first basic observation we can make is that whatever happens in symmetric, and so rotation by 120° will keep it the same at any time, and therefore we know they will all meet at the center, as that is the only point where this holds true for the endpoint.  Each insect is moving towards each other one with some vector component of its speed, and so let’s try and see what happens if we try and delve into that concept of relative velocities.

B is moving toward A with a vector speed of 1/3 ms-1  and the angle BAC is 60° clearly.  What is the vector component of A’s speed in the direction of B?  Let’s draw a triangle.

Screen Shot 2016-02-20 at 3.28.23 PM.png

PQ is the vector of A’s speed, in the direction of C, and therefore QR would be the vector of A’s speed in the direction of B, which would by simple trigonometry be PQ x cos 60. This gives the vector PQ/2, which is half the vector speed of A towards C, which gives a vector of (1/3)/2 ms-1 , 1/6 ms-1 . B is moving towards A at 1/3 ms-1  and A is moving at a relative velocity towards B at 1/6 ms-1 .  Essentially, since these two insects are moving towards each other, they are coming together at a rate 1/3 + 1/6, so 1/2 ms-1 . We know that distance AB is 1m, as the side length of the triangle is 1m, so the time for A and B to meet is distance/speed which is:

Time = D/S

Time = 1m / (1/2 ms-1 ) = 2 seconds

So the time we get is 2 seconds.  Now what about the distance.  Thinking about the arc and path that these insects follow, anyone can get a little disillusioned about this.  But we know these insects have constant speed.  And we know the time.  What is distance? Speed x time.

Distance = S x T

Distance = (1/3 ms-1 ) x 2 s = 2/3 m

I can’t imagine anyone ever saying that this problem looked easier than it actually is.  And this is why we like doing math.

The Drop of a Needle

One of my all time favorite problems is that of Buffon’s Needle. The problem itself is clearly unique and intriguing, and I will show you a solution that is equally astounding, and that requires no calculus or advanced mathematics whatsoever.  The traditional way to solve this problem is using integral geometry, but I can affirmatively say this way is much more savvy.

Buffon.png

The premise of the problem is that on the floor you have lines 1 cm apart, and you drop a needle 1 cm long onto the floor. The task is to find the probability the needle cuts or touches a line. An interesting aspect of this is that it blends the physical world into a math problem, without any physics as such. It brings probability which is generally thought of as drawing balls out of a bag into a more creative and visual setting. I would suggest you try it out before reading further to see the solution.

 

buf_02.png

 

Assumption is one of the first things one must do in any problem. So let us assume that the probability is P. This P can also be thought of the expected number of lines that the needles cuts for every drop when it is carried out a large number of times. In fact let us keep P as an expected value (for example if it is .6, it means that out of every 100 drops, the needles cut 60 lines).

What can we do now? What if the needle was 2 cm? In a way, it is like dropping two needles onto the floor, but the instance says that they are connected together. But what would the expected number of lines that it would cut relative to P? Well it would just be 2P, because it is simply as if two needles were dropped, but they are tied together by the same probability, which would be the same regardless of whether they were dropped separately in the long run. So the expected lines cut for every drop is 2P.

What if the length of the needle is ½ cm? Then the expected lines cut would be simply 1/2 P by the same reasoning. Let’s try something new now. What if the line was a curve. When we have a curve, if we keep breaking it down further and further, we will basically have a set of lines, and so a curve of length 1 cm is approximately 1000 small lines of length 1/1000 cm, which each have an expected value of 1/1000 P by the logic we used before. So added together, they give a total expected value of 1000 x 1/1000 P, which equals P. So whether a line is straight or not is irrelevant to the expected values.

Now we have that insight, consider a circle of diameter 1 cm. Think about how many lines it would cut. If it lands completely in the middle of two lines, it will touch both, giving 2, and if it lands anywhere else it will cut one line twice.

 

noodle3.png

So we can see that the expected value of this circle is 2. But what is the length of the circumference? It’s π x Diameter, which is Pi. We saw that whether the needle is curved doesn’t matter, so the expected value is simply π x P using the logic that we used before. So:

π x P = 2

P = 2/π

 And there it is. We have a super awesome answer using a method that involved nothing but imagination and circles. Who would have guessed that this question, which had nothing to do with circles, would have an answer in terms of π ? Beautiful, right?

Who Knows Who?

There’s a nice area of math called Ramsey Theory which is quite rich in its ideas. It’s a sub-section of graph theory, and a here’s a proof for one of the most fundamental ideas which comprises this field, which can give you an interesting taste of the concepts in it.

In any party of six people either at least three of them are  (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.

Ramsey.png

If you are not familiar with graph theory, it basically consists of the analysis of nodes and edges, and everything about them (it’s not an x and y-axis like you may have thought). One of the best parts of this is that you get to draw a lot. First we should give each person a node, and each person is connected to another with either a blue or red edge. Blue can signify that these two people know each other, and red means that they don’t. Therefore each possible edge has to be drawn and has to be one of the two colors.

If we take one particular person, he/she will be connected to the other 5 people with 5 edges, and by the pigeonhole principle we know that there have to be at least 3 edges of the same color in these 5 since there are only two possible colors. So let’s say that A is connected to B, C, and E by blue edges (AB, AC, and AE). If we consider the edges between B, C, and E (BC, CE, and BE), we know that either all three are of one color, or there are edges of both colors. If there is any edge which is blue, we have completed a triangle, because AB, AC, and AE are already blue, so for example if CE is blue, A, C, and E form a triangle which are pair-wise acquaintances. So what if there are no blue edges between B, C, and E? Well then they must all be red, meaning then that they form their own triangle of pair-wise strangers. This means that for any set of 6 people, there has to be a set of 3 people who are either all friends or all strangers when taken in pairs. If it is hard to visualize it, always just try drawing it out.  Are you starting to get how powerful a graph can be at modeling things?

Be Rational

When we think of proofs, we think of long, esoteric manipulations, yet sometimes they have quite a surprising simplicity (which is one of the reasons they are so intriguing).  Here’s a conjecture which has a really cool proof to it.

irrational-numbers1.png

There exist irrational numbers x and y such that xy gives a rational number.

Let’s start with the most well-known irrational number: √2. What is (√2)√2? If it is rational, then the conjecture is proved, but this is not a trivial thing to find out. So let’s assume it’s irrational. What happens when we raise it to the power √2? That’s ((√2)√2))√2, which results in (√2)2, which is 2, a rational number. And that’s it. If  (√2)√2 is rational, it is proved, and if it is irrational, then we can raise it to the power root two, which is an irrational number to the power an irrational number, and we get a rational number. Thus the theorem is proved.  I know, this was pretty awesome.

Infinity and Beyond

One of the most appealing aspects of proofs is the “wow” factor that some have. Euclid proved the infinitude of primes quite beautifully in my opinion, and this proof is one of my all-time favorites. This can be understood by anyone, and I’m sure anyone who has studied number theory to any depth would have come across it, but for those who haven’t seen it, this proof is something that you should definitely read:

500-prime-numbers.jpg

First 500 primes plotted in a spiral

The proof uses proof by contradiction, and starts out with the assumption that there are a fixed number of primes. Let p be the set of prime numbers, where there are n prime numbers:

Untitled1.png

In that case, consider the number x:

Untitled2.png

Think about the factors that x would have. It turns out that it will have no factors other than itself and 1, which makes it a prime. This is because for it to have any other factor, it needs to divide at least one prime, and x cannot divide any of the primes (1 is not divisible by any of the primes, and therefore 1 added to the product of all primes is prime). You can also think about it as if you were trying to pull out a common factor from this sum, which is not possible, because it will result in a fraction from the 1. Since this number x is also a prime, it gives a contradiction, because we thought we had all the primes in the set p. Therefore the number of primes is infinite. This might well be one of the most beautiful proofs in mathematics.

Where’s My Seat?

This is a rather interesting probability problem I saw, and which really has an absolutely deceiving answer. There is an airplane with 100 seats, and 100 flyers each have 1 seat number assigned to them. Additionally these passengers board the plane in order, so 1 goes first. But the first passenger unknowingly sits in any random seat, and from then on all the passengers sit in their correct position. That is, unless their seat is taken, in which case they also take a random seat (they do not want to disturb anyone seated: this is a flight to Canada). What is the probability that the final passenger sits in his/her correct seat (#100)?

Try out the problem yourself: give it at least a day of thought before scrolling below the picture to see the solution.

original.jpg

The solution to this problem is one that will almost guarantee your anger. All the deliberations, all the calculations, and all the scenarios, and yet the answer is so simple. One way to think about this problem is by using 3 passengers instead on 100 and trying to use basic induction from there onwards. Let’s think about it another way though.

Here is the question that drives the answer: Which seats can the last person sit in? The only possible seats for the last passenger to take are #1 and #100. Now let’s think about why. Every passenger from 1 to 99 has been seated, and they either sat in their own place, which means the number is occupied, or sat in a random place, which also means the number is occupied because someone else was sitting there. But the exception to this was passenger 1, who directly sat in a random place. So we know 2-99 are occupied for sure, and so #1 and #100 are the only possibilities for the last seat. Both of these seats have equal chances of being sat on as a random seat, and therefore there is an equal likelihood of either being the last seat. So we come to a very clean answer: the probability is 50%…