Consider an \(n\)-dimensional simplex \(\mathcal{A} = A_1A_2...A_{n+1}\), namely a body spanned over vertices \((0,0,...,0), (1,0,0,...,0), (0,1,0,0...,0), ... (0,0,...0,1)\). \[\mathcal{A} = \{\sum_{i=0}^{n}a_i(0,0,...,1,...,0), \,\,\, a_i \geq 0, \,\,\,\, \sum_{i=1}^{n+1}a_i = 1\}.\] Where next to \(a_i\) there is a point with coordinate where \(1\) is in \(i\)-th place. The point \((0,0,...,0)\) belongs to the simplex as well.
A simplicial subdivision of an \(n\)-dimensional simplex \(\mathcal{A}\) is a partition of \(\mathcal{A}\) into small simplices (cells)
of the same dimension, such that any two cells are either disjoint, or
they share a full face of a certain dimension.
Define a Sperner’s coloring of a simplicial subdivision as an assignment
of \(n+1\) colors to the vertices of
the subdivision, so that the vertices of \(\mathcal{A}\) receive all different colors,
and points on each face of \(\mathcal{A}\) use only the colors of the
vertices defining the respective face of \(\mathcal{A}\).
Consider a simplicial subdivision given by pairwise connected middles of
all the segments in the original simplex. Assign the numbers \(0,1,2...,n\) to the subdivision vertices in
such a way as to conduct a Sperner’s coloring in such a way that you
will have only one rainbow simplex.
Consider an equilateral triangle \(ABC\). Parallel to each side, five equally spaced segments are drawn across the triangle so that \(ABC\) is subdivided into \(36\) smaller equilateral triangles. Vertices \(A,B\) and \(C\) are painted red, blue and green, respectively in counterclockwise order. Alice and Bob take turns painting each vertex of the smaller triangles either red, green, or blue with the following restrictions: the segment \(AB\) can only have red or green, the segment \(BC\) can only have green and blue, and the segment \(AC\) can only have blue and red. The interior vertices can be drawn freely. Once all vertices have been painted, Alice gets a point for every smaller triangle whose vertices have the three colors (red, green, and blue) appearing in the counterclockwise direction. Bob gets a point for every smaller triangle whose vertices have the three colors but in the clockwise direction. Who wins?
An equation of the form \(x^2 - dy^2 = 1\) where \(d>0\) is a nonsquare (what if \(d\) is a square?) integer and we seek \(x,y\) in the integers is called Pell’s equation. By changing the sign of \(x\) and \(y\), we may assume they are nonnegative. There is always the solution \((x,y)=(1,0)\) which we call trivial.
Here is a useful way to think about the solutions to Pell’s equations. The difference of squares identity prompts us to consider the solution \((x,y)\) to Pell’s equation as the real number \(x+y\sqrt{d}\). The fact that \((x,y)\) is a solution simply means \((x+y\sqrt{d})(x-y\sqrt{d})=1\).
Here is some common notation you might see if you look at books or on the internet: if we have a number \(u=x+y\sqrt{d}\), we can define its conjugate as the number \(\bar u=x-y\sqrt{d}\). Moreover, the set of numbers of the form \(x+y\sqrt{d}\) where \(x,y\) are whole numbers, is often written as \(\mathbb Z[\sqrt{d}]\) (pronounced “integers adjoint \(\sqrt{d}\)"). Therefore, a number \(u\) that belongs to \(\mathbb Z[\sqrt{d}]\) is a solution to Pell’s equation if \(u\bar u=1\).
As with all Diophantine equations, we would like to to know the following about Pell’s equation.
Does Pell’s equation always have nontrivial solutions?
When Pell’s equation does have solutions, is the number of solutions finite?
How can we describe all solutions to Pell’s equation?
In this sheet, we answer all of the questions above and apply these theoretical results to some other problems.
There are \(100\) people in a room, and each person has at least one friend in the room. Prove that amongst them there are two people with the same number of friends in the room (we don’t count being friends with oneself).
Suppose that \((x_1,y_1),(x_2,y_2)\) are solutions to Pell’s equation \(x^2-dy^2 = 1\). Show that \((x_1x_2+dy_1y_2,x_1y_2+x_2y_2)\) also satisfies the same equation.
Suppose that \(x+y\sqrt{d}>1\) gives a solution to Pell’s equation. Show that \(x\geq 2\) and \(y\geq 1\). Can the bounds be achieved?
Can we obtain the polynomial \(h(x)=x\) by adding, subtracting, or multiplying the polynomials \(f(x)=x^2+x\) and \(g(x)=x^2+2\)?
The topic of this problem sheet will be polynomials. Before we dive into the examples, let’s recap a few key concepts.
A polynomial in \(x\) is an expression formed by adding or subtracting monomials, which are terms of the form \(a x^n\), where \(a\) is a number called a coefficient, and \(n\) is a whole number (non-negative integer). Here, \(x\) is a variable that may represent a number.
We can perform several familiar operations on polynomials, which you may have seen before:
Addition and subtraction: We add or subtract polynomials by looking at each power of \(x\) and adding or subtracting the corresponding coefficients. For example, if \[f(x) = x^4 + 3x - 1 \quad \text{and} \quad g(x) = x^3 + 2x + 5,\] then \[f(x) - g(x) = x^4 - x^3 + x - 6.\]
Multiplication: We use the distributive property, which means that every term in the first polynomial is multiplied by every term in the second polynomial. For example, if \[f(x) = x^2 + x + 1 \quad \text{and} \quad g(x) = x - 1,\] then \[f(x) g(x) = (x^2 + x + 1)(x - 1) = x^3 + x^2 + x - x^2 - x - 1 = x^3 - 1.\]
Let’s now present the examples. They have some very important techniques, so read them carefully before attempting the problems.
In this example we will discuss division with remainder. For polynomials \(f(x)\) and \(g(x)\) with \(\deg(f)\geq \deg(g)\) there always exists polynomials \(q(x)\) and \(r(x)\) such that \[f(x)=q(x)g(x)+r(x)\] and \(\deg(r)<\deg(g)\) or \(r(x)=0\). This should look very much like usual division of numbers, and just like in that case, we call \(f(x)\) the dividend, \(g(x)\) the divisor, \(q(x)\) the quotient, and \(r(x)\) the remainder. If \(r(x)=0\), we say that \(g(x)\) divides \(f(x)\), and we may write \(g(x)\mid f(x)\). Let \(f(x)=x^7-1\) and \(g(x)=x^3+x+1\). Is \(f(x)\) divisible by \(g(x)\)?
In this example we discuss the Factor Theorem. First, let us recall the following concept: if \(P(x)\) is a polynomial, then a number \(z\), is a root of \(P(x)\) if \(P(z)=0\). For example, \(x=1\) is a root of the polynomial \(Q(x)=x-1\). Show:
If \(0\) is a root of \(P(x)\), i.e: \(P(0)=0\), then \(P(x)=xQ(x)\) for some polynomial \(Q(x)\).
Use part 1 to show the Factor Theorem: if \(z\) is a root of \(P(x)\), then \(P(x)=(x-z)K(x)\) for some polynomial \(K(x)\).