\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 1    *
%**************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $A$, $B$, and $C$ be sets.  Assume that $A \cap
B \cap C = \emptyset$.  Prove that

\[
A \cup B \cup C = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A).
\]

(Note: If $X$ and $Y$ are sets, then $X \setminus Y$ is the set of
elements in $X$ that are not in $Y$.)

\bigskip

\begin{proof}
We prove the equality by showing that the left set contains the right
set and vice versa.  Let $S$ be the set on the left, $A \cup B \cup
C$, and let $T$ be the set on the right, $(A \setminus B) \cup (B
\setminus C) \cup (C \setminus A)$.  Our objective is to prove that $S
= T$.

First, we show that $S$ is contained in $T$.  Let $x$ be an element of
$S = A \cup B \cup C$.  There are then six cases:

\begin{itemize}
\item $x \in A, x \not\in B, x \not\in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A \setminus B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B \setminus C$, and so $x \in T$.

\item $x \not\in A, x \not\in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C \setminus A$, and so $x \in T$.

\item $x \in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B \setminus C$, and so $x \in T$.

\item $x \in A, x \not\in B, x \in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A \setminus B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C \setminus A$, and so $x \in T$.
\end{itemize}

In every case, $x \in T$ as well; therefore, every element of $S$ is
also an element of $T$, and so $S \subseteq T$.  (Note that the case
$x \in A, x \in B, x \in C$ does not exist, since $A \cap B \cap C =
\emptyset$ by assumption.)

Now we show that $T$ is contained in $S$.  Let $x$ be an element of $T
= (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.  There
are then three cases:

\begin{itemize}
\item $x \in A \setminus B$:  This implies that $x \in A$, and so $x \in S$.
\item $x \in B \setminus C$:  This implies that $x \in B$, and so $x \in S$.
\item $x \in C \setminus A$:  This implies that $x \in C$, and so $x \in S$.
\end{itemize}

In every case, $x \in S$ as well; therefore, every element of $T$ is
also an element of $S$, and so $T \subseteq S$.  Since set $S$
contains set $T$ and vice versa, $S$ and $T$ must be the same set;
that is, $S = T$.
\end{proof}

\bigskip

The following alternative presentation of the proof may make the
structure of the argument more clear.

\begin{proof}
Goal: show that if $A \cap B \cap C = \emptyset$, then $A \cup B \cup
C = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.

\begin{enumerate}
\item Let $S = A \cup B \cup C$.
\item Let $T = (A \setminus B) \cup (B \setminus C) \cup (C \setminus A)$.
\item $S \subseteq T$
	\begin{enumerate}
	\item Let $x$ be an element of $S$.
	\item If $x \in A, x \not\in B, x \not\in C$,
		then $x \in A \setminus B \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \in B, x \not\in C$,
		then $x \in B \setminus C \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \not\in B, x \in C$,
		then $x \in C \setminus A \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \in A, x \in B, x \not\in C$,
		then $x \in B \setminus C \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \in A, x \not\in B, x \in C$,
		then $x \in A \setminus B \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item If $x \not\in A, x \in B, x \in C$,
		then $x \in C \setminus A \subseteq T$
		by definition of $\setminus$ and of $T$.
	\item Q. E. D. by exhaustive case analysis.
	\end{enumerate}
\item $T \subseteq S$
	\begin{enumerate}
	\item Let $x$ be an element of $T$.
	\item If $x \in A \setminus B$, then $x \in A \subseteq S$
		by definition of $\setminus$ and of $S$.
	\item If $x \in B \setminus C$, then $x \in B \subseteq S$.
		by definition of $\setminus$ and of $S$.
	\item If $x \in C \setminus A$, then $x \in C \subseteq S$.
		by definition of $\setminus$ and of $S$.
	\item Q. E. D. by exhaustive case analysis.
	\end{enumerate}
\item Q. E. D. since two-way set inclusion implies equality.
\end{enumerate}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A real number $r$ is called {\em sensible} if there
exist positive integers $a$ and $b$ such that $\sqrt{a / b} = r$.  For
example, setting $a = 2$ and $b = 1$ shows that $\sqrt{2}$ is
sensible.  Prove that $\sqrt[3]{2}$ is not sensible.  (Consider only
positive real roots in this problem.)

\bigskip

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that $\sqrt[3]{2}$ is sensible.  Then there exist
positive integers $a$ and $b$ such that $\sqrt{a / b} = \sqrt[3]{2}$.
Squaring both sides of this equation gives $a / b = \sqrt[3]{4}$,
which implies that $\sqrt[3]{4}$ is rational.

Since $\sqrt[3]{4}$ is rational, we can write it as a fraction $x / y$
in lowest-terms, where $x$ is an integer and $y$ is a positive
integer.  Therefore, we have:

\begin{eqnarray*}
\sqrt[3]{4}	& = &	x / y \\
4		& = &	x^3 / y^3 \\
4 y^3		& = &	x^3
\end{eqnarray*}

In the last equation, the left side is even, and so the right side
must be even.  Since $x^3$ is even, $x$ itself must be even.  This
implies that the right side is actually divisible by 8, and so the
left side must also be divisible by 8.  Therefore, $y^3$ is even, and
so $y$ itself must be even.

The fact that both $x$ and $y$ are even contradicts the fact that $x /
y$ is a fraction in lowest terms.  Therefore, $\sqrt[3]{2}$ is not
sensible.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%\problem
%
%\begin{problemparts}
%
%\problempart {\bf (Oiler's Conjecture)} The following claim,
%often confused with the famous Euler Conjecture, was made by the
%driver of a heating-oil truck in Cambridge.  Prove or disprove: the
%equation $a^3 + b^3 + c^3 + d^3 = e^3$ has no solutions when $a$, $b$,
%$c$, $d$, and $e$ are all positive integers.
%
%The claim is false.  One solution to the equation is:
%
%\[
%1^3 + 1^3 + 5^3 + 7^3 = 343 = 7^3
%\]
%
%\problempart {\bf (The Goldenbacher Conjecture)} The oiler's brother-in-law,
%Stu Goldenbacher, has made a claim of his own, which is similar to the
%well-known Goldbach Conjecture.  Prove or disprove: every positive
%even number is the sum of at most two primes, one of which has a
%single digit.  As evidence for his conjecture, Stu points out that 2 =
%2, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5, and 12 = 7 + 5.
%
%There are only four possible ways to write a number $n$ as the sum of
%a single digit prime and another number: $2 + (n-2)$, $3 + (n-3)$, $5
%+ (n-5)$, and $7 + (n-7)$.  If there exists an $n$ such that $n-2$,
%$n-3$, $n-5$, and $n-7$ are all composite, then there is no way to
%write $n$ as the sum of two primes, one of which has a single digit,
%and the conjecture is disproved.
%
%Such is the case if, for example, we choose $n = 2 \cdot 3 \cdot 5
%\cdot 7 = 210$.  Then we have
%
%\begin{eqnarray*}
%n-2 & = & 2 \cdot(3 \cdot 5 \cdot 7 - 1) \quad \mbox{composite} \\
%n-3 & = & 3 \cdot(2 \cdot 5 \cdot 7 - 1) \quad \mbox{composite} \\
%n-5 & = & 5 \cdot(2 \cdot 3 \cdot 7 - 1) \quad \mbox{composite} \\
%n-7 & = & 7 \cdot(2 \cdot 3 \cdot 5 - 1) \quad \mbox{composite}
%\end{eqnarray*}
%
%Therefore, the conjecture is false.
%
%\end{problemparts}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%%%%%%%%%  S99 ps1

\problem (\S 3.1, Exercise 18) As a preliminary, note that a natural
number $n$ is a perfect square if an only if every prime appears an
even number of times in the prime factorization of $n$.  To prove one
direction, note that if $n$ is a perfect square, then there exists an
$m$ such that $n = m^2$.  Each prime appears twice in the prime
factorization of $n$ for each appearance of the prime in the
factorization $m$; thus, each prime appears an even number of times in
the factorization of $m$.  To prove the other direction, suppose that
every prime appears an even number of times in the factorization of
$n$.  Then let $m$ be the product of primes in which each prime
appears half as many times as in the factorization of $n$.  Then $m^2
= n$, and so $n$ is a perfect square.

Now we prove the main claim.  Let $n$ be a natural number that is not
a perfect square.  Assume for the purpose of contradiction that
$\sqrt{n}$ is rational.  Then we can write $\sqrt{n} = a / b$, where
$a$ and $b$ are integers and $b$ is positive.  Squaring and
multiplying both sizes of this equation by $b^2$ gives $nb^2 = a^2$.
Since $n$ is not a perfect square, there is a prime $p$ such that the
highest power of $p$ dividing $n$ is odd.  Since $b^2$ is a perfect
square, the highest power of $p$ dividing $b^2$ is even.  Thus, the
highest power of $p$ dividing $n b^2$ is odd.  On the other hand, the
highest power of $p$ dividing $a^2$ is even, since $a^2$ is a perfect
square.  These conclusions contradict the fact that $n b^2 = a^2$.
Thus, the assumption that $\sqrt{n}$ is rational must be false.


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%
%pset1 problem8 from spring98

\problem \hfill

\bparts

\ppart

Prove by contradiction: for all integers $n > 1$, the $n$th root of a
prime number is irrational.

\ppart Your proof must depend on some property of prime numbers not shared
by all integers greater than one.  Why?  What property?

\eparts

%%%%%%%% SOLUTION
%pset1 problem8 from spring98

\solution{

\bparts

\ppart

Prove by contradiction: for all integers $n > 1$, the $n$th root of
a prime number is irrational.

Proof by contradiction:
Assume for the purposes of contradiction that the $n$th root
of a prime number, $p$, is rational.

$p ^ {1/n} = a/b$ where $a,b \in \naturals$ and $a,b$ are in lowest terms.\\
$p = a^n/b^n$\\
$b^np = a^n$ \\
therefore $a^n$ is divisible by $p$\\
therefore $a$ is divisible by $p$.\\
$a = pa_1$\\
$b^np=p^n(a_1)^n$\\
$b^n=p^{n-1}(a_1)^n$\\
therefore $b^n$ is divisible by $p^{n-1}$, and $n > 1$, \\
so $b^n$ is divisible by $p$\\
therefore $b$ is divisible by $p$\\
therefore $a$ and $b$ are both divisible by $p$, and so are not in lowest terms,
a contradiction. \qed

\ppart Your proof must depend on some property of prime numbers not
shared by all integers greater than one.  Why?  What property?

The property used is that $p | a^n$ for some $n > 0$, implies that $p$
divides $a$.

\eparts
} %solution

%%%%%%%%
%pset1 problem9 from spring98

\problem
Prove by cases: for every $n \in \naturals$, either $4 | n^2$ or $4 |
(n^2-1)$.

%%%%%%%% SOLUTION
%pset1 problem9 from spring98

\solution{
Prove by cases: for every $n \in \naturals$, either $4 | n^2$ or
$4 | (n^2-1)$.\\

Case one: n is even.  Then $2 | n$ and therefore $4 | n^2$.\\

Case two: n is odd.  So $n = 2k+1$ for some $k \in \naturals$.  Then $n^2
-1 = (2k+1)^2 -1 = (4k^2 + 4k +1) - 1 = 4k^2 + 4k = 4(k^2 + k)$, so $4 |
n^2 -1$. \qed
} %solution

%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems

\end{problems}

\end{document}


