Category: Puzzles

Two Chess Geometries

Two chess variants, played on the chess board.

I can’t lay claim to the first, but I’m pretty sure that the second is my own creation – I certainly came up with it myself, but I don’t know if anyone else has thought of it in this form before. There is mention of something similarly-inspired on the Chess Variants Pages, but the game is very different to mine, and you need special equipment!

These variants both use the same board and pieces as regular chess. The movement and capture rules are the same as chess. The difference lies in the geometry of the board, where we make edge identifications to alter the space the game is played on. The first variant is called Cylindrical Chess, the second is Möbius Chess.

Continue reading

Complete Word Tours

Suppose we were to take a finite alphabet \mathbb{A}_n of n letters, say \{ 0, 1, \ldots, n-1\}, and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:

\{00, 01, \ldots, 0(n-1), 10, 11, \ldots, (n-1)(n-1)\}

and there are n^2 many of these. Let’s denote the set of length-m words using the alphabet \mathbb{A}_n by \mathbb{W}^m_n.

What I am interested in now is “For a given n and m, what is the minimum length string of letters I can write down and still be sure that every word in \mathbb{W}^m_n appears somewhere in it as a substring?”. Why might I be interested in such a thing? Because I really should be working on my PhD, that’s why.

Example:

01100

contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of \mathbb{W}^2_2 appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,

0011101000

and

0201221100

are examples of optimal tours through \mathbb{W}^3_2 and \mathbb{W}^2_3 respectively, as they both have this property that each letter added after the first m adds a previously unseen word.

Notice I’ve introduced the terminology tour for any string \tau that contains all words in a given \mathbb{W}^m_n, with optimal tour being the tour \tau^m_n that is of minimum possible length for that m and n.

Continue reading

Sum-Product Cycles of Positive Integers Pt. 3

To recap, we are attempting to find general solutions to the system of n coupled Diophantine equations with the form:

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1 .

We have already found that a solution is either compound (the concatenation of two shorter solutions), or it is simple (no consecutive subset is a solution to any shorter cycle). We have a canonical simple cycle, which for any pair (i, j) is the (i - 1)(j - 1)-cycle given by

[(i, j)]_{Can} = [(i, j), (1, i+j), (1, i+j+1), \ldots, (1, ij-1)]

As we shall see in this third (and final) post, the canonical cycle is very significant in the classification of simple solutions, and hence of all solutions.

Continue reading

Sum-Product Cycles of Positive Integers Pt. 2

Recall the sum-product n-cycle that we examined in this post. We seek simultaneous solutions to the coupled system of n Diophantine equations

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1.

We found some particular instances of complete descriptions of B_n, the set of equivalence classes of solutions (equivalence under commutation of the operations or of cyclic permutation of the indices i = 1, 2, \ldots, n). Now we seek a more powerful machinery with which to find and classify solutions.

Continue reading

Sum-Product Cycles of Positive Integers

Introduction

So in this post I’m going to talk a bit about a nice little number-theoretic problem that has been rattling around in my head a bit over the last few weeks. I’m essentially looking at the solutions (for each integer n) to a system of n coupled second-order Diophantine equations. The equations involved have a nice internal symmetry and I have a couple of theorems giving a complete classification of the solutions for each n – at least for positive integer solutions.

Let’s look at the prototypical equation we want to generalise:

a + b = ab \qquad a, b \in \mathbb{Z}^+.

Clearly the only viable solution to this is setting (a, b) = (2, 2) – it’s a very strong condition for two natural numbers to satisfy. However, it is a very aesthetically pleasing equation, so we would like to consider some extensions, and indeed a couple present themselves immediately.

One possible extension, which I am not going to consider here, is to find n-tuples of positive integers (x_1, x_2, \ldots, x_n) which satisfy

\sum_{i = 1}^n x_i = \prod_{i = 1}^n x_i.

((We observe immediately that the n-tuple (1, 1, \ldots, 1, 2, n) always works – but can you find how to generalise this to other n-tuples? What about those guaranteed to contain a certain subset of positive integers \{x_i, x_j, \ldots, x_k\}? What about finding the number of unique solutions for each n? You can read more about this in [1].))

The extension I will be looking at is the following: consider n many Diophantine equations of the form

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1.

Does such a system of equations always have a solution? How many solutions are there for a given n? What structure exists on the set of solutions? Clearly the solutions themselves are invariant under pair commutation ((x_i, y_i) \mapsto (y_i, x_i)) and under cyclic permutation of the indices (i \mapsto i + k (\mathrm{mod})_n). This kind of structure – where we have both an overall permutation of blocks and an underlying, independent permutation within each block – is realisable as the action of a wreath product on our space of objects. Let’s formalise this.

Definition 1

Let the n many coupled Diophantine equations of the above form be called the sum-product n-cycle, or just the n-cycle. Let A_n denote the set of n-tuples of pairs of positive integers which satisfy the n-cycle. That is,

A_n \subseteq ((\mathbb{Z}^+)^2)^n.

Let \Omega = S_2 \wr \mathbb{Z}_n denote the regular wreath product of S_n, the permutation group of two elements, and \mathbb{Z}_n, the group of integers modulo n. Furthermore let elements of \Omega act upon A_n with the primitive wreath action. We take the quotient space by this action,

B_n = A_n / \Omega,

to be our space of n-cycle solutions.

And let’s immediately disregard this formalism for the time being. We need to focus first on coming to grips with what an n-cycle is, and how it’s solved. Let’s look at some small-n solutions. Continue reading

Homotopy Groups? We don’t need no stinking Homotopy Groups! (at least if we want to prove Brouwer’s Fixed point theorem)

One of the things that annoyed me while I was doing honours in economics, Brouwer’s Fixed Point Theorem was used in several proofs, but never proven (except in one-dimension, where it’s almost trivial). It was used in the proof of theorems such as Nash’s Equilibrium Theorem, when in reality the existence of a fixed point was the most non-intuitive component of the proof (actually I’ve heard folktales that Nash’s Equilibrium Theorem is actually equivalent to Brouwer’s Fixed Point Theorem, which, if true, would make me more annoyed). However, this is understandable, as the standard proof of this theorem uses homotopy groups, the introduction of which fails almost any cost benefit analysis for a lecturer trying to teach economics (although, they do have some truly awesome applications to Game Theory – the study of which is fairly high on my “to learn” list). However I recently found a very easy proof, that uses Sperner’s Lemma. It should be accessible to anyone who has some basic analysis, and at least an intuitive understanding of graph theory. In fact I’ve also written up the proof as a problem set, designed to let people prove the result “quasi-independently”. I’ve posted it on my website at https://sites.google.com/site/matthewphillipcalvin/writing.

I first saw this idea on a blog post of Vadim Kulikov’s blog post http://blogs.helsinki.fi/kulikov/2010/02/03/brouwers-fixed-point-theorem-many-in-one-post/. I also used some notes written by Jonathan Huang at http://www.stanford.edu/~jhuang11/research/old/sperner.pdf.

Philosophic and Diadatic Musing

Warning: There is a lot of discussion here before I actually get to any maths. If you want to skip ahead to the Handshake Lemma you won’t miss anything relevant to the proof (this was intended to be a short introduction, but it rather ballooned out of proportion).

Some years ago I read “The Strange Case of Mrs. Hudson’s Cat” by Colin Bruce. The premise of the book is that Sherlock Holmes, still in Victorian (or Edwardian) Britain is presented with several cases that involve, in some way or another, principles based on modern physics, most of which make interesting cases in and of themselves, and all of which make principles of modern physics seem intuitive (when thought about the right way). One case involves a man being shot twice in quick succession. At the time he happens to be embracing a woman. At the first shot the  woman notices the impact of the shot and then hears the shot, seconds late the woman hears the second shot then feels the impact. The question is how is this possible (the same gun was used both times). This simple puzzle sets the scene for a discussion of the wave-particle duality in light and an introduction to relativity. It’s a fantastic book, and one I think about a surprising amount. (In case this plug hasn’t been clear enough, I’d recommend reading the book see links here or here, or, you know, get it out the library).

Anyway the reason I brought up this book, is that there’s a particular example that’s stayed with me. In one of the cases Sherlock and Watson are presented with two (minor) problems to solve (these aren’t quite the same problems as were in the book but they’re close enough):

CASE ONE: There are four stones half buried in the ground with only one face visible. These stones have a letter and a numeral engraved on opposite sides. Suppose we can see that the stones read A2W9. We want to determine whether any stone with a vowel on one side has an even number on the other, but can only dig up two stones. Can we determine this, and which stones do we check.

CASE TWO: Watson is chaperoning a party. The party serves two drinks lemonade and beer. In an effort to counteract youth drinking people have to buy a wristband, yellow if they want only lemonade, orange if they want the choice of beer as well. Only people over 18 may have beer. Holmes is presented in quick succession by a sixteen year old, a man who wants a yellow band, a twenty-three year old, and a woman who wants an orange band. Who does Holmes have to check IDs/ask what colour band they want?

These puzzles probably aren’t difficult for maths students, we deal with the idea of how to check whether P implies Q everyday. But for most people the second question is much easier than the first, although really the two questions  are isomorphic (the rule is P implies Q, where P is either a vowel or under-eighteen, and Q is an even number or gets a yellow wristband. To check this we only need to check that the cases where we observe P or not Q obey the rule. That is A and 9, or the sixteen year old and the person who wants an orange band).

So what do we take from the fact that most people find the second case significantly easier. Humans are very well suited to thinking about other people, and less well suited to thinking about problems in the abstract (not that we’re bad at that). Ceteris paribus I enjoy abstract problems that can be stated in human terms, which I why I particularly enjoy this proof’s explanation of the Handshaking Lemma. This is a graph theoretic result that can be presented as a “human” problem, and is very tidy to solve.

Handshaking Lemma

Handshaking Lemma Show that the number of those, who have shaken their hands with others an odd number of times, is even. (Note to pure mathematicians – assume the number of people in the world is finite.). Continue reading

Doing the impossible (but not really) with infinitary processes and the axiom of choice

One of the interesting things about mathematics is that it allows us to reason about objects (like fractals, dimensionless points or infinite sequences) and processes (limits, the axiom of choice) that, while logically sound and often even intuitive, cannot actually exist or be feasibly carried out in real life. This is arguably one of the main reasons for a common popular view of pure mathematics as being “too theoretical”, aka. of no practical use. Admittedly this ability of what is known as “classical” mathematics to talk about infinities, infinitesimals and ambiguous choices has given rise to some strange results, like the notorious Banach–Tarski paradox, which informally says that a 3-dimensional ball can be divided into finitely many pieces and reassembled into two balls each identical to the original, or the Riemann rearrangement theorem, which states that a conditionally convergent real infinite series {\sum_{n=1}^{\infty} a_n} can be rearranged to converge to any real number whatsoever, or to {\pm\infty}.

Effective or not?

Both these theorems are statements about our ability to accomplish certain actions, and the proof of each consists of a description of a procedure to do so. So are these surprising results actually practicable in real life? The latter is; we can obtain an algorithm that, given a conditionally convergent series, rearranges its terms to either diverge or converge to a specified real number [BB09]. The former is not, as it relies on the axiom of choice to select points from an infinite number of sets, and while we can infer non-trivial things about the resulting set, there is no way for finite, mortal mathematicians to actually construct it. So while both theorems are statements of the logical possibility of accomplishing a certain seemingly impossible task, only the rearrangement of the infinite series to converge to any sum is “physically” possible; the feasibility of cutting an orange into five pieces and putting them back together to get two oranges remains firmly in the realm of logic, out of the material world.

This illustrates a subtle but important distinction between the procedures described in the respective proofs. We say that there is an effective procedure for the series rearrangement problem: for any conditionally convergent series the procedure always terminates in a finite number of steps and returns the desired result, a permutation of the terms of the series which sums to a given number, or diverges. This is characteristic of what we call effective procedures in general: a series of instructions guaranteed to end in a finite number of steps, always returning a correct result. The procedure for decomposing a 3-ball into a finite number of pieces and reassembling them into two identical 3-balls is a non-effective process; since an infinite number of selections must be made in order to obtain those pieces in the first place, we can never hope to actually get our hands on any of the pieces, much less reassemble them!

Guessing numbers in a random real sequence

I would like to discuss another example of a non-effective procedure which “enables” us to accomplish an impossible feat. Consider the following

Problem. A house has a hundred rooms. In each room are an infinite number of boxes labelled with the natural numbers n = 1, 2, 3, \dotsc, each containing an arbitrary real number. The rooms are identical, so that in each room the n-th box always contains the same number. We kidnap a hundred mathematicians and into each room send one, where they are allowed to open up boxes to reveal the numbers inside. They may open as many boxes as they like (possibly infinitely many) as long as at least one box is left unopened. Each mathematician’s task is to guess the number inside a particular unopened box of their choice. They know that the rooms are identical, and once they have been sent into the rooms no further communication is allowed. Before they are sent to the rooms they are given a chance to discuss a strategy.

Find a strategy that will enable at least 99 of the 100 mathematicians to correctly guess their real number. Continue reading