## MSLC Semina — Exploring Knights Tours

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.

## Math Club Number Theory Training Session

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 1If we write for the statement “ divides .”

Formally, means for .

Question 2What is the largest such that is divisible by ? Idea: Find a factorization where is a small constant.

Fact 3The “divisors” of are all such that . We say is “prime” if its divisors are . We say that is “composite” if it is not prime.

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

Question 5Show that is irrational. Generalize!

Question 6Show that there are infinitely many primes. Euclid’s idea: Suppose there are finitely many and consider .

Question 7Show that there are arbitrarily large gaps between primes. That is, show that for any there are consecutive numbers which are all composite.

Question 8 (Germany 1995)Consider the sequence and . Show that this sequence contains infinitely many composite numbers.

**3. Congruence **

Fact 9 (The Division Algorithm)For any there is a unique pair such that and .

Fact 10We write if . For any there is \mbox{} such that . We say that “ is congruent to modulo ”. Congruence preserves the usual rules of arithmetic regarding addition and multiplication.

Question 11Suppose that has digits in decimal notation.

- Show that .
- Show that .
- Show that .
- Show that .

Question 12What are the last two digits of ?

Question 13Show that any perfect square is congruent to or . Conclude that no element of is a perfect square.

Question 14Show that 3 never divides .

**4. The Euclidean Algorithm **

Fact 15The “greatest common divisor” of and is:

Question 16Show that where and is the unique pair of numbers given by the division algorithm.

Question 17The Fibonacci numbers are defined so that , and for . Show that .

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 then the Euclidean algorithm takes at most steps to calculate . Check out this great write-up at Cut the Knot.

** 4.1. Parity **

Question 18Suppose that is odd and is a permutation. Show that the number

must be even.

Question 19A room starts empty. Every minute, either one person enters or two people leave. Can the room contain people after minutes?

Idea: Consider the “mod-3 parity” of room population.

**5. Contest Problems **

Question 20Show that is not an integer for any .

Idea: Consider the largest power . 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. . Prove that less than a tenth of them can be expressed in the form where , , and are positive integers.

Idea: None of , , or can be very big. For example, .

Question 22 (Rochester 2003)An -digit number is “-transposable” if and . For example, is -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 .

Find a number with a repeating decimal of length six.

Question 23Suppose that you write the numbers on the blackboard. You now proceed as follows: pick two numbers and , erase them from the board, and replace them with . Continue until there is a single number left. Does this number depend on the choices you made?

## Basic Combinatorics.

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: , . We also use set constructor notation where is some statement about that can be true or false. For example: , . We write: , for the set of natural numbers, for the set of rational numbers, for the set of integers.

We write to mean that is in the set . We write . We write . We write for if . If then we say that and are disjoint sets.

We write for the set of ordered pairs of elements.

Definition 1A function isinjective (one to one)if: implies . A function issurjective (onto)if: for all there is such that . A function isbijectiveif: for all there is such that . The number of elements in a set is written .

** 1.2. Basic formulae **

The basic facts of combinatorics are very simple.

- If then there is no injective function from a set with elements to a set with elements. (This is called pigeon hole principle.)
- If there is a bijective function from to then .
- If and are disjoint then .
- If and are disjoint then .
- .
- The number of element subsets of a set with elements is: . (Why is this an integer? Prove it.)
- The number of functions from an -element set to a element set is .
- If then the number of bijective functions from to (permutations of ) is .

There are a couple formulae that are handy to remember:

- There are subset of .
- Suppose you have objects of types 1, 2, , respectively. The number of ways of arranging all the objects is:
- Suppose you have identical objects that you want to distribute among containers. The number of ways to do this is: . (Why?)

## 2014 Mentoring

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.

## Questions about Discs

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.

## A Bijection

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

Exercise 1Show that is a bijective map .

## Group Theory Problems

Mike Pawliuk and I got talking about elementary group theory problems today. I wanted to record one of my favourites. I heard this one from Lucy Kadets, who heard it from Yuri Burda. I’m not sure if he is the original author or not.

Let denote the symmetric group on elements. We say is *a point-fixing subgroup* if there is a such that for all . We say *has fixed points* if for each there is such that .

Exercise 1Is every that has fixed points a point-fixing subgroup?

## Polynomials

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

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

*Hint*: Look at and .

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

## Induction for Fields Circle

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

## An Original Colouring Puzzle

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?

leave a comment