Proof of PIE (Princple of Inclusion-Exclusion)

Introduction

Most other people’s proofs are awful to look at/so long/so boring. Mine is an easily digestible paragraph

The main difference is that others prove the statement as a whole holds inductively (boo!) while I prove that each element is counted exactly once inductively (yay!)

PIE Statement

As a refresher, PIE states that

Given sets $\latex A_1,A_2,\dots,A_n,$
$$\latex |A_1\cup A_2\cup \dots \cup A_n|=\sum\limits_{i=1}^{n} (-1)^{i}\sum\limits_{\text{sym}}|A_1\cap A_2\cap \dots \cap A_i|.$$

PIE Proof

Here goes.

We claim that each element is counted once.

Say that some element $\latex X$ is in $\latex k$ sets. Without loss of generality, these sets are $\latex A_1,A_2,\dots,A_k.$

We proceed by induction. This is obvious for $\latex k=1.$

If this is true for $\latex k,$ we prove this is true for $\latex k+1.$ For every set of sets not containing $\latex A_{k+1}$ with size $\latex i,$ there is a set of sets containing $\latex A_{k+1}$ with size $\latex i+1.$ In PIE, the sum of how many times these sets are counted is $\latex 0.$ There is also one additional set of sets $\latex \{A_{k+1}\},$ so $\latex X$ is counted exactly once.

 

The Woes of Multiple Choice

Multiple choice in its current state is pretty bad. Ambiguity between answer choices can screw up a student. The reward for “process of elimination” (removing terrible answers) is usually based on luck. And if someone doesn’t know the answer and guesses… once again, luck. The way test-makers seem to want to counteract this is by 1) making every answer except the correct one completely terrible and 2) make a ton of terrible test questions (Law of Large Numbers, I suppose).

While multiple-choice is already a pretty bad format in of itself (something like the grading procedure the AIME uses is pretty easy to implement and better for large-scale automated grading), it doesn’t seem teachers will be moving away from it. So can we make multiple choice better?

Split the Point

I propose the following grading system for multiple choice be used instead:

  1. Allow students to pick as many choices as they want.
  2. If they get the answer right, they get 1/(amount of choices they picked) points.

In practice this will eliminate in-test stress. If you’ve got the answers down to 2 choices, rather than having to guess which one is right, you can choose both. It gets annoying when you have to think about one stupid question for the rest of the test because “What if I got it wrong?” and proceed to alternate between two choices.

This also rewards “partial knowledge” (knowing some but not all of the content). If you can figure out an answer or two are ridiculous, you should be rewarded for that in a consistent manner. This does exactly that.

I’ve seen teachers put “co-dependent questions” (they basically amount to being the same question) to avoid this issue and let students guess two options.

An example:

  1. What is a potato? (A) A vegetable (B) A fruit
  2. Name a vegetable. (A) Potato (B) Banana

You can assume a potato is a vegetable and a fruit and get half the points (guaranteed!) by answering 1. (B) and 2. (A). But this is annoying and cumbersome. Nobody wants to take a test like this. Why do people write tests like this?

Splitting the point would make it so you can guess (A) and (B) for the following question and not pray to the RNG gods:

What is a potato?
(A) A vegetable
(B) A fruit
(C) A Nintendo console
(D) Clothing

You can reward your students for not being an absolute moron consistently if you adopt this system.

(By the way, a potato is a vegetable.)

True/False

How would this work with true/false sections? The answer is simple: STOP DOING TRUE/FALSE.

Fill in the Blank/Matching

Fine as is.

exploring euclidean geometry 2: electric boogaloo

First, as a teaser, I’ll publish a couple of things on here.

Preface

It is very easy to teach geometry wrong. There are plenty of high school geometry
books written for profit that do exactly this. Rarely are underlying connections pointed
out, or are thought-provoking problems required. More often than not, those who do
not enjoy math associate it with brutal calculations with ugly numbers. Rounding to the
nearest hundredth or to the nearest inch, and messing up the calculations has been a
constant source of frustration for those in typical math classes.

But the art of math is filled with beauty. In reality, most ratios are simple. A surprising
fact is that in a triangle, HG = 2GO. Most configurations will have beautiful numbers
involved, and each problem’s numbers, if any, have been chosen with care. Rarely will a
problem require unreasonable computation, because understanding the concept will
be enough to solve it.

While these theorems may seem memorization based at first, a deeper understanding
of each theorem and enough practice with them on significant, thought-provoking
problems will be more than enough to have them ingrained in your head. Putting
formulas on flashcards, writing down a formula hundreds of times, and so on are not
efficient methods because the best way to learn to solve problems is to do them!
However, if a problem does not provoke thought, it will not stick around in your brain.
Only when our brains are sufficiently stimulated will they be able to remember what
stimulated them in the first place.

Geometry can be taught wrong in so many ways, but there are so many ways to teach it
right. Only through a variety of perspectives will you understand a concept deeper.
This is one of the many resources out there, and other good resources should be used
as well.

With that said, let us begin Exploring Euclidean Geometry!

Table of Contents

A. The Fundamentals
1. The Axioms of Geometry
2. Definitions and Properties
3. Logic in Mathematics

B. Playing with Circles
1. Circles and Angles
2. Circles and Lines
3. Radical Axes

C. Triangles
1. Area of a Triangle
2. Concurrency and Collinearity
3. Lengths in a Triangle
4. Circles and Triangles

D. Trigonometry
1. Sine, Cosine, and Tangent
2. Reciprocals and Inverses
3. Trigonometric Identities
4. Graphing Trigonometric Functions

E. Analytic Geometry
1. Cartesian Coordinates
2. Conic Sections
3. The Complex Plane
4. Vectors and Matrices
5. Mass Points
6. Barycentric Coordinates
7. Trilinear Coordinates
8. Miscellaneous Algebraic Problems

F. Transformations
1. Generic Transformations
2. Homothety
3. Similitude
4. Inversion
5. Isogonal and Isotomic Conjugates
6. Projective Geometry

G. The Third Dimension
1. Volume and Surface Area
2. Lengths and Cross Sections

H. Extra
1. Pythagorean Theorem
2. Constructions
3. Directed Angles
4. Geometric Inequalities
5. Additional Problems

Progress Report?

What’s in green has already been written, and what’s in red has yet to be written. Fortunately, I only have 2 more beasts to tackle: Projective Geometry and Geometric Inequalities. Pencils/harmonic bundles should not be very hard to cover. Geometric inequalities stem from geometric equalities + inequalities, so it shouldn’t be too hard. Additional problems are for Alg/Combo/NT that I like.

So when will this be done? The short answer is I don’t know. I’m going to be busy for the fall of Freshman year ( marching band 😦 ) and it takes motivation to write the book instead of doing other things. However, I’m optimistic it could be finished in 2 months – but I don’t think I want to rush it or full effort for 2 months. The current pagecount is 306, and I’m expecting to hit at least 375. 400 might be realistic.

What? Day 3 (Beijing)

Note: Day 3, Beijing implies the third day I’ve been in Beijing.

Another note: A regular and hopefully non-boring blog post is coming up. As a note to self, things on the back-burner are (in order of priority) the following:

  1. Hard Work – How people’s idea of “You need to work hard to get really good at something” is completely wrong, and you’ll only ever get good if you don’t consider your investments “hard work.” Also talks about motivations to get top-level at certain activities and how “nice benefits from doing something” has been frequently misconstrued as “reasons to do something” (mathematics and sports are the most common victims of this).
  2. An Attempt at a Public School – Given enough money, time, and influence, it would be very easy for me to construct a good private school (or a series of outside classes or something of the sort). Most of the time when we complain about public schools all we get is an echo chamber, and I think we’ve spent so much time complaining we haven’t really been bothering to find a solution.
  3. Exploring Euclidean Geometry – A progress report and why I am so behind schedule. Estimated release times are completely inaccurate and I really hope I can get it released before I finish my freshman year of high school.

Also, remind me of this in 5 years: Mosquitoborne viruses such as malaria might be able to be solved by getting the mosquitoes to die whenever they bite a human. Whenever I take the time to learn Chem/Bio better, I might want to look into stuff that won’t affect humans but will debilitate/kill mosquitoes. If that isn’t possible, we could engineer a virus that doesn’t do anything against humans but debilitates mosquitoes (sort of the reverse of malaria).

Short explanation: Mosquitoes only get malaria from biting infected humans. This way the amount of mosquitoes with malaria can be limited and we only have to deal with the existing ones. This is probably very far off, but if in 5 years I see this and realize it is actually feasible when I have more knowledge then this is a lead worth pursuing.

Problems

Since I did 2017 AIME I #6-10 for homework a few hours before writing this post, solution outlines, thought process, and comments on these are fresh from the mind.

(Problem 6)

A circle is circumscribed around an isosceles triangle whose two congruent angles have degree measure $x$. Two points are chosen independently and uniformly at random on the circle, and a chord is drawn between them. The probability that the chord intersects the triangle is $\frac{14}{25}$. Find the difference between the largest and smallest possible values of $x$.

Solution:

Let y = 2x. Then we have arcs of lengths y, y, 360-2y. Let’s complementary count. The probability of no intersection is the probability both point are on the same arc, namely (\frac{y}{360})^2+(\frac{y}{360})^2+(\frac{360-2y}{360})^2. If you solve this quadratic, you see that the difference between the two values of y is 24. But we want double that so the answer is 48.

(Problem 7)
For nonnegative integers $a$ and $b$ with $a + b \leq 6$, let T(a,b)=\binom{6}{a}\binom{6}{b}\binom{6}{a+b}. Let $S$ denote the sum of all $T(a, b)$, where $a$ and $b$ are nonnegative integers with $a + b \leq 6$. Find the remainder when $S$ is divided by $1000$.

Solution: Let c=6-(a+b). Then T(a,b)=\binom{6}{a}\binom{6}{b}\binom{6}{c}. Combinatorially, this is basically the same as saying “take 18 objects and choose a any amount of them from each group so you choose 6 in total,” which is the same as saying “18 choose 6.” Evaluating it gives a remainder of 564.

(Problem 8)

Two real numbers $a$ and $b$ are chosen independently and uniformly at random from the interval $(0, 75)$. Let $O$ and $P$ be two points on the plane with $OP = 200$. Let $Q$ and $R$ be on the same side of line $OP$ such that the degree measures of $\angle POQ$ and $\angle POR$ are $a$ and $b$ respectively, and $\angle OQP$ and $\angle ORP$ are both right angles. The probability that $QR \leq 100$ is equal to $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

Solution: These are arcs, arcs, arcs of a circle with diameter OP. The measures of the arcs 2a and 2b are from (0,150). If QR is less than 100, then |2a-2b|\leq 60 as the radius is $latex $100.$ This implies |a-b|\leq 30, and finding the probability that this happens is very standard. Using a graph, you get \frac{16}{25}, so the answer is 41.

(Problem 9)

Let $a_{10} = 10$, and for each integer $n >10$ let $a_n = 100a_{n - 1} + n$. Find the least $n > 10$ such that $a_n$ is a multiple of $99$.

Solution: Essentially you can let a_n=a_{n-1}+n, meaning a_n=n+(n-1)+\dots+11+10. This evaluates to \frac{1}{2}(n+10)(n-9). Now it is not hard to see that the answer is 45.

(Problem 10)

Let $z_1=18+83i,~z_2=18+39i,$ and $z_3=78+99i,$ where $i=\sqrt{-1}.$ Let $z$ be the unique complex number with the properties that $\frac{z_3-z_1}{z_2-z_1}~\cdot~\frac{z-z_2}{z-z_3}$ is a real number and the imaginary part of $z$ is the greatest possible. Find the real part of $z$.

Solution: Terrible problem.

The condition just means z must be on the circumcircle of \triangle z_1z_2z_3. So if we translate this to Cartesian Coordinates, we just want to find the x value of the highest point on the circle; this is the x value of the circumcenter, which is easy to find. The answer is 56.

Pointlessness

I believe what we did this day can be described as “hilariously pointless.”

We decide to take a taxi to the National Aviation Museum. It’s closed, and five minutes later we desperately call the same taxi driver to come pick us up as literally nobody else is there. (Fortunately, they come back and deliver us home.)

We then eat food and do more boring stuff. When we decide to go home, we walk to the further metro station. Basically, if the closer station is Station A and the further one is Station B, we walked to Station B and took the metro to Station A… when we could’ve just walked to Station A.

Our bus ride is even more idiotic; we were supposed to take Line 430 (which we end up taking), but we sit for 7 or 8 stations before realizing we are going the wrong way, which ends up taking us about 30 minutes further away from home. Oops. I would like to say we get home safely that day despite mishaps, but that wouldn’t be true; we didn’t even get home that day. When we got back, it was (technically) already the next day. Fun!

Reflections: Day 1 (Seoul)

I’ve been feeling compelled to write some of the things that go through my head, and a lot of good stuff doesn’t make the blog; I hope to change that soon. There are a couple of interesting things going through my head, math and non-math alike.

As thus I feel a desire to keep a journal of some of the events that transpire and my thoughts on them, not for any real reason in particular other than fun(?) I suppose. Sentence structure will probably be more free-flow as well.

And of course, a lot of you are “here for the math,” so I will include at least one problem every day. Hopefully more. (This is mostly to force me to actually do math every day.)

Problems

(AoPS Introduction to Geometry, Problem 3.44)

\triangle ABC has a right angle at \angle C. Points D and E are on \overline{AB} such that AD=AC and BE=BC. find \angle DCE.

(Classic Problem)

Consider square ABCD and point P outside ABCD such that \angle APB=90^{\circ}. Prove that the angle bisector of \angle APB cuts the area of ABCD into two equal halves.

(Mandelbrot, 2000-something)

There are two possible triangles with AB=13,BC=10, and \angle A = 40^{\circ}. What is the sum of the two possible values of \angle B?

Solutions will be included as a comment to this post, as to best avoid spoilers. None of these problems are hard (though the second one will make you feel very smart when you solve it).

The Plane Ride

Oh, boy, this was the worst part. Plane rides are half the reason I dislike travelling to different continents. On the 10 hour flight to Seoul, I decided to watch movies (and anime) the entire time, much to the chagrin of my parents. (The movies were Spiderverse, Crimes of Grindelwald, and Lego Movie 2. I also found One Punch Man on the plane’s catalogue, and watched it.)

The plane ride was boring, and it (along with actually getting to the hotel) resulted me in being so tired I walked like a drunkard. The food was also unacceptable.

As I left the plane, I saw that some of the people who sat on the plane took the liberty of taking their trash (including a really disgusting half-eaten piece of bread) and throwing it on the ground. No wonder airplanes are such a breeding ground for disease.

Public Transportation

We did not rent a car as public transportation and taxi would pretty much get us anywhere we wanted, and the culture is much more accommodating to those who want to survive without a car. This is a good change of pace from the States, mostly because we stay in a better mood when we don’t have to actually FIND where we are going on our own.

My first impression of the subway system was that it was big. However, I soon noticed something more meaningful; the subway was very clean. Unlike pretty much every urban area in the States, there isn’t a ton of litter on the streets. I suspect this is a cultural thing at some level, because in the States even cities not so densely populated (like my hometown) suffer from litter all the time.

The view of the highways actually looks very similar to home in the SFBA, where you see a couple of billboards, non-residential buildings, and for some reason, a lot of water.

Food

holy CRAP it’s spicy

Jet Lag

The only type of lag that makes the input lag in Smash Ultimate seem acceptable. Fortunately, due to a LOT of luck in timing and some cooperation from my body, I don’t actually have to suffer it (I hope). I went from 6:20 AM on Sunday to something like 3:00 AM the next day (all Pacific Time) without sleeping, so I could sleep and wake up at a relatively normal time. I did wake up relatively early so I suspect I will have to power through the next day without sleeping the only way I know how – with an unhealthy dose of video games.

A Journey Through Niven’s Theorem

Prerequisites

To understand this post, you’ll need to know \sin \alpha+\beta = \sin\alpha\cos\beta+\cos\alpha\sin\beta and \cos \alpha+\beta=\cos\alpha\cos\beta-\sin\alpha\sin\beta. A good grasp on Algebra is also nice. This might be helpful, but knowing these are not necessary.

Preamble

One morning I was thinking of the following configuration:

Consider \triangle OA_1A_2 with OA_1=3, A_1A_2=4, and OA_2=5. Then for all n, construct \triangle OA_nA_{n+1} such that \triangle OA_nA_{n+1}\sim \triangle OA_1A_2.

It doesn’t take long to figure out that this is very easy to express with polar coordinates (or complex, whatever flavor you desire). If O=(0,0) and A_0=(3,0), then in polar coordinates, A_n=(3\cdot (\frac{5}{3})^n,n\theta) where \theta=\arcsin\frac{3}{5}.

Then the realization strikes; none of the triangles “overlap” each other! In other words, there is no pair of integers p,q such that O,A_p,A_q are collinear. What does this mean? Well, there are no integers p,q such that p\theta=q\theta+2\pi k for some integer k. This basically means that there is no rational number k such that \theta = 2\pi k.

The Meat

We claim that \frac{\arcsin \frac{3}{5}}{\pi} is irrational. This is the same as claiming \frac{\arccos \frac{4}{5}}{\pi} is irrational.

Suppose otherwise. Then there must be some positive integer n such that \cos(n\theta)=0. But notice that \cos (n\theta) is a polynomial about \cos \theta. Similarly, \sin (n\theta) is a polynomial about \sin \theta.

We claim that \cos (n+1)\theta = 2\cos \theta \cos n\theta-\cos(n-1)\theta for all n\geq 2. Adding \cos (n-1)\theta and expanding out using the sum-difference identities yields \cos n\theta \cos \theta - \sin n\theta \sin \theta + \cos n\theta \cos \theta + \sin n\theta \sin \theta = 2\cos \theta, which is true.

Now we have a recurrence for \cos n\theta! This general recurrence is called the Chebyshev Polynomial of the First Kind. In fact, generally, the Chebyshev Polynomial of the First Kind states the following:

  1. P_0(x)=1.
  2. P_1(x)=x.
  3. P_{n+1}(x)=2xP_{n}(x)-P_{n-1}(x).

Now we have to prove that \frac{4}{5} is not a root of any of these polynomials. What follows is probably the most ingenious yet simplest step of this problem (and the extension, Niven’s Theorem) – an application of the Rational Root Theorem. We claim that the coefficient of the leading term of P_{n}(x) is 2^{n-1}. The proof is fortunately very obvious; we can discard the P_{n-2}(x) and notice that the leading coefficient of P_{n-1}(x) is multiplied by 2. By the Rational Root Theorem, \frac{4}{5} CANNOT be a root of \cos n\theta for ANY n, because 5 NEVER divides 2^{n-1}. Isn’t it beautiful?

Generalization

Now let’s talk about Niven’s Theorem. It states that the only non-negative values of k such that \frac{\arcsin k}{\pi} is rational are 0, \frac{1}{2}, 1. To do this, we need to expand the Chebyshev Polynomial of the First Kind a little bit more. The Rational Root Theorem will be more powerful if we have the leading coefficient and the constant value; let’s try to look for a pattern of the constant value.

P_0(x)=1

P_1(x)=x

P_2(x)=2x^2-1

P_3(x)=4x^3-3x

P_4(x)=8x^4-8x^2+1

P_5(x)=16x^5-20x^3+5x

P_6(x)=32x^6-48x^4+18x^2-1

Actually, let’s make it a bit more obvious.

P_0(x)=\dots+1

P_1(x)=\dots+0

P_2(x)=\dots-1

P_3(x)=\dots+0

P_4(x)=\dots+1

P_5(x)=\dots-0

P_6(x)=\dots-1

P_7(x)=\dots+0

P_8(x)=\dots+1

P_9(x)=\dots+0

P_{10}(x)=\dots-1

Again, this is very easy to prove using induction. So what does this mean? By the Rational Root Theorem, the only possible values of k are either 0 or of the form \frac{1}{2^m} for even n of P_n(x), and for odd n we can also have things of the form \frac{n}{2^m}. (Remember k is non-negative; negative values are symmetric anyways.) So now all that remains is to prove that these are not roots.

To utilize modular arithmetic, we’ll divide by \frac{1}{x^n} for P_n(x). If we let y = \frac{1}{x}, we are basically “reversing” the polynomial. Let’s rewrite the polynomials in hope we see a pattern:

P_0(x)=x^0(1)

P_1(x)=x^1(1)

P_2(x)=x^2(2-y^2)

P_3(x)=x^3(4-3y^2)

P_4(x)=x^4(8-8y^2+y^4)

P_5(x)=x^5(16-20y^2+5y^4)

P_6(x)=x^6(32-48y^2+18y^4-y^6)

Let Q_{n}(x)=\frac{P_{n}(x)}{x^n}. Notice the recursion is Q_{n+1}(x)=2Q_{n}(x)-y^2Q_{n-1}(x). We’ll write the first few Q_{n}x.

Q_0(x)=1

Q_1(x)=1

Q_2(x)=-y^2+2

Q_3(x)=-3y^2+4

Q_4(x)=y^4-8y^2+8

Q_5(x)=5y^4-20y^2+16

Q_6(x)=-y^6+18y^4-48y^2+32

The only possible roots are 2^0,2^1\dots 2^{n-1},2^n.

Notice that for odd n, the leading coefficient is \pm n. This then causes an obvious problem \pmod n, so it’s proven for odd n. (It is obvious that this is impossible if x=\frac{n}{2^m}, or y=\frac{2^m}{n}, because we need everything to be an integer if we are to get rid of the constant.)

For even n, notice that the constant term is of the form 2^{k+1} while the terms with a coefficient of y are of the form (2^{k})^{2j}), so it won’t work out either. Thus we have proven this is impossible for all rational numbers except for our three exceptions. (For y=2, Q_6(x) is an exception.)

And that’s Niven’s Theorem!

References

Stack Exchange: Is arccos 3/5 rational?

Stack Exchange: 1/pi arccos (1/3) is irrational.

Wikipedia: Niven’s Theorem

Wikipedia: Chebyshev Polynomials

Wolfram Mathworld: Chebyshev Polynomials of the First Kind

Brilliant: Chebyshev Polynomials