After a fairly happy 3-year run, I realized it was time for a change.
Thanks for the good times blogger! I've moved on to using the Pelican static site-generator with GitHub Pages.
These posts will remain here for all time, but comments have been disabled (Disqus is enabled on the new blog) and this blog will only be found at bossylobster.blogspot.com.
Thanks for stopping by. Head on over to the new blog and have a look!
Tuesday, November 18, 2014
Sunday, September 28, 2014
Quantitative Interview Brain Teaser: Computer Assistance
In a previous post I discussed a recent brain teaser I had come across:
Since there are 10 digits in total and each of the digits represent a subcount of occurrences, the total number of occurrences can be represented as the sum:
Additionally, (for example) since each 3 contributes a value of 3 to the digit sum, we must also have
This second equation (which requires the first to make sense) limits our choices of digits a great deal:
The last four are obvious since (for example) 2⋅6>10. We can also say that d5<2. It is clearly no bigger than 2 but in the case that d5=2 we'd also have d2>0 meaning 2d2+5d5=2d2+10>10. Thus to brute force the problem we can choose digits 5 through 9 (5 digits in total) from the 32 (25) different possible ways to make them 0 or 1.
This serves to make the interview question that much more difficult, since there is a unique solution.
Find a 10-digit number, where each digit represents the number of that ordinal number in the whole number. So, the first digit represents the number of 0's in the whole 10 digits. The second digit represents the number of 1's in the whole 10 digits. And so on. The first digit is not a 0.As I promised at the end of the "brain only" post, we'll do better than simply finding an answer, we'll find all of them (with the aid of a computer).
Making the Problem Smaller
Without any thinking, there are 9 billion (9⋅109) total choices. This is not only intractable for the human brain, but becomes difficult for a computer too. A 3 GHz processor in the most optimal case can only perform 3 billion operations per second but there is a lot of counting, lists to create, and otherwise to find a number which fits the criteria. To start, we write our number asn=d0,d1d2d3,d4d5d6,d7d8d9.
d0+d1+d2+d3+d4+d5+d6+d7+d8+d9=10
d1+2d2+3d3+4d4+5d5+6d6+7d7+8d8+9d9=10
0≤d5,d6,d7,d8,d9≤1
Listing All Choices
Now for the fun part: programming (in Python). We now have 90,000 (9⋅104) choices for our first 5 digits and 32 choices for our last 5 digits. We can use Python's range(10**4, 10**5) to represent the 5-digit numbers between 10,000 and 99,999 (inclusive). For the 32 choices for the last 5 digits, we use itertools.product. To see it in action on a smaller set of data: When we ask for 5 repeated copies of the tuple (0, 1) we get 32 possible 5-tuples as expected:Checking Candidates
Before we can iterate through all of our combinations, we need a way to check if a given number fits the criterion. To do that we implement This takes a list of digits, so as we loop over all choices, we'll turn them into lists.Exhaustive Search
Now we can use our accumulated tools, loop through all choices and print any matches As luck would have it, the output is simply In other words, the only number which fits the criteria is the one we found with our brains alone:6,210,001,000
Monday, September 22, 2014
Quantitative Brain Teaser: Brain Only
I've recently been working some atrophied mental muscles and came across a brain teaser that was pretty nifty:
works since we have d0=2 and two 0's (in the second and fourth slots), d1=0 since the number has no 1's, d2=2
since the number has two 2's (in the first and third slots) and d3=0 since the number has no 3's.
We can see this in the above example when we refer to the digits in the four digit number
since we must have nine 0's. However since we have one 9, d9=0 should not occur.
Thus we see none of our choices are possible when d0=9.
But this leaves us with d8=1 as our only choice since we can't place any more 8's. But now the presence of a 1 in
can't coexist with d1=0 so we again see none of our choices are possible when d0=8.
Since we know d7=1 our possible solutions must look like
But again here we reach an impossible point. If we set d1=1 then that digit would contradict itself since it is the second occurrence of 1. If d1=2 it would contradict d2=0 and so on for higher values. In addition, we have used all our digits, so can't increase the value of d1 by placing more 1's in our number.
Thus we see none of our choices are possible when d0=7.
Also as before we can't have d1=1 but now have some extra freedom (an extra digit which doesn't have to be 0) so consider the case d1=2. This corresponds to an occurrence of the digit 2, hence we set d2=1.
Now we have 4 non-zero digits along with six 0's to place:
Thus we have found a number which satisfies the criteria! The zero digits in the 3, 4, 5, 7, 8, and 9 places correspond to the absence of those digits. The non-zero digits in the 0, 1, 2, and 6 places also are the correct counts of each of those digits.
As a math nerd, I was still curious to know how to find every possible number that satisfies the criteria, but that task is too tedious to handle with the brain alone (or at least to be worth reading about when solved by hand). In my follow up to this, I'll show how a combination of smarts and programming can perform an exhaustive search in under 10 seconds.
Find a 10-digit number, where each digit represents the number of that ordinal number in the whole number. So, the first digit represents the number of 0's in the whole 10 digits. The second digit represents the number of 1's in the whole 10 digits. And so on. The first digit is not a 0.
Example
If we shortened from 10 digits to 4 digit, the number2,020
Shorthand Notation
In order to refer to each digit, for search we name them all:n=d0,d1d2d3,d4d5d6,d7d8d9.
n=d0,d1d2d3.
A Practical Approach, Breaking Into Subproblems
Our search space is massive, and with only our wits, we need to quickly find a way to focus on a small space of possibilities. Since the first digit allows us to place a number of 0's we try to set it equal to values starting from the largest. By doing this we only have a little wiggle room to find the places which don't hold a zero.First Case: d0=9
In this case our only choice is9,000,000,000
Thus we see none of our choices are possible when d0=9.
Second Case: d0=8
Here we must have eight 0's and d8>0 so our possible solutions must look like8,000,000,0∗0
8,000,000,010
Third Case: d0=7
Here we have seven 0's and know that d7=1. It must be at least 1 since the first digit is a 7. It can't be 2 because the presence of another 7 would mean another digit (other than 0) would occur 7 times, which is impossible since there are only 10 total digits.Since we know d7=1 our possible solutions must look like
7,∗00,000,100
Thus we see none of our choices are possible when d0=7.
Fourth Case: d0=6
Here we have six 0's and must have d6=1 since (as above), two different digits can't occur six times among 10 digits.Also as before we can't have d1=1 but now have some extra freedom (an extra digit which doesn't have to be 0) so consider the case d1=2. This corresponds to an occurrence of the digit 2, hence we set d2=1.
Now we have 4 non-zero digits along with six 0's to place:
6,210,001,000
As a math nerd, I was still curious to know how to find every possible number that satisfies the criteria, but that task is too tedious to handle with the brain alone (or at least to be worth reading about when solved by hand). In my follow up to this, I'll show how a combination of smarts and programming can perform an exhaustive search in under 10 seconds.
Friday, August 22, 2014
Math for Humans, A Second Attempt
The morning after posting my latest blog post, I woke up still thinking about how to explain the concept.
More importantly, I realized that my goal of writing math for humans failed miserably.
So here is a second go at it.
First we're told we're in a world where 85% of cabs are Green and the rest are Blue. Humans love tables (and they are easy to understand). So we start off with a representative sample of 100 cabs:
After this, we're told that a bystander correctly identifies a cab 80% of the time, or 4 out of every 5. Applying this to the 85 Green cabs (85 is 17 times 5), this bystander will mis-identify 17 as Blue (1 out of 5) and the other 68 will correctly be identified as Green:
Similarly, of the 15 Blue cabs (15 is 3 times 5), this bystander will mis-identify 3 as Green (1 out of 5) and the other 12 will correctly be identified as Blue:
Now Kahneman wants us to use the data at hand to determine what the probability is that a cab is actually Blue given the bystander identified the cab as Blue. To determine this probability, we simply need to consider the final row of the table:
This rows tells us that only 29 cabs will be identified as Blue, and among those, 12 will actually be Blue. Hence the probability will be \[\boxed{\frac{12}{29} \approx 0.413793103}.\] What this really shows is that even though the bystander has a large chance (80%) of getting the color right, the number of Green cabs is so much larger it overwhelms the correctly identified Blue cabs with incorrectly identified Green ones.
More importantly, I realized that my goal of writing math for humans failed miserably.
So here is a second go at it.
First we're told we're in a world where 85% of cabs are Green and the rest are Blue. Humans love tables (and they are easy to understand). So we start off with a representative sample of 100 cabs:
| Category | Green | Blue | Total |
|---|---|---|---|
| Cabs | 85 | 15 | 100 |
After this, we're told that a bystander correctly identifies a cab 80% of the time, or 4 out of every 5. Applying this to the 85 Green cabs (85 is 17 times 5), this bystander will mis-identify 17 as Blue (1 out of 5) and the other 68 will correctly be identified as Green:
| Category | Green | Blue | Total |
|---|---|---|---|
| Cabs | 85 | 15 | 100 |
| ID'd Green | 68 | ||
| ID'd Blue | 17 |
Similarly, of the 15 Blue cabs (15 is 3 times 5), this bystander will mis-identify 3 as Green (1 out of 5) and the other 12 will correctly be identified as Blue:
| Category | Green | Blue | Total |
|---|---|---|---|
| Cabs | 85 | 15 | 100 |
| ID'd Green | 68 | 3 | |
| ID'd Blue | 17 | 12 |
Now Kahneman wants us to use the data at hand to determine what the probability is that a cab is actually Blue given the bystander identified the cab as Blue. To determine this probability, we simply need to consider the final row of the table:
| Category | Green | Blue | Total |
|---|---|---|---|
| ID'd Blue | 17 | 12 | 29 |
This rows tells us that only 29 cabs will be identified as Blue, and among those, 12 will actually be Blue. Hence the probability will be \[\boxed{\frac{12}{29} \approx 0.413793103}.\] What this really shows is that even though the bystander has a large chance (80%) of getting the color right, the number of Green cabs is so much larger it overwhelms the correctly identified Blue cabs with incorrectly identified Green ones.
What I Overlooked
- Dense text is always bad
- Using colors and breaking up text makes reading easier (more modular)
- Introducing mathematical notation is almost always overkill
- Tables and samples are a good way to discuss probabilities
Tuesday, July 29, 2014
Conditional Probabilities in "Thinking Fast and Slow"
I'm currently reading Thinking Fast and Slow by Daniel Kahneman. (Thanks to Elianna for letting me borrow it.) I'm not finished yet, but 60% of the way through I definitely recommend it.
While reading the "Causes Trump Statistics" chapter (number 16), there is a description of a study about cabs and hit-and-run accidents. It describes a scenario where participants are told that 85% of cabs are Green, 15% are Blue and a given observer has an 80% chance of correctly identifying the color of a given cab. Given this data, the chapter presents a scenario where a bystander identifies a cab in an accident as Blue and Kahneman goes on to explain how we fail to take the data into consideration. I really enjoyed this chapter, but won't wreck the book for you.
Instead, I want to do some math (big surprise, I know). However, I want to make it accessible to non-mathematicians (atypical for my posts).
Given the data, Kahneman tells us that the true probability that the cab was Blue is 41% though we likely bias our thinking towards the 80% probability of the identification being correct. I was on the bus and it kept bothering me, to the point that I couldn't continue reading. Eventually I figured it out (when I got to the train) and I wanted to explain how this is computed using Bayes' Law. As a primer, I wrote a post using layman's terms explaining how we use Bayes' Law. (There is some notation introduced but I hope it isn't too confusing.)
\[\text{Pr}(B \mid IDB).\] Using Bayes' Law, we can write
While reading the "Causes Trump Statistics" chapter (number 16), there is a description of a study about cabs and hit-and-run accidents. It describes a scenario where participants are told that 85% of cabs are Green, 15% are Blue and a given observer has an 80% chance of correctly identifying the color of a given cab. Given this data, the chapter presents a scenario where a bystander identifies a cab in an accident as Blue and Kahneman goes on to explain how we fail to take the data into consideration. I really enjoyed this chapter, but won't wreck the book for you.
Instead, I want to do some math (big surprise, I know). However, I want to make it accessible to non-mathematicians (atypical for my posts).
Given the data, Kahneman tells us that the true probability that the cab was Blue is 41% though we likely bias our thinking towards the 80% probability of the identification being correct. I was on the bus and it kept bothering me, to the point that I couldn't continue reading. Eventually I figured it out (when I got to the train) and I wanted to explain how this is computed using Bayes' Law. As a primer, I wrote a post using layman's terms explaining how we use Bayes' Law. (There is some notation introduced but I hope it isn't too confusing.)
Putting Bayes' Law to Use
We need to understand what 41% even corresponds to before we can compute it. What's actually happened is that we know the event \(IDB\) has occurred -- the cab has been identified (\(ID\)) as Blue (\(B\)). What we want is the probability that the cab is Blue given we know it has been identified -- we want:\[\text{Pr}(B \mid IDB).\] Using Bayes' Law, we can write
\[\text{Pr}(B \mid IDB) = \frac{\text{Pr}(B \text{ and } IDB \text{ both occur})}{\text{Pr}(IDB)} \quad \text{and} \quad \text{Pr}(IDB \mid B) = \frac{\text{Pr}(B \text{ and } IDB \text{ both occur})}{\text{Pr}(B)}.\] We're told that a cab can be correctly identified 80% of the time hence
\[\text{Pr}(IDB \mid B) = 0.8\] (i.e. the probability of correct ID as Blue given it is actually Blue). We're also told that 15% of the cabs are Blue hence
\[\text{Pr}(B) = 0.15.\] We can combine these with the second application of Bayes' Law above to show that
\[\text{Pr}(B \text{ and } IDB \text{ both occur}) = \text{Pr}(IDB \mid B) \cdot \text{Pr}(B) = 0.8 \cdot 0.15 = 0.12.\] The only piece of data missing now to finish our computation is \(\text{Pr}(IDB)\).
Using the extended form of Bayes' Law, since we know that the events \(B\) and \(G\) (the cab is Blue or Green) are exclusive and cover all possibilities for the cab, we can say that
\[\text{Pr}(IDB) = \text{Pr}(IDB \mid B) \cdot \text{Pr}(B) + \text{Pr}(IDB \mid G) \cdot \text{Pr}(G).\] Since there is only an 80% chance of correct identification, we know that \(\text{Pr}(IDB \mid G) = 0.2\) (the probability of misidentifying a Green cab as Blue). We also know that 85% of the cabs are Green hence we can plug these in (along with numbers already computed) to get
\[\text{Pr}(IDB) = 0.8 \cdot 0.15 + 0.2 \cdot 0.85 = 0.12 + 0.17 = 0.29.\] Putting it all together we get our answer
\[\text{Pr}(B \mid IDB) = \frac{\text{Pr}(B \text{ and } IDB \text{ both occur})}{\text{Pr}(IDB)} = \frac{0.12}{0.29} = \boxed{\frac{12}{29} \approx 0.413793103}.\] Fantastic! Now we can get back to reading...
\[\text{Pr}(IDB \mid B) = 0.8\] (i.e. the probability of correct ID as Blue given it is actually Blue). We're also told that 15% of the cabs are Blue hence
\[\text{Pr}(B) = 0.15.\] We can combine these with the second application of Bayes' Law above to show that
\[\text{Pr}(B \text{ and } IDB \text{ both occur}) = \text{Pr}(IDB \mid B) \cdot \text{Pr}(B) = 0.8 \cdot 0.15 = 0.12.\] The only piece of data missing now to finish our computation is \(\text{Pr}(IDB)\).
Using the extended form of Bayes' Law, since we know that the events \(B\) and \(G\) (the cab is Blue or Green) are exclusive and cover all possibilities for the cab, we can say that
\[\text{Pr}(IDB) = \text{Pr}(IDB \mid B) \cdot \text{Pr}(B) + \text{Pr}(IDB \mid G) \cdot \text{Pr}(G).\] Since there is only an 80% chance of correct identification, we know that \(\text{Pr}(IDB \mid G) = 0.2\) (the probability of misidentifying a Green cab as Blue). We also know that 85% of the cabs are Green hence we can plug these in (along with numbers already computed) to get
\[\text{Pr}(IDB) = 0.8 \cdot 0.15 + 0.2 \cdot 0.85 = 0.12 + 0.17 = 0.29.\] Putting it all together we get our answer
\[\text{Pr}(B \mid IDB) = \frac{\text{Pr}(B \text{ and } IDB \text{ both occur})}{\text{Pr}(IDB)} = \frac{0.12}{0.29} = \boxed{\frac{12}{29} \approx 0.413793103}.\] Fantastic! Now we can get back to reading...
Bayes' Law Primer
I'm currently writing a blog post that uses Bayes' Law but don't want to muddy the post with a review in layman's terms. So I have something to link, here is a short description and a chance to flex my teaching muscles before the school year starts.
\[\text{Pr}(X \mid Y) = \frac{\text{Pr}(X \text{ and } Y \text{ both occur})}{\text{Pr}(Y)}.\]
This effectively is a re-scaling of the events by the total probability of the given event: \(\text{Pr}(Y)\).
For example, if \(X\) is the event that a \(3\) is rolled on a fair die and \(Y\) is the event that the roll is odd. We know of course that \(\text{Pr}(Y) = \frac{1}{2}\) since half of the rolls are odd. The event \(X \text{ and } Y \text{ both occur}\) in this case is the same as \(X\) since the roll can only be \(3\) is the roll is odd. Thus
\[\text{Pr}(X \text{ and } Y \text{ both occur}) = \frac{1}{6}\]
and we can compute the conditional probability
\[\text{Pr}(X \mid Y) = \frac{\frac{1}{6}}{\frac{1}{2}} = \frac{1}{3}.\]
As we expect, one out of every three odd rolls is a \(3\).
In such a case we know that since the \(Y\)-events are distinct
\[\text{Pr}(X) = \text{Pr}(X \text{ and } Y_1 \text{ both occur}) + \text{Pr}(X \text{ and } Y_2 \text{ both occur}) + \text{Pr}(X \text{ and } Y_3 \text{ both occur}).\]
Using Bayes' law, we can reinterpret as
\[\text{Pr}(X \text{ and } Y_j \text{ both occur}) = \text{Pr}(X \mid Y_j) \cdot \text{Pr}(Y_j)\]
and the above becomes
\[\text{Pr}(X) = \text{Pr}(X \mid Y_1) \cdot \text{Pr}(Y_1) + \text{Pr}(X \mid Y_2) \cdot \text{Pr}(Y_2) + \text{Pr}(X \mid Y_3) \cdot \text{Pr}(Y_3).\]
The same is true if we replace \(3\) with an arbitrary number of events \(n\).
Bayes' Law
For those who aren't sure, Bayes' Law tells us that the probability event \(X\) occurs given we know that event \(Y\) has occurred can easily be computed. It is written as \(\text{Pr}(X \mid Y)\) and the vertical bar is meant like the word "given", in other words, the event \(X\) is distinct from the event \(X \mid Y\) (\(X\) given \(Y\)). Bayes' law, states that\[\text{Pr}(X \mid Y) = \frac{\text{Pr}(X \text{ and } Y \text{ both occur})}{\text{Pr}(Y)}.\]
This effectively is a re-scaling of the events by the total probability of the given event: \(\text{Pr}(Y)\).
For example, if \(X\) is the event that a \(3\) is rolled on a fair die and \(Y\) is the event that the roll is odd. We know of course that \(\text{Pr}(Y) = \frac{1}{2}\) since half of the rolls are odd. The event \(X \text{ and } Y \text{ both occur}\) in this case is the same as \(X\) since the roll can only be \(3\) is the roll is odd. Thus
\[\text{Pr}(X \text{ and } Y \text{ both occur}) = \frac{1}{6}\]
and we can compute the conditional probability
\[\text{Pr}(X \mid Y) = \frac{\frac{1}{6}}{\frac{1}{2}} = \frac{1}{3}.\]
As we expect, one out of every three odd rolls is a \(3\).
Bayes' Law Extended Form
Instead of considering a single event \(Y\), we can consider a range of \(n\) possible events \(Y_1, Y_2, \ldots, Y_n\) that may occur. We require that one of these \(Y\)-events must occur and that they cover all possible events that could occur. For example \(Y_1\) is the event that H2O is vapor, \(Y_2\) is the event that H2O is water and\(Y_3\) is the event that H2O is ice.In such a case we know that since the \(Y\)-events are distinct
\[\text{Pr}(X) = \text{Pr}(X \text{ and } Y_1 \text{ both occur}) + \text{Pr}(X \text{ and } Y_2 \text{ both occur}) + \text{Pr}(X \text{ and } Y_3 \text{ both occur}).\]
Using Bayes' law, we can reinterpret as
\[\text{Pr}(X \text{ and } Y_j \text{ both occur}) = \text{Pr}(X \mid Y_j) \cdot \text{Pr}(Y_j)\]
and the above becomes
\[\text{Pr}(X) = \text{Pr}(X \mid Y_1) \cdot \text{Pr}(Y_1) + \text{Pr}(X \mid Y_2) \cdot \text{Pr}(Y_2) + \text{Pr}(X \mid Y_3) \cdot \text{Pr}(Y_3).\]
The same is true if we replace \(3\) with an arbitrary number of events \(n\).
Monday, November 25, 2013
Trigonometry and Nested Radicals
Early last month, I was chatting with one of my officemates about a curious problem I had studied in high school. I hadn't written any of the results down, so much of the discussion involved me rediscovering the results and proving them with much more powerful tools than I once possessed.
Before writing about the problem I had played around with, I want to give abrief motivation. For as long as humans have been doing mathematics, finding values of \(\pi\) has been deemed worthwhile (or every generation has just found it worthwhile to waste time computing digits).
One such way the Greeks (particularly Archmides) computed \(\pi\) was by approximating a circle by a regular polygon and letting the number of sides grow large enough so that the error between the area of the unit circle (\(\pi \cdot 1^2\)) and the area of the polygon would be smaller than some fixed threshold. Usually these thresholds were picked to ensure that the first \(k\) digits were fully accurate (for some appropriate value of \(k\)).
In many introductory Calculus courses, this problem is introduced exactly when the limit is introduced and students are forced to think about the area problem in the regular polygon:
Given \(N\) sides, the area is \(N \cdot T_N\) where \(T_N\) is the area of each individual triangle given by one side of the polygon and the circumcenter.
Call one such triangle \(\Delta ABC\) and let \(BC\) be the side that is also a side of the polygon while the other sides have \(\left|AB\right| = \left|AC\right| = 1\) since the polygon is inscribed in a unit circle. The angle \(\angle BAC = \frac{2\pi}{N}\) since each of the triangles has the same internal angle and there are \(N\) of them. If we can find the perpendicular height \(h\) from \(AB\) to \(C\), the area will be \(\frac{1}{2} h \left|AB\right| = \frac{h}{2}\). But we also know that
\[\sin\left(\angle BAC\right) = \frac{h}{\left|AC\right|} \Rightarrow h = \sin\left(\frac{2\pi}{N}\right).\] Combining all of these, we can approximate \(\pi\) with the area:
\[\pi \approx \frac{N}{2} \sin\left(\frac{2\pi}{N}\right) = \pi \frac{\sin\left(\frac{2\pi}{N}\right)}{\frac{2 \pi}{N}}. \] As I've shown my Math 1A students, we see that
\[\lim_{N \to \infty} \pi \frac{\sin\left(\frac{2\pi}{N}\right)}{\frac{2 \pi}{N}} = \pi \lim_{x \to 0} \frac{\sin(x)}{x} = \pi\] so these are indeed good approximations.
Starting out with the simplest polygon, the square with \(N = 2^2\) sides, we have
\[A_2 = 2 \sin\left(\frac{\pi}{2}\right) = 2.\] Jumping to the octagon (no not that "The Octagon"), we have
\[A_3 = 4 \sin\left(\frac{\pi}{4}\right) = 4 \frac{\sqrt{2}}{2} = 2 \sqrt{2}.\] So far, the toughest thing we've had to deal with is a \(45^{\circ}\) angle and haven't yet had to lean on Abraham (him, not him) for help. The hexadecagon wants to change that:
\[A_4 = 8 \sin\left(\frac{\pi}{8}\right) = 8 \sqrt{\frac{1 - \cos\left(\frac{\pi}{4}\right)}{2}} = 8 \sqrt{\frac{2 - \sqrt{2}}{4}} = 4 \sqrt{2 - \sqrt{2}}.\]
Before writing about the problem I had played around with, I want to give a
One such way the Greeks (particularly Archmides) computed \(\pi\) was by approximating a circle by a regular polygon and letting the number of sides grow large enough so that the error between the area of the unit circle (\(\pi \cdot 1^2\)) and the area of the polygon would be smaller than some fixed threshold. Usually these thresholds were picked to ensure that the first \(k\) digits were fully accurate (for some appropriate value of \(k\)).
In many introductory Calculus courses, this problem is introduced exactly when the limit is introduced and students are forced to think about the area problem in the regular polygon:
Call one such triangle \(\Delta ABC\) and let \(BC\) be the side that is also a side of the polygon while the other sides have \(\left|AB\right| = \left|AC\right| = 1\) since the polygon is inscribed in a unit circle. The angle \(\angle BAC = \frac{2\pi}{N}\) since each of the triangles has the same internal angle and there are \(N\) of them. If we can find the perpendicular height \(h\) from \(AB\) to \(C\), the area will be \(\frac{1}{2} h \left|AB\right| = \frac{h}{2}\). But we also know that
\[\sin\left(\angle BAC\right) = \frac{h}{\left|AC\right|} \Rightarrow h = \sin\left(\frac{2\pi}{N}\right).\] Combining all of these, we can approximate \(\pi\) with the area:
\[\pi \approx \frac{N}{2} \sin\left(\frac{2\pi}{N}\right) = \pi \frac{\sin\left(\frac{2\pi}{N}\right)}{\frac{2 \pi}{N}}. \] As I've shown my Math 1A students, we see that
\[\lim_{N \to \infty} \pi \frac{\sin\left(\frac{2\pi}{N}\right)}{\frac{2 \pi}{N}} = \pi \lim_{x \to 0} \frac{\sin(x)}{x} = \pi\] so these are indeed good approximations.
Theory is Nice, But I Thought We Were Computing Something
Unfortunately for us (and Archimedes), computing \(\sin\left(\frac{2\pi}{N}\right)\) is not quite as simple as dividing by \(N\), so often special values of \(N\) were chosen. In fact, starting from \(N\) and then using \(2N\), the areas could be computed via a special way of averaging the previous areas. Lucky for us, such a method is equivalent to the trusty half angle identities (courtesy of Abraham De Moivre). To keep track of these polygons with a power of two as the number of sides, we call \(A_n = \frac{2^n}{2} \sin\left(\frac{2\pi}{2^n}\right)\).Starting out with the simplest polygon, the square with \(N = 2^2\) sides, we have
\[A_2 = 2 \sin\left(\frac{\pi}{2}\right) = 2.\] Jumping to the octagon (no not that "The Octagon"), we have
\[A_3 = 4 \sin\left(\frac{\pi}{4}\right) = 4 \frac{\sqrt{2}}{2} = 2 \sqrt{2}.\] So far, the toughest thing we've had to deal with is a \(45^{\circ}\) angle and haven't yet had to lean on Abraham (him, not him) for help. The hexadecagon wants to change that:
\[A_4 = 8 \sin\left(\frac{\pi}{8}\right) = 8 \sqrt{\frac{1 - \cos\left(\frac{\pi}{4}\right)}{2}} = 8 \sqrt{\frac{2 - \sqrt{2}}{4}} = 4 \sqrt{2 - \sqrt{2}}.\]
To really drill home the point (and motivate my next post) we'll compute this for the \(32\)-gon (past the point where polygons have worthwhile names):
\[A_5 = 16 \sin\left(\frac{\pi}{16}\right) = 16 \sqrt{\frac{1 - \cos\left(\frac{\pi}{8}\right)}{2}}.\]
Before, we could rely on the fact that we know that a \(45-45-90\) triangle looked like, but now, we come across \(\cos\left(\frac{\pi}{8}\right)\), a value which we haven't seen before. Luckily, Abraham has help here as well:
\[\cos\left(\frac{\pi}{8}\right) = \sqrt{\frac{1 + \cos\left(\frac{\pi}{4}\right)}{2}} = \sqrt{\frac{2 + \sqrt{2}}{4}} = \frac{1}{2} \sqrt{2 + \sqrt{2}}\] which lets us compute
\[A_5 = 16 \sqrt{\frac{1 - \frac{1}{2} \sqrt{2 + \sqrt{2}}}{2}} = 8 \sqrt{2 - \sqrt{2 + \sqrt{2}}}.\]
\[\cos\left(\frac{\pi}{8}\right) = \sqrt{\frac{1 + \cos\left(\frac{\pi}{4}\right)}{2}} = \sqrt{\frac{2 + \sqrt{2}}{4}} = \frac{1}{2} \sqrt{2 + \sqrt{2}}\] which lets us compute
\[A_5 = 16 \sqrt{\frac{1 - \frac{1}{2} \sqrt{2 + \sqrt{2}}}{2}} = 8 \sqrt{2 - \sqrt{2 + \sqrt{2}}}.\]
So why have I put you through all this? If we wave our hands like a magician, we can see this pattern continues and for the general \(n\)
\[A_n = 2^{n - 2} \sqrt{2 - \sqrt{2 + \sqrt{2 + \sqrt{\cdots + \sqrt{2}}}}}\]
where there are \(n - 3\) nested radicals with the \(\oplus\) sign and only one minus sign at the beginning.
This motivates us to study two questions, what is the limiting behavior of such a nested radical:
\[\sqrt{2 + s_1 \sqrt{2 + s_2 \sqrt{ \cdots }}}\]
as the signs \(s_1, s_2, \ldots\) takes values in \(\left\{-1, 1\right\}\). Recasting in terms of the discussion above, we want to know how close we are to \(\pi\) as we increase the number of sides.
When I was in high school, I just loved to nerd out on any and all math problems, so I studied this just for fun. Having heard about the unfathomable brain of Ramanujan and the fun work he had done with infinitely nested radicals, I wanted to examine which sequences of signs \((s_1, s_2, \ldots)\) produced an infinite radical that converged and what the convergence behavior was.
I'm fairly certain my original questions came from an Illinois Council of Teachers of Mathematics (ICTM) contest problem along the lines of
\[\text{Find the value of the infinite nested radical } \sqrt{2 + \sqrt{2 + \cdots}}\]
or maybe the slightly more difficult
\[\text{Find the value of the infinite nested radical } \sqrt{2 - \sqrt{2 + \sqrt{2 - \sqrt{2 + \cdots}}}}.\]
Armed with my TI-83, I set out to do some hardcore programming and figure it out. It took me around a month of off-and-on tinkering. This second time around as a mathematical grown-up, it took me the first half of a plane ride from SFO to Dallas.
In the next few weeks/months, I hope to write a few blog posts, including math, proofs and some real code on what answers I came up with and what other questions I have.
Subscribe to:
Posts (Atom)