Many Inquiries

When Will Madao Bloom?

April 2, 2013 in Sappy/Personal | Leave a comment

Introduction, Part I

It’s odd writing posts for a blog, when you’re never sure if someone will read it, when you don’t know if someone else will find what you’ve written to be worth reading. It might be even more bizarre to use blogging as a way to shame yourself into striving to achieve your goals. But I don’t know what else could work. At first, I thought this could be a place where I would let my thoughts run free, where I would post anything I found of interest–from mathematics, philosophy, physics, to interesting literature and poetry, and so on. But shyness got the better of me, and I felt embarrassed that personal posts would be an avenue for others to judge–as if it mattered, let alone as if it happens!

After some thinking, I’ve decided to try to play on this fear-of-judgement to my advantage. Before, I made goals and if they ended up unfulfilled, I could walk away without any burden. This time, I will discuss my goals on this post so that I have a responsibility to the undefined audience to fulfill them–otherwise, they will judge me as a failure, and I don’t want that! (I am acknowledging this complex while simultaneously using it to my advantage). Besides this, I have thoughts that I want to record and remember in years to come, and this is a great way to fulfill THAT goal.

Introduction, Part 2

Why this sudden resoluteness? It’s not like I haven’t had this resolution before–it’s just that I never carried it out. Here’s what provides me with new resoluteness, and hopefully the will to see this through.

I may have mentioned in some earlier posts that I attended Canada/USA Mathcamp 2013. Every alumni you ask will, without a doubt, say it was an incredible experience. For me, it was incredible, and it was horrible, though no fault of the camp itself. Whether I want to admit it or not, I was definitely not mature enough for the experience there, and failed to appreciate how to appreciate it while I was there. I thought I could get by in life, even enjoy it, by creating a bubble around myself, through which only mathematical knowledge would pass through. And so while I struggled on problem sets, everyone else was busy doing bizarre crosswords together, singing, playing ultimate Frisbee, playing Dominion, playing Go and Phutball. I wanted to join in and have fun, but felt like I shouldn’t.

Fast forward a few months, and I am applying to MIT in hopes of finding there a similar culture as I did at Mathcamp. Fast forward another two months for a deferral. Another four months to straight rejections from Harvard, Stanford, Princeton. Another week of self-pity to a few hours ago, where I decided to overcome that self-pity. A few hours ago, I was attending Art of Problem Solving’s Math Jam (discussion, of sorts) on Mathcamp, which brought back many fond memories. I decide I want an experience like Mathcamp again. But that’s only going to happen at MIT, I say. How am I going to get into MIT again, I ask myself? Then it hit me: why not apply as a transfer?

Weeding out Bad Habits Such as…

Laziness,

Being motivated to set new goals, just to get into MIT, I realize, is a bad note to end this post on, and a bad way to start the body of it. This realization came immediately after deciding to apply as a transfer student. Nevertheless, to achieve that goal I would have to achieve (or should) achieve some lesser, related goals, not as means but as ends. In short, while bettering oneself to get into a “good” college/university is a bad idea, sometimes it can set the right idea for how one should improve.

The first step is to weed out bad habits. Until now I have thought my salient characteristic to be hard work, but this was self-deception; rather, it has been stubbornness and laziness and dreaming big, among other things. Neither of the first and the third are particularly bad; both stubbornness and dreaming big are good if one has the means of achieving such a dream. Laziness, on the other hand, is not, and might be considered the worst.

As a journey of a thousand miles begins with one step, laziness is the first bad habit I will weed out, by committing myself to studying math at least two hours a day.

Feeling Inferiority and Self-Pity,

is also the first habit I will weed out. Intentionally being humble, but without self-pity is how I will deal with this.

Antisociality,

is the second habit I will weed out, by learning to enjoy life with my friends. But this doesn’t mean giving up ‘myself’ for what’s popular or to be popular. If I have an interest, I will explore it and find friends that enjoy it, whether or not current friends like it.

Avoiding Anything but Math.

is the third habit I will weed out. I personally even get the feeling that my education in high school has not been complete. I have not taken chemistry, biology, economics. I have not done enough writing, and as you can see if you’ve read far enough, that my writing has suffered as a consequence.

If I can take classes at the University of Utah this summer, I will insist on taking one class in:

writing,
biology,
chemistry,

in addition to two classes in mathematics.

And, of course, I will blog as a means to improve my writing skills. I apologize in advance that often the quality of writing in these posts will suck. But not for long, I hope.

Why?: Because it seems like life will be more enjoyable when I do away with these habits, even if they don’t get me into MIT next year.

Area Arguments

September 28, 2012 in Mathematics | Tags: ams, apa, contour, extended essay, integration, lectures, math team, problems | Leave a comment

I recently came across the following problem on Math StackExchange (my account there: http://math.stackexchange.com/users/39595/michael-zhao).

Problem. Let $ABCD$ as shown. Prove that $\sqrt{[ABCD]} = \sqrt{[ABE]} + \sqrt{[CDE]}$ where $[ABC]$ is the area of $ABC$ .

What we want to prove is

$\sqrt{[ABCD]} = \sqrt{[ABE]} + \sqrt{[CDE]}.$

Squaring both sides and subtracting $[ABE]$ and $[CDE]$ from both sides gives:

$[AED] + [BEC] = 2\sqrt{[ABE][CDE]}$ .

Dividing both sides by $[BEC]$ gives:

$\dfrac{[AED]}{[BEC]} + 1 = 2 \sqrt{\dfrac{[ABE]}{[BEC]} \dfrac{[CDE]}{[BEC]}}$ . (1)

We prove this instead (if this is true we can go back to the original equation given).

Proof. Since triangles $ABE$ and $BEC$ have the same height from $B$ , the ratio of their areas is given by $AE/EC$ .

Similarly, $[CDE]/[BEC] = ED/BE$ . But observe that by AA similarity, $ABE$ and $CDE$ are similar, and hence $BE/ED = AE/EC$ .

This means $\dfrac{AE}{EC} \cdot \dfrac{ED}{BE} = 1$ , and so $\dfrac{[ABE]}{[BEC]} \dfrac{[CDE]}{[BEC]} = 1$ . Thus the right-hand side of (1) equals 2.

Notice further that $[ABD] = [ABC]$ and subtracting $[ABE]$ from both sides gives

$[ABD]-[ABE] = [ABC]-[ABE] \Rightarrow [AED] = [BEC]$ ,

and so the left-hand side of (1) is: $\dfrac{[AED]}{[BEC]} + 1 = 2$ . QED.

Notes on APA Formatting and Citations in LaTeX

September 28, 2012 in LaTeX/Programming | Tags: apa, apa6, apacite, bibliography, bibtex, citation, formatting, latex, social science, url, wikipedia | Leave a comment

Getting APA formatting setup on LaTeX was a pain for me, most possibly because I’ve only recently started messing with LaTeX a lot. Nevertheless, I’d like to record what I did to get the formatting set up, and various tidbits that you need to be careful about to produce APA6 with BibTeX. So, suppose we are writing an essay for psychology and the teacher requires that it is has APA formatting.

1. Obtaining the APA document class. Do not manually try to do APA formatting. Instead, look for the APA 6th edition document class package on CTAN: http://www.ctan.org/tex-archive/macros/latex/contrib/apa6. Download the .zip file and extract everything to some folder, say C:\Users\Username\Desktop. Open up the “apa6.dtx” file in TeXnicCenter (or whatever program works for you), and then hit compile. Of course, it will output a pdf “apa6.pdf” and you will have many errors and warnings: that’s ok. If you look in the folder where the “apa6.dtx” file was, you should now also have a file called “apa6.cls”, which is the APA 6th edition document class file.

2. Setting up APA on a .tex file. Suppose you are working on an essay, stored in C:\Users\Username\Desktop\Essay for Psychology\Essay.tex. Copy and paste the apa6.cls file into the “Essay for Psychology” folder. You can now put the following in the preamble of “Essay.tex”:
\documentclass{apa6}

You will now want to specify the options for this document class. The three primary options you have are called “jou”, “man”, and “doc”. “jou”, to my understanding, will do everything that “man” does, but also put it in two column format. Most likely this is not what your teacher has requested. However, “man” does include things that you’d need for submission to an APA-format required journal: a titlepage with a running head, commands for abstract and table of contents, etc. I believe “doc” avoids titlepage and header – it just handles double-spacing and section headings and such. For now, let’s use “man”.

Another important option that I encountered was the option to have figures (pictures, graphs) between the text, rather than after the references. If you have any figures that you want to refer to frequently, you might want to also want to include the option “floatsintext”, which will put the floats (figures) in the text rather than after the references. So, including these two options will give you:
\documentclass[man,floatsintext]{apa6}
3. The rest of the preamble. At best, I can include here what packages I want to use. As it turns out, for IB we have to do an extended essay which my supervisor wants in APA format. This is rather unusual since I want to do a mathematics essay. At any rate, this is why I have the following packages:
\usepackage{amsmath} \usepackage{amssymb} \usepackage{graphicx} \usepackage{geometry} \usepackage{hyperref} \usepackage{apacite}

The first two packages are amsmath and amssymb, which are used to typeset math and get fancy symbols. The package graphicx is for including figures in the text, and the package geometry provides an easy way to format the paper (set margins, and such). To be honest, I’m not sure why else I have it.

A comment on the last two packages. Yesterday I was able to get apacite and hyperref working together without problems: I was toying with it today, and couldn’t get lower than 6 errors each time I compiled. I looked online: http://promberger.info/linux/2009/03/18/latex-using-apacite-and-hyperref-in-the-same-document/ and found that the answer is that the hyperref package should come before the apacite package (which is used to make citations and the bibliography in APA format). Now, more on citations later.

4. More on the preamble. I presume that setting the margins to your liking with \setlength commands will cause no problems. Alternately, I do not think setting them as options on the geometry package will cause any problems either. However, we have more to say on the remainder of the preamble, in which commands for the running head, abstract and title/author come. Here is the remainder of my preamble after all the \usepackage code.
\shorttitle{Short title and anything else} \title{Title} \author{Name \\ Anything else you need} \affiliation{Institution Name} \abstract{Abstract here.} \begin{document} \maketitle \tableofcontents \newpage

The \shorttitle command gives you the running head. It should be a short title. The title command gives you a title, \author gives you an author. For my personal convenience, I put anything else I need here (such as word count, IB number, etc.). This information can be put on additional lines with the \\ separation as you see above. The affiliation and abstract should be self-explanatory.

That is where the preamble ends, and where the document begins. However, the first thing in the document part of the code should be the \maketitle. You can (I think “should,” because I believe it’s APA format) have the table of contents come after the abstract with the \tableofcontents command. The \newpage is to separate this from the body of the text.

5. Citations. Obtain the apacite package from here: http://www.ctan.org/tex-archive/biblio/bibtex/contrib/apacite. Like before, extract the files to a separate folder and open and compile apacite.ins to obtain apacite.sty. Include this in your LaTeX project folder (just the apacite.sty). For more information on actually installing the packages, see section 1.1 here: http://www.iit.edu/graduate_college/academic_affairs/pdfs/StyleHelp2.pdf. Once you have the apacite.sty file in your folder (say, C:\Users\Username\Desktop\Essay for Psychology), you can nearly begin citations. We will discuss why you can only “nearly” begin in a moment.

Once you have the citation system set up, you will be able to simply reference things in the body of the essay and the “References” section will automatically be compiled for you. However, for now, I will go over three (four?) standard citation commands (by standard, I mean what I used on my own paper).

Citing multiple sources at once. For this, simply use the command: \cite{source1, source2}. This will give you “(source1,year1), (source2,year2)”.
Citing just the year. For this, simply use the command: \citeA{source1}. This will then give you “source 1 (year 1)”.
Page numbers. This will work for any number of sources, as well as work with \citeA. Simply add [p.#] between \cite and {sources}. For instance, if I wanted the citation “Arfken (1985, p.450)” then I would use the command \citeA[p.450]{Arf85}, where Arf85 is the abbreviation I have given the source (more on this later).
Citing the author and the year. If I wanted the citation (Arfken, 1985), then I would type \cite{Arf85}, where again Arf85 is the abbreviation I have given the source.

Now you might be wondering: How will LaTeX know the information that needs to be on the References page?

6. Creating a BibTeX Database (.bib file). This was the scary part for me. But have no fear! Essentially, you first need to create a .txt file that will store information about the sources that you have drawn from. Later you will change this to a .bib file, open it in TeXnicCenter (or TeXWorks, which is actually the default for me and it seems to be more convenient than TeXnicCenter), and then compile it as BibTeX. The information that you should record for each type of source (book, article, proceedings, etc.) can be found here: http://www.maths.ox.ac.uk/help/faqs/latex/bibtex

As an example, let me show you my .bib file:
@BOOK{Bro03, AUTHOR = "Brown, J.W. and Churchill, R.V.", TITLE = "Complex Variables and Applications", PUBLISHER = "McGraw Hill", YEAR = 2003 } @BOOK{Arf85, AUTHOR = "Arfken, G.", TITLE = "Mathematical Methods for Physicists", PUBLISHER = "Academic Press", YEAR = 1985 } @UNPUBLISHED{Carde12, Author = {Carde, Kevin}, Institution = {Canada/USA Mathcamp}, Howpublished = {Class handout}, Year = {2012}, Title = {Summing Series: Complex Analysis Edition} } @ONLINE{Sik07, author = {Siklos, S.T.C.}, title = {Cauchy Principal Value}, year = {2007}, url = "{http://www.damtp.cam.ac.uk/user/stcs/courses/fcm/handouts/cauchy_principal_value.pdf}" } @MISC{Wiki1, author = "Augustin-Louis{\hspace{4pt}}Cauchy", title = "\textup{In} {W}ikipedia", year = "n.d.", howpublished = "Retrieved September 28, 2012 from \url{http://en.wikipedia.org/wiki/Augustin-Louis_Cauchy\#Complex_functions}", } @MISC{Wiki2, author = "Estimation{\hspace{4pt}}lemma", title = "\emph{In} {W}ikipedia", year = "n.d.", howpublished = "Retrieved September 28, 2012 from \url{http://en.wikipedia.org/wiki/Estimation_lemma}", } @MISC{Wiki3, author = "Jordan's{\hspace{4pt}}lemma", title = "\textup{In} {W}ikipedia", year = "n.d.", howpublished = "Retrieved September 28, 2012 from \url{http://en.wikipedia.org/wiki/Jordan's_lemma}", }

You can look up more of these online. The books, unpublished, and online should speak for themselves. Basically, the first entry in the brackets after the @(TYPE OF SOURCE) is the abbreviation you give to the source so that you can easily use the \cite command on it. (Recall for instance, I used the command \cite{Arf85}). Use abbreviations that make sense! Afterwards, you fill in information that in general any citation style will want to draw from.

Weird code for Wikipedia. Let me explain quickly the Wikipedia entries (@MISC). Wikipedia’s entry on citing Wikipedia says that APA formatting requires that their page on plagiarism be formatted as:

Plagiarism. (n.d.). In Wikipedia. Retrieved August 10, 2004, from http://en.wikipedia.org/wiki/Plagiarism

In particular, the APA format requires the article name to take the place of the author.

To cite Wikipedia with BibTeX, they say to use the code:
@misc{ wiki:###, author = "Wikipedia", title = "Plagiarism --- {W}ikipedia{,} The Free Encyclopedia", year = "2004", url = "\url{http://en.wikipedia.org/w/index.php?title=Plagiarism&oldid=5139350}", note = "[Online; accessed 22-July-2004]" }
This however, puts Wikipedia as the author, among other things (and is therefore not in APA format).

The solution, of course, is that we must put the title into the author field. However, if we then compile, we get things like: if I put, say, author = Estimation lemma, the output in the author position is “lemma, E.” Well, that’s not quite the article name. There are two solutions to this. The first, which I figured out myself, is to set put in the author field the code “Estimation\hspace{4pt}lemma” which then simulates the spacing between two words. A better solution to this problem, which I asked on tex.stackexchange.com (if you have any major problems you’re stuck on with your code, GO THERE): http://tex.stackexchange.com/questions/74578/citing-wikipedia-with-apa-formatting-and-bibtex.

The answer is to simply put
author = {{Estimation lemma}}

That is, to use double brackets (double quotation marks doesn’t quite work). The outer set of brackets work just like the quotation marks.

Reason why the “W” in “Wikipedia” is in brackets. This capitalizes the W. APA format requires the first letter of the first word in a title to be capitalized, and everything else to be in lower case. Of course, given that Wikipedia says APA doesn’t want that in citing Wikipedia, we better get rid of it.

Dangers and benefits of using the \url{…} command in your .bib file. The benefit of this is that when the citation appears in your references page, the \url command automatically breaks up long URLs in natural places (such as after/before a backslash, etc.). The problem with this is that it conflicts with BibTeX a lot – you can find that issue all over the web. I don’t have any certain solution to this. Some things I did to solve this problem:

Take your LaTeX project file and any necessary other files (such as apa6.cls and apacite.sty) to a new folder, and compile there.
Include the \url{…} command in the “howpublished” field. In this case, when citing Wikipedia in APA format with BibTeX, it’s actually necessary. We want the part that says “Retrieved (date) from …,” which to my knowledge we can only add in in the “howpublished” field (as opposed to the “url” field).

Miscellaneous on .bib files. Do not forget the commas after each field in the example above. Also note that the outer set of brackets work like quotation marks (and since they appear to be more flexible, might be more useful in general than quotation marks). I also think it could cause problems if your .bib file name has spaces, but I am not certain on this. In general I have noticed it is a good idea to avoid spaces in file names when working with TeXnicCenter, however.

Creating a bibliography. Finally, we are basically done. If you have put \usepackage{apacite} in your preamble, put the following code on its own page (usually references are on their own page).

\bibliographystyle{apacite} \bibliography{refs}

The “refs” is whatever you named your .bib file before. Now you need to: compile your LaTeX file. Then compile your BibTeX file. Afterwards, compile your LaTeX file twice. After this you should be done. Any time you make minor edits, be sure to compile LaTeX, then BibTeX, then LaTeX twice. If you get errors that prevent a .pdf from being outputted (or just want to get rid of errors in general), look at every possible piece of offending code. Generally, you will be able to tell when the error is in the body of the essay (if you’re used to TeXing, you can avoid this). Otherwise, look at whether packages conflict with each other, whether the order of the packages might conflict with each other, etc. If all else fails, Google the problem or go to tex.stackexchange.com.

When all is said and done, you should have something that looks like this (note: on my Windows 7 64-bit laptop, when I compile this I only get 1 warning for no citations which will, of course, go away when I put in citations).
\documentclass[man,floatsintext]{apa6} \usepackage{amsmath} \usepackage{amssymb} \usepackage{graphicx} \usepackage{geometry} \usepackage{hyperref} \usepackage{apacite}


\shorttitle{Short title and anything else}

\title{Title}

\author{Michael Zhao \\ Anything else you need}

\affiliation{Institution Name}

\abstract{Abstract here.}
\begin{document}

\maketitle

\tableofcontents

\newpage

\newpage \bibliographystyle{apacite} \bibliography{references} \end{document}

Logic Problem and Logical Fallcies

September 12, 2012 in Logic/Philosophy | Tags: fallacy, formal, fossil, kill, logic, natives | Leave a comment

[Update]: See the edit below, I was erroneous in saying that the answer “You will boil me in water” is wrong. The initial reasoning that I heard in justification of this statement was in fact wrong, however.

My brother challenged me with a problem he had heard in school and that his class had solved together.

Problem. While exploring the Amazon Jungle, Professor Fossil was seized by hostile natives who told him he could make one final statement which would determine how he would die. If the statement he made was false, he would be boiled in water. If the statement were true, he would be fried in oil. Since Fossil found neither option too attractive, he made a statement that got him out of this seemingly impossible situation. What is the one statement he made?

I have heard that the answer that everyone agreed was right was that Fossil said: “You will boil me in water.” This is wrong. The answer should be “This statement is false.”

In fact, the first answer of “You will boil me in water” and the reasoning that follows is based on a logical fallacy. The answer relies on the idea the statement “if they boil Fossil in the water, then what he said is false.” Then the solution claims: so he must be fried in oil! Then it goes on to say: but if that were the case, then what he said is true. The natives can reason as long as they want, but they won’t find what he says to be true or false. But this is based on flawed logic.

Why is the reasoning that “if they boil Fossil in the water, then what he said is true” a fallacy? Consider the following statement: if I see a white cat, I have seen a cat. Now what if we switch the underlined clause with the bold and underlined clause? The statement becomes “if I have seen a cat, I see a white cat.” Is that necessarily true? No, not all cats are white. This is a general principle which we can prove using formal logic: that the statements “if p, then q” and “if q, then p” aren’t necessarily equivalent. That is, one does not imply the other or vice versa.

But the purported “solution” relies on that very fallacy! The problem says “if Fossil says something false, he will be boiled in water.” What the purported solution has done is to switch the bolded clause with the bolded and underlined clause. But we just saw that switching the two isn’t always valid!

Answer. The correct answer is that Fossil said “This statement is false.” If this sentence were true, then “this statement is false” is correct, so the sentence has to be false. Something can’t be both false and true! Now if this sentence is false, then “this statement is false” is false, so the sentence must be true. But we can’t have it be false AND true, so we have to conclude it is neither. The natives then are able to neither boil him in water nor fry him in oil. What he said isn’t true, so they can’t fry him. What he said isn’t false either, so they can’t boil him.

If on the other hand, you dislike the idea that “not true” is the same as “false,” and that “not false” is not the same as “true,” then you still end up with the conclusion that “This statement is false” is neither true or false.

Edit: How silly of me! The answer “You will boil me in water” is not an incorrect answer. In fact, we can simply reason it out as so: suppose that this statement were true. Then that would mean he would be fried in oil. But then it follows his statement is false. Supposing that this statement were false, then he will be boiled in water. In which case, what he said is true. And so this statement can be neither true nor false.

Experience Teaching Math Team: Number Theory Part I

September 7, 2012 in Mathematics | Tags: ability, divisibility, divisor, even, integer, irrational, math team, number, odd, pedagogy, problems, rational, teaching, theory | Leave a comment

“God created the natural numbers, all else is the work of man.” — Kronecker”

We begin with number theory, the study of the integers. Many of you will already have an intuition for how numbers work (if not, then this may be too theoretical). In these first few problems, we try to build and formalize this intuition. We first consider a problem which highlights properties about divisibility that you already have an intuition for:

Problem 1. A thousand students take turns walking down a hall that contains a row of closed lockers, numbered 1 to 1000. The first student opens all the lockers; the second student closes all the lockers which are divisible by two; the third student operates on all the lockers divisible by 3. If a locker was closed, the student opens it and if not the student closes it. The $i$ th student works on the lockers numbered by multiples of $i$ : if a locker was closed, the student opens it and if the locker was open, the student closes it. What is the number of locks that remain open after all the students finish their walks?

We can begin by investigating whether lockers with small numbers remain open or closed. That is, we consider an easier problem. Consider the locker labelled 1: it is opened by the first student then never touched by anyone else. What about the second locker? It is opened by the first, and closed by the second. No one else operates on it.

When does a general locker numbered $n$ remain closed? When an even number of people operate on it, since then for each student who opens that locker, there is a student who closes that locker. We might have began with this invariant principle: if you have something that changes, see what remains the same! We can now turn to the question: when does a locker have an even number of people operating on it? To answer this, we should answer: who operates on locker $n$ ? Any student $i$ for which there exists an integer $k$ such that $n = ik$ , or when $n$ is a multiple of $i$ . That is, student $i$ operates on locker $n$ if $i$ is a divisor of $n$ .

Hence the question is: when does a number have an even number of divisors? Experimentation might yield that unless $n$ is a perfect square, it will have an even number of divisors. More formally, we can say: suppose $d$ is a divisor of $n$ . Then $d|n$ . But we also have $\frac{n}{d} | n$ . Hence divisors come in distinct pairs, unless we have $\frac{n}{d} = d \Rightarrow n = d^2$ , or $n$ is a perfect square.

We have now solved the problem: any locker that isn’t labelled with a perfect square will remain closed. Hence the lockers that end up being opened are the ones with perfect squares as labels. Since $31^2 < 1000 < 32^2$ , we have that $\boxed{31}$ lockers remain open after all the students finish. $\square$

Many of you will also have intuition about even and odd numbers. This can be embodied in the following relations:

(odd) times (odd) is (odd); (odd) plus (odd) is (even)
(odd) times (even) is the same as (even) times (odd) which is (even); (odd) plus (even) is the same as (even) plus (odd) which is (odd)
(even) times (even) is (even); (even) + (even) is (even)Let’s

Finally, we may also represent an even number $n$ as $n = 2k$ , which says that $n$ is a multiple of 2. An odd number $m$ can be expressed as $m = 2j + 1$ which says that $m$ is not divisible by 2. These will be useful later, but for now we see what can be done with this intuition of even and odd.

Problem 2. Let $k$ be an even integer. Is it possible to write 1 as a sum of the reciprocals of $k$ odd integers?

Short of finding an actual representation of 1 as the sum of reciprocals of an even number of odd integers, there doesn’t seem to be a solid direct way to approach this. Let’s approach this indirectly. Suppose that we could find such a representation:

$1 = \dfrac{1}{a_1} + \dfrac{1}{a_2} + \cdots + \dfrac{1}{a_k}$ .

One common strategy is to get rid of what is difficult in a problem $-$ in this case, we might want to get rid of the fractions by multiplying both sides of the equation by $a_1 \cdots a_k$ . This would give us:

$a_1 a_2 \cdots a_k = a_2 a_3 \cdots a_k + a_1 a_3 \cdots a_k + \cdots + a_1 a_2 \cdots a_{k-1}$ .

Notice that the left hand side is a product of odd integers, which is odd. Each of the terms on the right hand side is a product of odd numbers, and is therefore odd. But there are an even number of terms (there were $k$ fractions in the original equation, and multiplying through by $a_1 a_2 \cdots a_k$ won’t change that number), and the sum of an even number of odd numbers will be even. This equation says that an odd number equals an even number, which can’t be true. So our original assumption that such a representation is possible is false. $\square$

Many of you must also have seen fractions, or rational numbers. Formally, rational numbers look like $\frac{a}{b}$ where $a, b$ are integers. Correspondingly, many of you will know about irrational numbers, and will probably consider $\sqrt{2}$ to be an irrational number. But how can we prove this?

Problem 3. Prove that $\sqrt{2}$ is irrational (i.e. not a rational number).

As before, proving this directly might seem kind of tricky. What does being an irrational number entail? On the other hand, if we proceed indirectly as before we have somewhere to start (this is called proof by contradiction). Moreover, we know (or have a rough idea) of the properties that rational numbers have. So, suppose we could write $\sqrt{2}$ as a rational number:

$\dfrac{a}{b} = \sqrt{2}$ .

First, notice that we can assume the fraction is in lowest terms (that is, the greatest common divisor of $a$ and $b$ is 1). Now, what’s difficult or messy about this equation? Compared to the number 2, $\sqrt{2}$ is significantly harder to deal with. So let’s square both sides. Additionally, let’s multiply both sides by $b^2$ afterwards so we are really only dealing with integers. This will give us:

$a^2 = 2b^2$ .

This equation says: we have a perfect square $a^2$ that is a multiple of 2. Clearly then, $a$ is a multiple of 2. To see why, suppose $a$ was not a multiple of 2 (i.e. is odd). Then $a^2$ is odd, which contradicts what the equation above is telling us. So we can say $a = 2k$ for some integer $k$ . If we substitute that into the equation above and divide both sides by 2, we get:

$2k^2 = b^2$ .

By the same reasoning, then, we must have $b = 2j$ for some integer $j$ . But that means $\frac{a}{b}$ wasn’t in lowest terms, even though we clearly could put it in lowest terms! We have a contradiction, and so $\sqrt{2}$ can’t be rational. $\square$ .

Let’s review this method of proof for a moment. If $\sqrt{2}$ could be written as a rational number, then of course it can be written in lowest terms. What we showed was that if this were the case, then the fraction that it’s equal to (which is in lowest terms) is also not in lowest terms! This was a contradiction, and so our original assumption must have been wrong. This is a very standard method of proof, and we will in fact use it once or twice more later.

Finally, you must all have heard of prime numbers. Let’s clarify the definitions of prime numbers for a moment: a prime number is a number that has two divisors. The number 1 is not a prime. A composite number is a number that is not prime. The only even prime is 2, and every other prime is called an odd prime (3, 5, 7, 11, 13, …). You might wonder if there are infinitely many, and the answer is yes: which we will prove later.

For now, consider the following problem.

Problem 4. (AHSME) If $p$ and $q$ are primes and $x^2-px+q=0$ has distinct positive integral roots, find $p$ and $q$ .

If you know Vieta’s formulas, this problem will be cake for you. Suppose you didn’t know Vieta’s formulas – how would you begin? Well, let’s let some variables be the roots of the equation, say $m$ and $n$ . Then we must have:

$x^2 - px + q = (x-m)(x-n)$ .

We can expand the right hand side:

$x^2 - px + q = x^2 - (m+n)x + mn$ .

Notice that the equality must hold for all $x$ . This is simply saying that they are the same quadratic. Now, if we plug $x=0$ into the equation, we get $q = mn$ . This says that two number multiply to a prime number. Then one of the numbers has to be 1, say $n = 1$ , and the other is the prime itself, so $m = q$ . So $mn = q \cdot 1 = q$ . So now suppose we plug in $x=1$ into the above equation. This gives

$1 - p + q = 1 -(m+n) + mn = 1-(m+n) + q$ .

And so $p = m+n = q+1$ . This following equation can give us the answer in two ways:

The equation tells us that we have two primes that are consecutive. The only case (that we know of, and can show in the next method) where this happens is $q=2, p = 3$ .
Suppose $q$ is an odd prime. Then $p$ is an even prime that is bigger than $q$ . But there are no even primes bigger than odd primes – the smallest prime is 2, an even prime. So $q$ is an even prime, or $q=2$ and so $p = 3$ .

Thus, $(q,p) = (2,3)$ . $\square$ .

Next time, we will discuss the fundamental theorem of arithmetic, prime factorization, greatest common divisor and least common multiple and their generalizations. That will get us through problem 10; afterwards we will look at the sum, number and product of the divisors of an arbitrary integer $n$ , the Chicken-McNugget theorem and the Euclidean algorithm. Finally after that will be modular arithmetic and diophantine equations.

(Two) Proofs of the First Isomorphism Theorem

August 25, 2012 in Mathematics | Tags: Further Math, group theory, homomorphism, isomorphism, normal, ring theory, school, subgroup | Leave a comment

School is starting soon, and this year I will finally be able IB Further Math SL, which covers a wide variety of topics – graph theory, group theory, set theory, number theory, and geometry. In regard to group theory, I’ve decided to work ahead since at Mathcamp this summer I’d already taken ring theory and field extensions, which made an article on AoPS much more accessible (http://www.artofproblemsolving.com/Resources/Papers/MildorfNT.pdf). In short, it develops number theory using group and ring theory.

It was assigned as homework to prove the first isomorphism theorem for rings in the field extensions class, and seeing the first isomorphism theorem for groups in article, I decided to try and prove it.

Theorem 1 (First Isomorphism Theorem for Groups). If $\varphi : G \rightarrow H$ is a group homomorphism, then

$G/\textrm{ker}(\varphi) \cong \textrm{im}(\varphi)$ .

In particular, if $\varphi$ is surjective, then $G/\textrm{ker}(\varphi) \cong H$ .

The statement for rings is practically the same.

Theorem 2 (First Isomorphism Theorem for Rings). If $\varphi : R \rightarrow S$ is a ring homomorphism, then

$R/\textrm{ker}(\varphi) \cong \textrm{im}(\varphi)$ .

In particular, if $\varphi$ is surjective, then $R/\textrm{ker}(\varphi) \cong S$ .

Not knowing much about groups, I tried to recall the proof for the second and then pattern the proof for the first on that.

Proof (Theorem 2). Let $I = \textrm{ker}(\varphi)$ , and define $\psi (a+I) = \varphi (a)$ where $a \in R$ , from $R/I$ to $\textrm{im}(\varphi)$ . We want to show that $\psi$ is an isomorphism from $R/I$ to $\textrm{im}(\varphi)$ , so we need to show it is a well-defined, bijective homomorphism. To see that it is well-defined, suppose we had $a + I = b+I$ . Then $a-b \in I$ , so $\varphi (a-b) = 0$ , which implies $\varphi (a) = \varphi (b)$ . Then $\psi (a+I) = \psi (b+I)$ , since $\varphi (a) = \psi (a+I)$ , and similarly for $b$ . Observe that from here, we may also go backwards from $\psi (a+I) = \psi (b+I)$ to $a + I = b+I$ , so $\psi$ is injective.

To show that $\psi$ is a homomorphism, we observe that $\psi ((a+I) + (b+I) = \psi ((a+b)+I) = \varphi (a+b)$ , and

$\varphi (a+b)=\varphi (a)+\varphi (b)=\psi (a+I)+\psi (b+I)$ .

And furthermore, $\psi ((a+I)(b+I)) = \psi (ab + I) = \varphi (ab)$ , and since

$\varphi (ab) = \varphi (a) \varphi (b) = \psi (a+I) \psi (b+I)$ ,

we must have that $\psi$ is a homomorphism.

Clearly $\psi$ is surjective since we defined its range to be $\textrm{im}(\varphi)$ , and so the image of $\psi$ equals its range. $\square$

The proof for groups turns out to be practically the same, although some definitions will make it more convenient.

Definition. A subset $H$ of $G$ is called a subgroup of group $G$ if $H$ is closed under the law of composition used on $G$ . A subgroup $N$ of $G$ is called normal if it is the kernel of a homomorphism from $G$ .

We can see that a normal subgroup behaves almost like an ideal. Just as we define a coset $a + I = \{ a+i | i \in I\}$ for some ring R and ideal I of R, and $a \in R$ , we can define cosets for groups.

Definition. If $H$ is a subgroup of $G$ , then a left coset of $H$ is a set of the form $aH$ for some $a \in G$ , and a right coset is a set $Ha$ . The index of a subgroup $H$ is the number of distinct left cosets of $H$ in $G$ , denoted $[G:H]$ .

We can use this to formulate another definition of a normal subgroup.

Definition. A subgroup $N$ of $G$ is normal if it is invariant under conjugation, or $gNg^{-1} = N$ for all $g \in G$ . If $N$ is a normal subgroup of $G$ , then the quotient group $G/N$ is the set of left cosets of $N$ with the law of composition $(gN)(hN) = (gh)N$ and having order $[G:N]$ .

And now we can prove the FIT for groups.

Proof (Theorem 1). Let $N=\textrm{ker}(\varphi)$ , and define $\psi (gN) = \varphi (g)$ from $G/N$ to $\textrm{im}(\varphi)$ , where $g \in G$ . We will need to show that $\psi$ is a well-defined, bijective homomorphism. Suppose we had $g_1 N = g_2 N$ , then $g_2^{-1}g_1 \in N$ . Thus $\varphi (g_2^{-1}g_1)=e_H$ . Thus

$e_H\varphi (g_2)=\varphi (g_2)\varphi (g_2^{-1})\varphi (g_1)=\varphi(g_1)$ .

And so we have $\varphi (g_2) = \varphi (g_1)$ , yielding $\psi (g_1 N) = \psi (g_2 N)$ . Observe that we may go back from here to find that $\psi$ is injective. The range of $\psi$ is $\textrm{im}(\varphi)$ so the image of $\psi$ equals its range, and so is surjective.

Finally, to show $\psi$ is indeed a homomorphism, we have $\psi((gN)(hN)) = \psi ((gh)N) = \varphi (gh)$ . But since $\varphi (gh) = \varphi (g) \varphi (h) = \psi (gN) \psi (hN)$ , $\psi$ is a homomorphism. $\square$

IMO 2012 #2

August 25, 2012 in Mathematics | Tags: arithmetic mean, geometric mean, inequality, international olympiad, math, mathcamp, minimum, tricks | Leave a comment

This summer, having taken an inequalities class at Canada/USA Mathcamp 2012 (http://mathcamp.org/ - apply there if you’re a high school student interested in math; it’s AMAZING), and having a long-standing interest in inequalities, I decided to try this year’s IMO #2. The problem is as follows.

Problem 1 (IMO 2012, #2): Let $n \geq 3$ be an integer, and let $a_2, a_3, ..., a_n$ be positive real numbers such that $a_2 a_3 \cdots a_n = 1$ . Prove that

$(1+a_2)^2 (1+a_3)^3 \cdots (1+a_n)^n > n^n$ .

Proof: By AM-GM, we have that

$\dfrac{1}{i-1} + \cdots + \dfrac{1}{i-1}+ a_i$ $\geq i\sqrt[i]{\dfrac{1}{(i-1)^{i-1}}a_i}$ ,

where there are $i-1$ terms of the form $\dfrac{1}{i-1}$ on the left hand side. Observe that this simplifies to

$1+a_i \geq i\sqrt[i]{\dfrac{1}{(i-1)^{i-1}}a_i}$ .

Taking both sides to the $i$ -th power gives

$(1+a_i)^i \geq \dfrac{i^i}{(i-1)^{i-1}} a_i$ .

And thus,

$\displaystyle\prod_{i=2}^{n} (1+a_i)^i \geq \prod_{i=2}^{n}\dfrac{i^i}{(i-1)^{i-1}} a_i = \prod_{i=2}^{n}\dfrac{i^i}{(i-1)^{i-1}}$ .

Note that this product on the right hand side evaluates to $n^n$ . Equality is achieved if equality is achieved in the first inequality. In particular, we would require

$a_i = \dfrac{1}{i-1}$ .

This, however, violates the condition that $a_2 a_3 \cdots a_n = 1$ , and so

$\displaystyle\prod_{i=2}^{n} (1+a_i)^i > n^n$ ,

as desired. $\square$

Originally, I had tried to use Hölder’s inequality by making the exponents sum to 1 and introducing $a_1 = 1$ . This quickly became rather complicated and in retrospect was somewhat silly. In contests, at least, it seems that one should try to apply more elementary techniques and afterwards moving on to advanced techniques. I eventually moved to AM-GM, but I got stuck when I applied it as follows:

$1+a_i \geq 2\sqrt{a_i}$ .

The way to overcome this difficulty is to apply AM-GM for $i$ variables, so that a factor of $a_i^{1/i}$ introduces itself on the right hand side. Raising this to the $i$ -th power yields $a_i$ , which will combine with the other $a_i$ when we multiply the inequalities together for $i =2, 3, ..., n$ . It took a while for me to realize how to overcome this second difficulty, but I remembered seeing a similar technique nearly two years earlier, from the Art of Problem Solving’s Intermediate Algebra book.

Problem 2: Let $x, y,$ and $z$ be positive real numbers such that $xy^2 z^3 = 108$ . What is the minimum value of $x+y+z$ ?

Since it appears that we could use the AM-GM inequality, the motivating question is: how many $x$ ‘s, $y$ ‘s, and $z$ ‘s do you need for a geometric mean of $x y^2 z^3$ ? Well, of course the answer is 1, 2, and 3 respectively. But it won’t do if we take an arithmetic mean of x, y, y, z, z, z, for then we’re not minimizing $x+y+z$ . The remedy for this is to take the AM of x, y/2, y/2, z/3, z/3, z/3 – essentially, divide our variables by the power we need in the geometric mean. The problem can then be solved as follows.