Infinitude of Primitive Solutions for x^3+y^3=7z^3 (15.1.45)

Let $V=\mathcal{Z}(x^3+y^3+7z^3)⊂ℂ^3$. Then $\mathcal{I}(V)=(x^3+y^3+7z^3)⊂ℂ[x,y,z]$ (cf. 15.3.24).
(a) Show that $$Φ(x)=x(y^3-7z^3),~~~~~Φ(y)=y(7z^3-x^3),~~~~~Φ(z)=z(x^3-y^3)$$ defines a $ℂ$-algebra homomorphism from $k[V]$ to itself.
(b) Let $φ~:~V→V$ be the morphism corresponding to $Φ$. Observe that $(-2,1,1)∈V$ and compute $φ(-2,1,1)$.
(c) Prove that there are infinitely many points $(a,b,c)∈V$ with $a,b,c∈ℤ$ and the greatest common divisor of $a,b,c$ is $1$.

Proof: (a) It sufficies to show $Φ(x^3+y^3+7z^3)∈(x^3+y^3+7z^3)$, and indeed general polynomial division will reveal $x^3+y^3+7z^3~|~Φ(x^3+y^3+7z^3)$.

(b) We see $φ$ is the morphism defined by $φ(a,b,c)=(a(b^3-7c^3),b(7c^3-a^3),c(a^3-b^3))$, so $φ(-2,1,1)=(12,15,-9)$.

(c) We may assume $a,b,c$ for $(a,b,c)∈V$ are pairwise relatively prime when $a,b,c$ have a trivial greatest common factor; to see this, assume two elements are divisible by a prime $p$. By reducing $x^3+y^3+7z^3=0$ modulo $p^3$, we see that the other element too must be divisible by $p$, impossible if they have trivial greatest common factor.

Let $ψ(a,b,c)=\dfrac{φ(a,b,c)}{d}$ when $d$ is the greatest common factor of the three coordinates of $φ(a,b,c)$. We shall show the first coordinate of $(a,b,c)$ is smaller than or equal in absolute value than that of the first coordinate of $Ψ(a,b,c)$ as well as are the second coordinates when $c≠0$, but that they cannot both be equalities, so $Ψ^i(-2,1,1)≠Ψ^j(-2,1,1)$ for nonnegative $i≠j$.

Assume an arbitrary prime $p~|~d$ when $d$ is the greatest common divisor of the coordinates of $φ(a,b,c)=(a(b^3-7c^3),b(7c^3-a^3),c(a^3-b^3))$ when $(a,b,c)∈V$. We have $p~|~a$ or $p~|~(b^3-7c^3)$; assume the former. Then since $(a,b)=1$ we have $p~|~(7c^3-a^3)$. Reduce modulo $p$ to observe either $p=7$ or $p~|~c$, only the former being possible. But now reduce $a^3+b^3+7c^3=0$ modulo $p=7$ to still get $p~|~b$. Hence $p\not |~a$. Since $p$ was arbitrary this implies $d~|~(b^3-7c^3)$, so $a~|~a'$ when $a'$ is the first coordinate of $Ψ(a,b,c)$. This shows $|a|≤|a'|$, and by very similar reasoning $|b|≤|b'|$.

The only possible case for $|a|=|a'|$ and $|b|=|b'|$ implies $|d|=|b^3-7c^3|=|7c^3-a^3|$. But either $b^3-7c^3=7c^3-a^3$ or $b^3-7c^3=a^3-7c^3$ together with the hypothesis $a^3+b^3+7c^3=0$ implies $c=0$, a contradiction. Therefore the absolute inequality is strict and the proposition is established.$~\square$

The Fitting Ideal of Level 0 is Independent of Choice of Generators (15.1.36-37)

Let $M$ be a finitely generated module over $R$.

36. (a) Show that for all $p≥n$, the Fitting ideal of $M$ is also the ideal in $R$ generated by all the $n×n$ minors of all $p×n$ matrices.
(b) Let $A$ be a fixed $p×n$ matrix as in (a) and let $A'$ be a $p×n$ matrix obtained from $A$ by any elementary row or column operation. Show that the ideal in $R$ generated by all the $n×n$ minors of $A$ is the same as the ideal in $R$ generated by all the $n×n$ minors of $A'$.

37. Suppose $m_1,...,m_n$ and $m_1',...,m_{n'}'$ are two sets of generators for $M$. Let $\mathcal{F}$ be the Fitting ideal calculated with respect to $m_1,...,m_n$ and let $\mathcal{F}'$ be the Fitting ideal calculated with respect to $m_1,...,m_n,m_1',...,m_{n'}'$.

(a) Show that $m_s'=a_{s',1}m_1+...+a_{s',n}m_n$ for some $a_{s',i}∈R$ for all $1 ≤ s ≤ n'$, so that $(-a_{s',1},...,-a_{s',n},0,...,0,1,0,...,0)$ is a relation among $m_1,...,m_n,m_1',...,m_{n'}'$.
(b) If $A$ is an $n×n$ matrix whose rows are the coefficients of relations among $m_1,...,m_n$, show that $\text{det }A=\text{det }A'$ where $A'$ is an $(n+n')×(n+n')$ matrix whose rows are the coefficients of relations among $m_1,...,m_n,m_1',...,m_{n'}'$. Deduce $\mathcal{F}⊆\mathcal{F}'$.
(c) Prove $\mathcal{F}'⊆\mathcal{F}$ and conclude $\mathcal{F}=\mathcal{F}'$.
(d) Deduce from (c) that the Fitting ideal is independent of choice of generators for $M$.

Proof: (36)(a) $⊆$ is clear by simply fitting every $n×n$ matrix of relations into a $p×n$ relations matrix whose minor will be included in the latter ideal, and $⊇$ is also clear since every such minor is the determinant of an $n×n$ relations matrix.

(b) Let $a$ be an $n×n$ minor, the determinant of an $n×n$ matrix $N$. Then let $a'$ be the determinant of the matrix $N'$, which is identical to $N$ save for one of its rows or columns being replaced with another part of a row or column in the $p×n$ matrix. Then since determinants are $R$-bilinear on rows and columns, we have $a+r·a'$ is the $n×n$ minor under the column or row operation on $p×n$ by adding $r$ times the specified row or column to another affecting $N$. Since $N'$ is undisturbed, we can retrieve $a$ the original minor in the new ideal, and since this minor was arbitrary, this shows that the two ideals are equal.

(37)(a) Self-explanatory.

(b) Let $A'$ be the block matrix $$\begin{bmatrix} A & 0 \\ B & I \end{bmatrix}$$ where $I$ is the $n' × n'$ identity, and $B$ is the $n' × n$ matrix converting $n × 1$ vectors in terms of $m_i$ into $n' × 1$ vectors in terms of $m_i'$. Then $\text{det }A = \text{det }A'$ where $A'$ is a matrix of relations among $m_1,...,m_n,m_1',...,m_{n'}'$ as desired.

(c) Let $A$ be an $(n+n')×(n+n')$ relations matrix, and observe that its determinant ideal is contained in the $(n+n')×(n+n')$ minor-generated ideal of the $(n+2n')×(n+n')$ block matrix $A'$, where the top $(n+n')×(n+n')$ block is $A$ and the bottom $n'×(n+n')$ block is $[B~~I]$ as above. By 36(b) we may perform row operations on $A'$ to remain $A''$ a block matrix $$\begin{bmatrix} C & 0 \\ B & I \end{bmatrix}$$ where $C$ is an $(n+n')×n$ relations matrix in terms of $m_1,...,m_n$. The nontrivial minors of this matrix are those $n×n$ minors of $C$, which by 36(a) are all contained in $\mathcal{F}$. Since $\mathcal{F}'$ is the smallest ideal containing all these determinant ideals, we have $\mathcal{F}'⊆\mathcal{F}$ and $\mathcal{F}=\mathcal{F}'$.

(d) When $\mathcal{F}''$ is the Fitting ideal calculated with respect to $m_1',...,m_{n'}'$, we have $\mathcal{F}=\mathcal{F}'=\mathcal{F}''$.$~\square$

Product of Algebraic Sets and its Coordinate Ring (15.1.28)

Prove that if $V$ and $W$ are algebraic sets, then so is $V×W$ and $k[V×W]≅k[V] ⊗_k k[W]$.

Proof: If $V=\mathcal{Z}(I')$ then also $V=\mathcal{Z}(I)$ where $I=\mathcal{I}(\mathcal{Z}(I'))$, with the additional helpful property that $\mathcal{I}(V)=I$. We shall assume the same for $W=\mathcal{Z}(J)$. Lemma: Let $V⊆\mathbb{A}^n$, $W⊆\mathbb{A}^m$ be algebraic sets. Then $\mathcal{I}(V×W)=\mathcal{I}(V)+\mathcal{I}(W)$. Proof: Clearly $⊇$ holds. Now assume $f∈\mathcal{I}(V×W)$ yet $f∉\mathcal{I}(V)+\mathcal{I}(W)$. (Following proof of lemma borrowed from MSE) We can write any polynomial in $k[x_1,...,x_n,y_1,...,y_m]/(\mathcal{I}(V)+\mathcal{I}(W))$ as $$\sum_{i=1}^r \overline{f_ig_i}$$ where $f_i∈k[x_1,...,x_n]$ and $g_i∈k[y_1,...,y_m]$ for all $i$. Let $f$ as above be minimal such that one of its reduction sums has the least summand terms $r$ of the form above of all the polynomials of its hypothesis. Now, assume $f_i(a)=0$ for all $a∈V$ and all $i$; then since $\mathcal{I}(V)=I$ we have $f_i∈I$, hence $f∈\mathcal{I}(V)+(\mathcal{I}(V)+\mathcal{I}(W))=\mathcal{I}(V)+\mathcal{I}(W)$, a contradiction. Therefore $f_k(a)≠0$ for some $k$ and $a∈V$, where we may reorder $f_1=f_k$. Now by the hypothesis for $f$, for all $b∈W$ we have $f(a)(b)=(\sum f_i(a)g_i(b))+t(a)(b)=\sum f_i(a)g_i(b)=0$ (for some negligible $t∈\mathcal{I}(V)+\mathcal{I}(W)$) hence $\sum f_i(a)g_i=p∈\mathcal{I}(W)$. Since $f_1(a)≠0$ write $g_1=\dfrac{p-f_2(a)g_2-...-f_r(a)g_r}{f_1(a)}$ to write $\overline{f}$ in strictly fewer summands, a contradiction.

Proceed with the exercise. To see that $V×W$ is an algebraic set, observe $V×W=\mathcal{Z}(\mathcal{I}(V)+\mathcal{I}(W))$, with $⊆$ being evident and $⊇$ resulting from $V=\mathcal{Z}(\mathcal{I}(V))$ and $W=\mathcal{Z}(\mathcal{I}(W))$. Now, define a $k$-bilinear map $k[V]×k[W]→k[V×W]$ by $(f,g)↦fg$ (well-defined since $\mathcal{I}(V)+\mathcal{I}(W)⊆\mathcal{I}(V×W)$) to induce a surjective group homomorphism $Φ~:~k[V] ⊗_k k[W]→k[V×W]$. This is also a ring homomorphism. To prove bijection, it suffices to check that the ring homomorphism $Φ'~:~k[x_1,...x_n,y_1,...,y_m]→k[V] ⊗_k k[W]$ given by $Φ'(x_i)=x_i ⊗ 1$ and $Φ'(y_i)=1 ⊗ y_i$ factors through $\mathcal{I}(V)+\mathcal{I}(W)$, as then it would be a two-sided inverse to $Φ$ when induced on $k[V×W]$. Indeed, when $f∈\mathcal{I}(V)$ or $g∈\mathcal{I}(W)$ is a generator of $\mathcal{I}(V×W)=\mathcal{I}(V)+\mathcal{I}(W)$, we see $Φ'(f)=f⊗1=0⊗1=0$ and $Φ'(g)=1⊗g=0$.$~\square$

Problem 8 Lemma (Existence of a Complete Sequence)

Lemma: Let $W$ be a tournament directed graph on $2n+1$ nodes where every node projects an arrow to exactly $n$ other nodes. Then there exists on $W$ a sequence $p_1→p_2→...→p_{2n+1}→p_{2n+2}=p_1$ such that $p_i \neq p_j$ for all $i \neq j$ for $1 \leq i,j \leq 2n+1$.

Proof: The results in my attached exercise on Vandermonde determinants imply that there must exist some sequence $p_1→...→p_m→p_{m+1}=p_1$ involving distinct nodes, so let us observe such a sequence where $m$ is assumed to be maximal of all possible sequences of that form. Assume $m \neq 2n+1$. Denote by $P$ the set of nodes in the sequence and set $Q=W \setminus P$. For all $w \in W$ denote by $\text{img }w$ the set of nodes toward which $w$ projects an arrow.

First, a sublemma: Let $q \in Q$ such that $p_i→q→p_j$ for some $i,j$. Then it follows that we must have some $k$ for $p_k→q→p_{k+1}$ (else all the nodes could be shown to point toward $q$ iff $p_i$ does, a contradiction for $p_j$). Then $p_1→...→p_k→q→p_{k+1}→...→p_m→p_{m+1}=p_1$ is a strictly larger sequence, a contradiction by the maximality of $m$. Therefore for all $q \in Q$ we have $P \subseteq \text{img }q$ or $P \cap \text{img }q = \emptyset$.

Assume $m > n$. Then since $1 \leq |Q| \leq n$ we may choose some $q \in Q$, where necessarily $)\text{img }q) \cap P \neq \emptyset$, therefore $P \subseteq \text{img }q$, but now $n < |P| \leq |\text{img }q| = n$, a contradiction.

Therefore $m \leq n$. Then by the sublemma $p_i→q \iff p_1→q$ for $q \in Q$. Since $|P \setminus \{p_1\}| < n$ we must have $p_1 → q$ for some $q \in Q$. Now $(\text{img }p_1) \setminus P = (\text{img }P) \setminus P$ and since $|Q| \geq n+1$ we observe the nonempty $S = (\text{img }P) \setminus P$ and $T = W \setminus (S \cup P)$. Note $P$, $S$, and $T$ partition $W$. Now, $|S| \leq n$ and $(\text{img }S) \cap P = \emptyset$, hence for all $s \in S$ there exists $t \in T$ such that $s→t$. Choose such $s$ and $t$ and observe that $p_1→s→t→p_2→...→p_m→p_{m+1}=p_1$ is a strictly larger sequence once more.$\square$

The motivation behind this lemma was to justify the privilege of imagining every such tournament directed graph as a polygon of nodes, with each successive vertex pointing toward the next. However, the utility of this was never realized.

Computation of Algebraic Sets and Coordinate Rings (15.1.24)

Let $k$ be an infinite field, and let $V=\mathcal{Z}(xy-z)$. Prove that $V$ is isomorphic to $\mathbb{A}^2$ and provide an explicit isomorphism $φ$ from $V$ to $\mathbb{A}^2$ and associated $k$-algebra isomorphism $Φ$ from $k[V]$ to $k[\mathbb{A}^2]$ and their inverses. Is $V=\mathcal{Z}(xy-z^2)$ isomorphic to $\mathbb{A}^2$?

Proof: We see $V$ is the set of all points of the form $(x,y,xy)$, so there is an isomorphism $φ~:~V→W$ given by $φ(x,y,xy)=(x,y)$ with inverse $ψ~:~W→V$ given by $ψ(x,y)=(x,y,xy)$. We see $(xy-z)⊆\mathcal{I}(V)$ naturally and by reducing modulo $(xy-z)$ any $f∈\mathcal{I}(V)$ to a polynomial in $k[x,y]$ we see the remainder must be $0$ as it would annihilate all of $\mathbb{A}^2$, hence $\mathcal{I}(V)⊆(xy-z)$. Thus this induces the isomorphism $Φ~:~k[W]→k[V]$ where $k[V]=k[x,y,z]/(xy-z)$ and $k[W]=k[x,y]$ given by $Φ(f(x,y))=\overline{f(x,y)}$ with inverse $Ψ~:~k[V]→k[W]$ given by $Ψ(\overline{f(x,y,z)})=f(x,y)$.

For the second part, we shall show $k[V]≇k[W]$ where $W=\mathbb{A}^2$ so that $V≇W$ as algebraic sets. First, we have $(xy-z^2)⊆\mathcal{I}(V)$. Assume $\mathcal{I}(V)⊈(xy-z^2)$ and let $f∈\mathcal{I}(V) \setminus (xy-z^2)$ be minimal with respect to the lexicographic ordering $z > y > x$, so $f=z·g_1(x,y)+g_2(x,y)$.

Let $k^2$ be the subset of nonzero squares in $k$, necessarily infinite since each square has only a finite number of square roots, and for each nonzero $b∈k$ let $k^2/b = \{v/b~|~v∈k^2\}$. Note $V$ is the set of points of the form $(x,y,\sqrt{xy})$ whenever $xy$ is square, so for each nonzero $b∈k$ we have an infinite number of $a∈k^2/b$ such that $$f(a,b,\sqrt{ab})=f(a,b,-\sqrt{ab})=$$ $$(\sqrt{ab})g_1(a,b)+g_2(a,b)=(-\sqrt{ab})g_1(a,b)+g_2(a,b)=0$$ Since $\sqrt{ab}$ is nonzero, for each such $b$ we have $g_1(x,b)∈k[x]$ has an infinite number of zeros $x=a$, so $g_1(x,b)=0$ for these $b$. Since there are an infinite number of such $b$, we have $g_1(x,y)∈k(x)[y]$ has an infinite number of roots $y=b$ in $k⊆k(x)$, hence $g_1(x,y)=0$ and by the same argument we find $g_2(x,y)=0$. Hence $f=0$ and we have shown $\mathcal{I}(V)=(xy-z^2)$.

We see $k[W]=k[x,y]$ is a UFD (cf. 9.3.8), and we shall prove $k[V]≇k[W]$ by showing $k[V]=k[x,y,z]/(xy-z^2)$ is not a UFD. Assume otherwise and observe the element $x∈k[V]$, which we shall prove is prime; we may write any element in $k[V]$ uniquely as a polynomial in $k[x,y][z]$ of degree $≤1$, so assume $x=(g_1+z·g_2)(g_3+z·g_4)$. Then $x=g_1g_3+xy·g_2g_4+z(g_1g_4+g_2g_3)$ is the unique reduced form, so $g_1g_3+xy·g_2g_4=x$ and $g_1g_4+g_2g_3=0$. Taking the first relation modulo $x$ we may assume without loss that $x~|~g_1$, and now taking the second relation modulo $x$ necessarily either $x~|~g_2$ or $x~|~g_3$; the former implies $x~|~(g_1+z·g_2)$, and the latter that the relation $g_1g_3+xy·g_2g_4$ involves adding monomial terms of degree strictly larger than $x$, hence the expression does not equal $x$. Thus $x$ must be prime. But $xy=z^2$ would imply $x~|~z$, a contradiction by observing unique representation. Hence $k[V]$ is not a UFD and not isomorphic to $k[W]$, and so neither is $V$ isomorphic to $\mathbb{A}^2$.$~\square$

Problem 10

10. How many zeros are there at the end of the number 1000!=(1)(2)(3)...(999)(1000)? How many for 1001!, 1002!, 1003!, 1004!, and 1005!?

Proof: Let $n=2^a5^bm$ with $2,5~\not |~m$. Then $n$ has $\text{min}\{a,b\}$ zeros at the end, as $10^c~|~n⇔2^c,5^c~|~n⇔c≤\text{min}\{a,b\}$. By Legendre's theorem for the power of $p$ in $n!$ $$v_p(n!)=\sum_{k=1} \lfloor n/p^k \rfloor$$ we see we will have to pay attention only to the power of $5$ in computing the number of zeros at the end. Use Legendre's theorem for this application on $1000$ to obtain $249$ zeros, and the same goes for $1001!,...,1004!$ as they don't have any greater powers of $5$, and $1005=3·5·67$ contributes one extra zero to $1005!$ for a total of $250$.

Problem 9

9. Suppose $n$ children holding loaded water pistols are standing in an open field, no three of them in line, such that all the distances between pairs of them are distinct. At a given signal, each child shoots the child closest to him or her with water. Show that if $n$ is an even number, then it is possible (but not necessarily the case) that every child gets wet. Show that if $n$ is odd, then necessarily at least one child stays dry.

Commentary: My method of finite-point intersections in constructing the even case was taken from a resourceful proof I'd read of the problem, "Can the real plane be covered by countably many lines?" This was important as it was otherwise difficult to "prove the obvious" that certain area subtractions didn't annihilate the whole area. For the odd case, the key was in finding an "odd man out" in pairing (guaranteeing a sequence of length greater than two) and the aside about sequence length (disproving any sequence of length greater than two).

Proof: We shall prove the odd statement first, and then the even.

Say $a→b$ if child $a$ shoots child $b$. Assume the configuration between the $n$ children is such that there exists distinct $a,b,c$ such that $a→b→c$. Then we show necessarily at least one child stays dry. This is generally the case for odd $n$ (as otherwise the children could be paired up exactly with who they shoot, as the shot would have no one else to shoot but the shooter; formally, say $a \text{~} b$ if $a=b$ or if $a→b$. Then $\text{~}$ is checked to be naturally reflexive, and transitive and symmetric by assuming such $a,b,c$ don't exist. Hence $\text{~}$ is an equivalence relation, and we cannot have less than or more than $2$ elements in any element of the afforded partition set, hence the order of the union of the partition is even), yet it can still occur from even $n$, and together with the even statement's proof it will classify the case in which it does occur when $n$ is even.

Before continuing with the odd case, we prove that there does not exist a sequence of distinct children $p_1→...→p_m→p_1$ when $m > 2$. To wit, let $r_i$ denote the distance between child $p_i$ and $p_{i+1}$ for $1 ≤ i < m$ and let $r_m$ be the distance between $p_m$ and $p_1$. When $m > 2$ we must have $r_1 > r_2$ for $p_2$ to shoot $p_3$ rather than $p_1$, and generally we continue $r_1 > ... > r_m$ implying $r_1 > r_m$, but now $p_1$ would've shot $p_m$, a contradiction.

Return back to the distinct sequence $a→b→c$. Let $D$ be the set of all children in a sequence that eventually shoots $a$. Starting from $a$, choose another child shooting $a$ (if no child is to remain dry), choose another child shooting this child, and continue until a child $d$ reappears in the sequence (necessarily since there are a finite amount of children), hence $d→e→...→d$. But this whole sequence is contained in $D$ by induction, and also by the aside above the sequence for $d$ must simply be $d→e→d→e→...$, never in fact reaching $a$, a contradiction.

The even statement is simple enough to take on faith; simply scatter the children very far apart so that they shoot each other in pairs, and wiggle them if necessary to eliminate collinearity. More formally, construct the $2m$ case for all natural $m$ by induction. $m=0$ is vacuously true without children. Construct the $2(m+1)$ case from $2m$ as follows: Let $r$ be the maximum distance between any two children. Then select a line $l$ such that $l$ does not intersect any circles of radius $r$ drawn around the children (possible since the circles' maximum height in the plane is bounded), so in particular doesn't intersect any children. Place an extra child $x_1$ on this line such that he isn't collinear with any other children and doesn't have equal distance between any two other children (possible since the other children's collinearity lines as do the lines denoting equal distance between two other children intersect $l$ in only finitely many places, and the line has infinite points). Letting $r' > r$ be the minimum distance between $x_1$ and any other child and $s$ be the smallest distance between any two children, draw an open ball $b$ of radius $\text{min}\{r'-r,r,s\}$ around $x_1$. Let $m$ be the maximum of the slopes collected when drawing lines between $x_1$ and the children and lines denoting the points equal distance between any two children (excluding vertical lines if needed), and draw a line $l'$ of slope $m'$ intersecting $x_1$. Then those lines intersect the infinite $l'∩b$ in only finitely many places, so place $x_2$ in $l'∩b$ not on any of these lines. We have completed the task of placing $x_1$ and $x_2$ such that (1) $x_1$ shoots $x_2$, (2) $x_2$ shoots $x_1$, (3) $|x_1-c|≠|d-e|$ for all children $c,d,e$ with $d,e≠x_1$, (4) $|x_1-c|≠|x_1-d|$ for all children $d,e$, also (3) and (4) with $x_1$ replaced by $x_2$, and (7) there are no lines containing $x_1$ and two previous children, and (8) no lines containing $x_1$, $x_2$, and a previous child.

Problem 8

8. A round-robin tournament was held among 13 players. Each player played one game against every other player. Each player won six games. How many triples (K,L,M) of players are there such that K beat L, L beat M, and M beat K?

Commentary: This was probably my favorite problem out of them all, as it certainly demanded my most effort.

My first thought was that I'd already solved this problem some months ago. It concerned the determinant of Vandermonde matrices, where cancellations of terms coincided with directed graphs which have no "triangles" $a→b→c→a$. I've attached the exercise and its proof on a separate paper. But though it turned out that that research wasn't going to directly help me here, I still expected the result to pan out relatively easily.

The first model for comparison I conceived of was the graph where $1→2,3,4,5,6,7$, $2→3,4,5,6,7,8$, $...$, $13→1,2,3,4,5,6$, whose triangles can be computed through one node then copied out by symmetry. Given that the problem asked for one specific number, I figured it would result that every directed graph on $2n+1$ for nodes each yielding an arrow to $n$ other nodes was isomorphic to this one for $n=6$. However, the solution wasn't making itself readily apparent, and though defaulting to a simpler case of $n=2$ allowed me to establish isomorphism with its appropriate graph, I was able to construct an explicit counterexample for $n=3$. This was startling, because now I realized this problem wouldn't be very trivial.

I began entertaining very far-flung ideas. Representing graphs as polynomials and considering their Grobner bases was probably the craziest. One persistent idea I had that I'm still curious about, was the semi-action (not actually a group action since it fails composition) of $S_{2n+1}$ on these graphs, where for example $(1 5 8)$ flips the arrows between $1$ and $5$, $5$ and $8$, and $8$ and $1$. This preserves the number of arrows projecting from any node, so I reasoned that in this case and perhaps generally it preserved the number of triangles. It took a bit of coding to handle higher-level examples show that it was not true in the general case, but I still held out some hope for it in this problem.

I had one big success before tripping over the actual solution below, in the form of a lemma which was never required. Its details are more complicated than that of the actual solution. I've also attached it.

Proof: Let $W$ be the tournament directed graph on $2n+1$ nodes inherited by the round-robin situation between $2n+1$ players for some $n$, where $a→b$ iff $a$ beat $b$ in the tournament. For any node $b$, observe how many pairs of nodes $a,c$ exist such that $a→b→c→a$. When $a→b$ and $b→c$ are assumed to hold there is merely $c→a$ to consider, hence it suffices to find the number of arrows projecting (1) from the set of nodes toward which $b$ points (what I call the image of $b$) (2) into the set of nodes pointing toward $b$. Since by definition no such arrow can project toward $b$, this is merely condition (1) so long as they don't point back into the image of $b$. Since there are $n$ nodes in the image, each projecting $n$ arrows, there are $n^2$ such arrows minus the amount projecting inward, which is merely the amount of arrows on an $n$ tournament directed graph $n(n-1)/2$, resulting in exactly $n(n+1)/2$ arrows. Multiply this by $2n+1$ nodes to get the raw number $n(n+1)(2n+1)/2$ of triples requested, and divide by $3$ to get the distinct number of $3$-cycles $n(n+1)(2n+1)/6$. For $2n+1=13$ this is respectively $273$ and $91$.$~\square$

Problem 4

4. Find the sum of the 4536 numbers from 1,000 to 10,000 which have all their digits distinct. This is really two problems: (a) Find a solution by using brute force on the computer; (b) find a solution by doing it analytically by hand.

Commentary: The solution was easy to compute using code, and there were no surprises in trying to derive it by hand.

Proof: (a) The following code in Python produces the desired result: 24,917,760.

def distinct_digits(x):
    x = str(x)
    for k in range(len(x)):
        if x.index(x[k]) != k:
            return(False)
    return(True)

sum(filter(distinct_digits,[x for x in range(1000,10000)]))

(b) We may decompose each number with distinct digits into its base-ten form $d_0d_1d_2d_3=d_0·10^3+d_1·10^2+d_2·10^1+d_3·10^0$, and thus obtain the sum of numbers with distinct digits as the sum of sums of their digits multiplied by their proper powers of ten. To find the sum of the thousands-place digits, we may observe that combinatorially there are $9·8·7=504$ numbers with any given thousands-place digit, and for nonzero digits (the only ones that would affect the sum) in the hundreds, tens, or ones place there are $8·8·7=448$ numbers accommodating them each. Hence the sum is $$(1000+2000+...+9000)(504)+(100+200+...+900)(448)+$$ $$(10+20+...+90)(448)+(1+2+...+9)(448)=24,917,760$$

Problem 3

3. Consider the number $2^{9876543}$. Determine (a) the number of digits it has; (b) its last three (rightmost) decimal digits; and (c) its first three (leftmost) decimal digits.

Commentary: This problem's part (c) really scared me because I hadn't ever heard of how to calculate digits starting from the left in any simple fashion. I put it off for a later time and maybe some research, but before then, the thought had already passed through my mind of simply raising $10$ to the decimal part to get the digits, scientific-notation-style. But it seemed to good to be true, so I put off actually thinking about it until it was nearly the last of the remaining problems.

Proof: (a) The number $10^x$ has $\lfloor x \rfloor + 1$ digits to the left of the decimal for nonnegative $x$. So we solve $10^x=2^9876543$ by $x=9876543ln(2)/ln(10) \approx 2,973,135.696$. Hence there are $2,973,136$ digits in full.

(b) A basic exercise to calculate modulo $1000$. The most efficient way to do this by hand is to calculate the smallest $n$ such that $2^n ≤ 9876543$ (in this case $n=23$), then successively calculate the reductions $2^i$ modulo $1000$ for $0 ≤ i ≤ n$ and line them up left to right, and according to the binary representation of $9876543$ multiply and reduce modulo $1000$ each of these terms in line. The result of this effort is $208$.

(c) We have $10^x=2^{9876543}$ so in scientific notation this number is $10^d · 10^{\lfloor x \rfloor}$ where $d=x-\lfloor x \rfloor$ is the decimal part of $x$. In this case we see $10^d \approx 4.97$ so the first three digits are $497$.

Problem 7

7. Show that the expressions $2x+3y$ and $9x+5y$ are divisible by $17$ for the same set of integral values of $x$ and $y$.

Proof: This is straightforward modular arithmetic. We have $2x+3y ≡ 0 \text{mod }17 ⇔ 13(2x+3y) = 26x+39y ≡ 9x+5y ≡ 0 \text{mod }17$, since $13$ is a unit in $ℤ/17ℤ$. Generally, when $z~\not |~a,b$, we have $ax+by$ is divisible by $z$ a prime for the same integral values as $cx+dy$ iff $-a^{-1}b ≡ -c^{-1}d \text{mod }z$, and when $z~|~a$ but $z~\not |~c$ then $(1,0)$ is a value for $ax+by$ but not for $cx+dy$, similarly for $z~|~c$ but $z~\not |~a$, and when $z~|~a,b$ we have the same values when $b$ and $d$ coincide in divisibility or lack of divisibility by $z$.

Problem 5

Three positive integers $a$, $b$, and $c$ form a Pythagorean Triple if $a^2+b^2=c^2$. It is primitive if they have no common factors. For example, $3$, $4$ and $5$ form a primitive Pythagorean Triple, $5$, $12$, and $13$ form another primitive Pythagorean Triple. Find two more primitive Pythagorean Triples.

Commentary: I had already read about how the set of Pythagorean Triples may be completely classified, though I didn't quite recall it at the moment, so I decided to do this problem by figuring out my own simple method.

Proof: Observe $a^2+b^2=c^2$ implies $a^2=(c-b)(c+b)$, so when $a$ is an odd prime this means we must solve $c-b=1$ and $c+b=a^2$, namely by $c=b+1$ and $b=(a^2-1)/2$. The triples $(3,4,5)$ and $(5,12,13)$ are of this form, and we may generate $(7,24,25)$, $(11,60,61)$, $...$.$~\square$

Since $(a,b,c)$ being a triple implies $(an,bn,cn)$ is a triple for $n∈ℕ$, this implies that every positive integer with an odd prime divisor (i.e., every positive integer except powers of $2$) is part of a Pythagorean Triple. This method can be applied to demonstrate that $1$ and $2$ are not part of any Pythagorean Triple, and that $(2^n,(2^{2n-1}-2)/2,(2^{2n-1}+2)/2)$ for $n > 1$ is a nontrivial Pythagorean Triple for greater powers of $2$.

Problem 6

6. Suppose your worst enemy gives you $n$ red points and $n$ blue points in the plane, no three of them collinear. (Your enemy picked them, so they are not nicely arranged.) Show that it is possible to draw $n$ line segments, each segment joining a red point to a blue point (so that each red point is paired with a unique blue point, and vice versa) in such a way that none of the line segments intersect.

Commentary: This one was quite a labor from beginning to end. At first I put it on the back burners, because I thought it would perhaps be a simple case of induction or intuitive resolution. However, I quickly became lost in my clear conception of why it would hold, and I didn't even want to think about how I'd go about explaining even semi-formally a solution.

I tried to get at it by simple induction for a really long time, trying to force the minimal $n$ counterexample to be as unlikely as possible. I did eventually settle on something; casually explained, if you take a ruler and pull it up from a region of the plane below all of the points and let it catch on a lowest point, then drag it clockwise until it catches another, and so forth until arriving at the original point, it can be reasoned that all of these points caught are of the same color, otherwise one could draw a line between two of these border points and finish the other $n-1$ points by induction without worrying about it interfering with the first line drawn. Essentially, this would mean all the points are trapped in a polygon defined by certain points of the same color.

This result would ultimately pan out to be useless, because of where it guided me: I ended up realizing a situation that implied it might very well be that "naive" induction (a proof of the form, "locate a certain pair of points, draw a line, and finish the rest by induction" as applied above) isn't enough to resolve the problem. This was because of the existence of the diagram below, where every possible green line might be intersected by another green line drawn:

(It being so sloppy because I only realized the significant proportions are those of "shrunken center pentagon" after having drawn it all out)

Long story short I had to make a fresh start. After some more contemplation, later that night I had a sleepy thought that "crosses represent inefficiencies in segment lengths," and after entertaining it for some while I settled on the solution below.

Proof: Lemma: In a quadrilateral where the diagonals intersect, the sum length of these two diagonals exceed the sum length of any two opposite sides. Proof:

When $E$ represents the intersection, it results from basic linear algebra $|u+v| < |u|+|v|$ (when $u$ and $v$ are nonassociate to each other as here) implying $$|\overline{AC}|+|\overline{BD}|=|\overline{AE}|+|\overline{EC}|+|\overline{BE}|+|\overline{ED}| > |\overline{AB}|+|\overline{CD}|$$ and similarly for the the other pair of sides.$~\square$

For each possible graph $P$ of line pairings that can be drawn (not necessarily without intersections), let $N(P)$ be the sum of the lengths of every line segment in $P$. Since there are a finite number $n!$ of such graphs, let $L$ be minimal with regard to this norm. Then $L$ has no intersections; otherwise assume $\overline{AB}$ and $\overline{CD}$ intersect. Then let $L'$ be the graph with every other line segment the same as in $L$, but with instead the segments $\overline{AD}$ and $\overline{CB}$. By the lemma applied to the quadrilateral $ADCB$, we thus see $N(L') < N(L)$, violating the minimality of $L$.$~\square$

Since there are only a finite number of graphs, this provides a constructive method of obtaining a nonintersecting line pairing by taking any random graph and successively decreasing its norm until no intersections may remain.

Problem 2

2. Does there exist an infinite collection of sets such that the intersection of every two distinct sets in the collection is nonempty, but the intersection of every three distinct sets in the collection is empty?

Proof: The answer is yes; the concept behind constructing a counterexample is in adducing an infinite collection of sets such that the intersection of any two distinct sets results in a singleton set whose element is independently identifiable as belonging to precisely those two sets.

For all $i∈ℕ^+$ comprehend from $\mathcal P(ℕ)$ the set $A_i=\{\{i,j\}~|~j∈ℕ\}$. For distinct $i,j$ we see $A_i∩A_j = \{\{i,j\}\}$ yet this $\{i,j\}∉A_k$ for any third distinct $k$.

Problem 1

1. Do there exist irrational numbers $r,s$ such that $r^s$ is rational? Do there exist irrational numbers $r,s$ such that $r^s$ is irrational?

Really, Wikipedia ruined this problem for me in advance, or at least part a. The answer to both these problems is yes.

Proof: (a) The easiest methods are nonconstructive; observe $α=\sqrt{2}^\sqrt{2}$. Either $α$ is rational, in which the proposition is established, or $α$ is irrational. If $α$ is irrational, then $α^\sqrt{2}=\sqrt{2}^(\sqrt{2}·\sqrt{2})=\sqrt{2}^2=2$ is a pair of irrationals $α,\sqrt{2}$ establishing the proposition.

(b) My method for this too is nonconstructive; assume the proposition is false. Then observe the map $\sqrt{2}^\_ : ℝ \setminus ℚ → ℚ$. Since the union of two countable sets would then be countable, and since $ℝ$ is uncountable, we have $ℝ \setminus ℚ$ is uncountable. Therefore this map is not injective and we have $\sqrt{2}^r=\sqrt{2}^{r'}$ for some distinct irrationals $r,r'$. But exponentiation is naturally injective, so we observe a contradiction.