problems | Parker Glynn-Adey

MSLC Semina — Exploring Knights Tours

Posted in Math by pgadey on 2019/10/24

20191021_144922

At the MSLC Seminar we had an “improvisational seminar” this week. We started off chit-chatting about various problems, and a theme emerged. One participant posed the following problem:

The game of Knight Placement is played on an 8×8 chessboard. Two players alternately take turns placing knights on the board. A move consists of adding a knight to the board, such that no knight is under attack. A player loses if they’re unable to place a knight. Who wins under optimal play?

I followed this question up with:

Suppose that the Queen of Chess has a garrison of twenty-five knights. The knights are kept on a 5×5 chessboard. One fine morning, the Queen shows up and orders the knights to all switch places, or be severely punished. Can every knight switch places simultaneously?

This got us thinking about knights tours. In a knight’s tour, a knight travels to every cell of a chessboard by visiting each square exactly once. Notice that if the 5×5 board has a knight’s tour, then the garrison can re-arrange themselves by each stepping along the tour.

We found a couple small boards with and without closed knight’s tours. Wikipedia turned our attention to this paper:

Allen J. Schwenk (1991). “Which Rectangular Chessboards Have a Knight’s Tour?” Mathematics Magazine: 325–332. (link)

Working through that paper might make a good session at MSLC Seminar. If anyone knows the history / providence of the puzzles above, I would be hear about them.

Tagged with: chess, games, mslc, problems, puzzle, seminar

leave a comment

Math Club Number Theory Training Session

Posted in Lecture Notes, Math by pgadey on 2019/01/31

These are some questions that I prepared for Math Club. The problems follow Paul Zeitz’s excellent book The Art and Craft of Problem Solving. You can find this hand-out is here:
https://pgadey.ca/teaching/2019-math-club/number-theory-training-talk/number-theory-training-talk.pdf (tex)

1. Advice and Suggestions

Try out lots of examples.
The small numbers are your friends.

2. Facts and Questions

Fact 1 If ${a, b \in \mathbb{Z}}$ we write ${a | b}$ for the statement “ ${a}$ divides ${b}$ .”
Formally, ${a|b}$ means ${b = ka}$ for ${k \in \mathbb{Z}}$ .

Question 2 What is the largest ${n}$ such that ${n^3 + 100}$ is divisible by ${n+10}$ ? Idea: Find a factorization ${n^3+100 = (n+10)( ... ) \pm C}$ where ${C}$ is a small constant.

Fact 3 The “divisors” of ${k}$ are all ${d}$ such that ${d | k}$ . We say ${p}$ is “prime” if its divisors are ${\{1, p\}}$ . We say that ${k}$ is “composite” if it is not prime.

Fact 4 (Fundamental Theorem of Arithmetic) Any natural number ${n}$ is a product of a unique list of primes.

Question 5 Show that ${\sqrt{2}}$ is irrational. Generalize!

Question 6 Show that there are infinitely many primes. Euclid’s idea: Suppose there are finitely many ${\{ p_1, p_2, \dots, p_n\}}$ and consider ${N = p_1 p_2 \dots p_k + 1}$ .

Question 7 Show that there are arbitrarily large gaps between primes. That is, show that for any ${k}$ there are ${k}$ consecutive numbers ${n, n+1, \dots, n+k}$ which are all composite.

Question 8 (Germany 1995) Consider the sequence ${x_0 = 1}$ and ${x_{n+1} = ax_n + b}$ . Show that this sequence contains infinitely many composite numbers.

3. Congruence

Fact 9 (The Division Algorithm) For any ${a, b \in \mathbb{N}}$ there is a unique pair ${(k,r)}$ such that ${b = ka + r}$ and ${0 \leq r < a}$ .

Fact 10 We write ${a \equiv b \mod n}$ if ${n | (a-b)}$ . For any ${a \in \mathbb{Z}}$ there is \mbox{ ${r \in \{0, 1, \dots, n-1\}}$ } such that ${a \equiv r \mod n}$ . We say that “ ${a}$ is congruent to ${r}$ modulo ${n}$ ”. Congruence preserves the usual rules of arithmetic regarding addition and multiplication.

Question 11 Suppose that ${n}$ has digits ${n = [d_1 \dots d_k]}$ in decimal notation.

Show that ${n \equiv d_1 + d_2 + \dots + d_k \mod 9}$ .
Show that ${n \equiv d_k \mod 10}$ .
Show that ${n \equiv \sum_{k=0}^n (-1)^k d_k \mod 11}$ .
Show that ${n \equiv [d_{k-1}d_k] \mod 100}$ .

Question 12 What are the last two digits of ${7^{40001}}$ ?

Question 13 Show that any perfect square ${n^2}$ is congruent to ${0}$ or ${1 \mod 4}$ . Conclude that no element of ${\{11, 111, 1111, \dots\}}$ is a perfect square.

Question 14 Show that 3 never divides ${n^2 + 1}$ .

4. The Euclidean Algorithm

Fact 15 The “greatest common divisor” of ${a}$ and ${b}$ is:

$\displaystyle \gcd(a,b) = \max\{ d : d|a \textrm{ and } d|b \}$

Question 16 Show that ${\gcd(a,b) = \gcd(a,r)}$ where ${b = ak + r}$ and ${(k,r)}$ is the unique pair of numbers given by the division algorithm.

Question 17 The Fibonacci numbers are defined so that ${F(1) = 1, F(2) = 1}$ , and ${F(n) = F(n-1) + F(n-2)}$ for ${n>2}$ . Show that ${\gcd(F_n, F_{n-1}) = 1}$ .

The Fibonacci numbers have the following curious property: Consecutive Fibonacci numbers are the worst-case scenario for the Euclidean Algorithm. In 1844, Gabriel Lamé showed: If ${a \leq b \leq F_n}$ then the Euclidean algorithm takes at most ${n}$ steps to calculate ${\gcd(a,b)}$ . Check out this great write-up at Cut the Knot.

4.1. Parity

Question 18 Suppose that ${n = 2k + 1}$ is odd and ${f : \{1, 2, \dots, n\} \rightarrow \{1, 2, \dots, n\}}$ is a permutation. Show that the number

$\displaystyle (1 - f(1))(2 - f(2)) \dots (n - f(n))$

must be even.

Question 19 A room starts empty. Every minute, either one person enters or two people leave. Can the room contain ${2401}$ people after ${3000}$ minutes?
Idea: Consider the “mod-3 parity” of room population.

5. Contest Problems

Question 20 Show that $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ is not an integer for any ${n > 1}$ .

Idea: Consider the largest power ${2^k < n}$ . Divide out by this largest power. This will make all of the denominators odd. (In fancy number theory terms, you’re using a 2-adic valuation.)

Question 21 (Rochester 2012) Consider the positive integers less than or equal to one trillion, i.e. ${1 \leq n \leq 10^{12}}$ . Prove that less than a tenth of them can be expressed in the form ${x^3 + y^3 + z^4}$ where ${x}$ , ${y}$ , and ${z}$ are positive integers.

Idea: None of ${x}$ , ${y}$ , or ${z}$ can be very big. For example, ${x < \sqrt[3]{10^{12}} = 10^4}$ .

Question 22 (Rochester 2003) An ${n}$ -digit number is “ ${k}$ -transposable” if ${N = [d_1 d_2 \dots d_n]}$ and ${kN = [d_2 d_3 \dots d_n d_1]}$ . For example, ${3 \times 142857 = 428571}$ is ${3}$ -transposable. Show that there are two 6-digit numbers which are 3-transposable and find them.

\noindent Big Idea: Consider repeating decimal expansions.
Observe that ${10 \times 0.[d_1 d_2 d_3 \dots] = d_1 . [d_2 d_3 d_4 \dots]}$ .
Find a number with a repeating decimal of length six.

Question 23 Suppose that you write the numbers ${\{1, 2, \dots, 100\}}$ on the blackboard. You now proceed as follows: pick two numbers ${x}$ and ${y}$ , erase them from the board, and replace them with ${xy + x + y}$ . Continue until there is a single number left. Does this number depend on the choices you made?

Tagged with: contest math, problems

leave a comment

Basic Combinatorics.

Posted in Uncategorized by pgadey on 2014/07/27

First we recall a little bit of terminology:

1.1. Sets and functions

A set is a collection of elements . We write a set by surrounding its list elements with curly braces. For example: ${X = \{1,2,3\}}$ , ${Y = \{\heartsuit, \clubsuit, \star\}}$ . We also use set constructor notation ${Y = \{x : P(x)\}}$ where ${P(x)}$ is some statement about ${x}$ that can be true or false. For example: ${X = \{n : n\text{ is even}\}}$ , ${Z = \{n : n\text{ is prime}\}}$ . We write: ${\{\} = \emptyset}$ , ${{\mathbb N}}$ for the set of natural numbers, ${{\mathbb Q}}$ for the set of rational numbers, ${{\mathbb Z}}$ for the set of integers.

We write ${x \in X}$ to mean that ${x}$ is in the set ${X}$ . We write ${X \cup Y = \{x : x \in X \text{ or } x \in Y\}}$ . We write ${X \cap Y = \{x : x \in X \text{ and } x \in Y\}}$ . We write ${X \sqcup Y}$ for ${X \cup Y}$ if ${X \cap Y = \emptyset}$ . If ${X \cap Y = \emptyset}$ then we say that ${X}$ and ${Y}$ are disjoint sets.

We write ${X \times Y = \{(x,y) : x \in X,\ y \in Y\}}$ for the set of ordered pairs of elements.

Definition 1 A function ${f : X \rightarrow Y}$ is injective (one to one) if: ${x \neq y}$ implies ${f(x) \neq f(y)}$ . A function is surjective (onto) if: for all ${y \in Y}$ there is ${x \in X}$ such that ${f(x) = y}$ . A function is bijective if: for all ${y \in Y}$ there is ${x \in X}$ such that ${f(x) = y}$ . The number of elements in a set ${X}$ is written ${|X|}$ .

1.2. Basic formulae

The basic facts of combinatorics are very simple.

If ${k < n}$ then there is no injective function from a set with ${n}$ elements to a set with ${k}$ elements. (This is called pigeon hole principle.)
If there is a bijective function from ${X}$ to ${Y}$ then ${|X| = |Y|}$ .
If ${X}$ and ${Y}$ are disjoint then ${|X \cup Y| = |X| + |Y| - |X \cap Y|}$ .
If ${X}$ and ${Y}$ are disjoint then ${|X \sqcup Y| = |X| + |Y|}$ .
${|X \times Y| = |X| \cdot |Y|}$ .
The number of ${k}$ element subsets of a set with ${n}$ elements is: ${\binom{n}{k} = \frac{ n! }{ (n-k)! k! }}$ . (Why is this an integer? Prove it.)
The number of functions from an ${n}$ -element set to a ${k}$ element set is ${k^n}$ .
If ${|X| = n}$ then the number of bijective functions from ${X}$ to ${X}$ (permutations of ${X}$ ) is ${n!}$ .

There are a couple formulae that are handy to remember:

There are ${2^n}$ subset of ${\{1, \dots, n\}}$ .
Suppose you have ${n_1, \dots, n_k}$ objects of types 1, 2, ${\dots}$ , ${k}$ respectively. The number of ways of arranging all the objects is: ${{ (n_1 + \dots + n_k)! }/{ n_1! n_2! \dots n_k! }}$
Suppose you have ${n}$ identical objects that you want to distribute among ${k}$ containers. The number of ways to do this is: ${\binom{n+k-1}{k-1}}$ . (Why?)

Tagged with: CMC2014, geometry, math, problems

leave a comment

2014 Mentoring

Posted in Math by pgadey on 2014/02/08

I’ve added a page about the mentoring project that I’m working on with three Gr. 12 students this semester. I’ll be updating the page as we go. For more information see Mentoring — 2014. From the introductory remarks:

The plan for the semester is an ambitious one. We’re going to understand the structure of all the regular convex polytopes in all dimensions, and build up a intuition for dimensions greater than three. We’ll spend most of our time learning the tools we need to understand how a geometric object can be pieced together. These tools will include vectors, metric spaces, symmetry groups, and simplicial complexes. I’m taking a very broad view of what constitutes a tool and counts as information about a space. The final result of the project will be a poster presentation about the solids and some 3-dimensional “nets” of the 4-dimemsional solids (the simplex, cube, cross-polytope, and 24-cell).

I can’t resist saying things about hyperbolic geometry. Therefore, if we get to the end of the proposed project, we’ll take a stab at using out high brow high dimensional intuition to understand the Gieseking manifold. There is more than enough stuff to say about the platonic solids, so we’ll see how far we get.

Tagged with: math, mentoring, outreach, problems

leave a comment

Questions about Discs

Posted in Math by pgadey on 2013/07/20

Over the past couple weeks I’ve been asked a lot of questions about discs in Euclidean space. In this post we’ll be putting pennies on a table, refining covers of discs, and trying to cram lots of balls into high dimensional balls. Some open questions about putting pennies on tables occur below.

(more…)

Tagged with: games, geometry, math, problems

leave a comment

A Bijection

Posted in Math by pgadey on 2013/03/30

While grading an assignment on cardinality, I ran into the answer to the following problem:

Exercise 1 Show that ${f(n) = \sum_{k=0}^n (-1)^{k+1} k}$ is a bijective map ${{\mathbb N} \cup \{0\} \rightarrow {\mathbb Z}}$ .

Tagged with: math, number theory, problems

leave a comment

Polynomials

Posted in Math by pgadey on 2013/03/01

Brandon Hanson told me the following elementary number theory problems last night.

Exercise 1 Every non-constant polynomial takes on a composite value.

Hint: Look at ${f(x) = p}$ and ${f(kp + x)}$ .

Exercise 2 If a non-constant polynomial takes on infinitely many prime values then it is irreducible.

Tagged with: math, number theory, polynomials, problems

1 comment

Induction for Fields Circle

Posted in Math by pgadey on 2013/03/01

Below the cut are some induction related questions I collected together for a Math Circle at the Fields Institute.

(more…)

Tagged with: math, problems

leave a comment

An Original Colouring Puzzle

Posted in Uncategorized by pgadey on 2013/03/01

Is it possible to colour the naturals greater than one using two colours, red and blue, such that: the product of two red numbers is blue, and the product of two blue numbers is red?

Tagged with: problems

2 comments

Older Posts »

Parker Glynn-Adey

MSLC Semina — Exploring Knights Tours

Math Club Number Theory Training Session

Basic Combinatorics.

2014 Mentoring

Questions about Discs

A Bijection

Polynomials

Induction for Fields Circle

An Original Colouring Puzzle

Pages

Categories

Tags

Meta