Sylvy’s weekly puzzle #4

Cross-reference to puzzle page on my website

This is an old one, but good fun.

Sylvy’s weekly puzzle #4

Let \mathcal{P}(\mathbb{N}) denote the powerset of the natural numbers. For clarity, we will consider 0 to be a natural number. Then the pair

(\mathcal{P}(\mathbb{N}),\subseteq)

is a partial order: the (weak) ordering is reflexive, antisymmetric, and transitive. But it is very definitely not a total order: given X,Y\in\mathcal{P}(\mathbb{N}) we may have neither X\subseteq Y nor Y\subseteq X. A chain is a subset \mathcal{C} of \mathcal{P}(\mathbb{N}) on which \subseteq is a total order. For example:

\mathcal{C}_{0}=\big\{\emptyset,\{0\},\{0,1,\},\{0,1,2\},...\big\}

is a chain, but note that \mathcal{C}_{0} is countable.

This week’s problem is to find an uncountable chain, that is a subset \mathcal{C} of \mathcal{P}(\mathbb{N}) which is totally ordered by \subseteq and uncountable.

Deadline: 10am Thursday 5th of November

(you can either send your solution by email or put a hand-written solution into the folder on my office door)

Prize: I’m very please to anounce that the winner will get a book of mathematical puzzles!!

Solution class: there will be a class at 10am on Thursday 5th of November in my office to go over the solution to this puzzle.

The webpage for these puzzles is http://anscombe.sdf.org/puzzle.html

Have fun!

Advertisements

Two old-ish Terry Tao posts about model theory

I can’t get enough of Terry Tao’s blog What’s New, he writes so much and so brilliantly. Anyway, I found two really nice old-ish posts about model theory:

  • this which talks about completeness, compactness, zeroth-order logic, and Skolemisation;
  • and this which talks about nonstandard analysis, notions of `elementary convergence’ and `elementary completion’, countable saturation, compactness and saturation re-written from an analytical point-of-view, and the Szemerédi regularity lemma (something I always want to know more about).

I don’t have time to write anything more now, but later I will get back to it.

 

Sylvy’s Weekly Puzzle #3, Solution (part I)

Cross-reference to puzzle page on my website

I’m really pleased at the interest the third puzzle has generated! Or maybe I just haven’t been able to stop talking about it… 🙂 Anyway, here is the first part of the solution:

The question asked us to investigate the world about which Sonic runs around in a certain special level. Let’s call that world \mathcal{S}. I want to describe \mathcal{S} as a topological suface. If you’ve not come across this notion before, you might like to think of a few key examples:

  • the (real) plane \mathbb{R}^{2},
  • the open unit disk D^{2}=\{(x,y)\in\mathbb{R}^{2}\;|\;x^{2}+y^{2}<1\}, and
  • the sphere S^{2}=\{(x,y,z)\in\mathbb{R}^{3}\;|\;x^{2}+y^{2}+z^{2}=1\}.

Slightly more exotic examples:

  • the Möbius band,
  • the Torus,
  • (variations on the theme…) multi-handled tori, and
  • the Klein bottle.

Perhaps now isn’t the time for a complete exposition of topological surfaces (okay, I may have got part-way through drafting one…!), that may come later. For the present I just want to say a few words about the Euler characteristic (which is denoted \chi) of a surface, and the formula that goes with it:

V-E+F=\chi\qquad(\star_{1}).

The first time I ever heard about this it was in the context of the Platonic solids, as follows.

  • Let’s begin by thinking of a cube. A cube has 8 corners (we’re going to call these vertices), 12 edges, and 6 faces. If V denotes the number of vertices, E the number of edges, and F the number of faces; then we have V-E+F=8-12+6=2.
  • Next, let’s think of a tetrahedron. In this case there are 4 vertices, 6 edges, and 4 faces; thus we have V-E+F=4-6+4=2.

(Can you see where this is going?)

  • Now let’s think of an octahedron. Here there are 6 vertices, 12 edges, and 8 faces; we have V-E+F=6-12+8=2.

You can check that the same formula

V-E+F=2\qquad(\star_{2})

holds for the other Platonic solids – but it doesn’t stop there. What about other solids, for example the Archimedean solid the rhombicuboctahedron?

(I picked this one just because it has such a beautiful name.) The formula holds here too: we have V=24, E=48, F=26. Therefore (\star_{2}) holds for this solid:

V-E+F=24-48+26=2.

In fact:

The formula (\star_{2}) holds for all polyhedra that are topologically equivalent to the sphere \mathcal{S}^{2}.

Although I won’t properly define `topological equivalence’ here, let me just say that – roughly speaking – two shapes A and B are topologically equivalent if one can be transformed into the other by continuous shrinking, stretching, bending, twisting, etc. (discontinuous transformations such as tearing or joining are not allowed). Each of the polyhedra discussed above is topologically equivalent to the sphere.

Let’s now think about the surface \mathcal{S} that sonic explores. It is given to us equipped with a vertices/edges/faces structure so we can calculate V-E+F. On \mathcal{S}, each face has four edges and each vertex is the endpoint of four edges. We don’t seem to know how many faces there are, so let n be the number of faces. Then there are 2n edges and n vertices. [Why?] Thus $V-E+F=0$. This shows that \mathcal{S} is not topologically equivalent to a sphere. This is a negative answer to the first part of the puzzle.

On the other hand, \mathcal{S} could be a torus, as shown by the following map for one of these levels:

[Map of a Special Stage in Sonic 3, copyright Sega (fair use of image for educational purposes)]

How does this show that \mathcal{S} could be a Torus? You can see quite easily that the programmers have joined the left edge to the right edge and joined the top edge to the bottom edge. Thus, if Sonic walks off the left edge of the map, he will just pass round to the right edge (without noticing!).  This shape is quite easily seen to be a Torus. This is a positive answer to the second part of the puzzle.

In the third part, I asked about whether \mathcal{S} could be a Klein bottle, and I’ll write a second post with the answer.

[Edit: perhaps it’s unfair to use the map of the level that I found online to argue that \mathcal{S} might be a Torus. In fact the map (plus the description of how the edges are `obviously’ joined together) shows that \mathcal{S} definitely is a Torus. If you didn’t have the map of the level then I think it’s reasonable to simply argue that a Torus can admit a vertex/edges/faces structure as seen in the level (i.e. with `square’ faces joined in fours at vertices). We’ll address the question of whether \mathcal{S} must be a Torus in the second part of this answer, when I’ll also discuss the Klein bottle.]

Sylvy’s weekly puzzle #3

Cross-reference to puzzle page on my website

My students already know that I am setting `weekly’ fun maths puzzles – although they’re not quite weekly! The first two can be found here, and I may well elaborate on them in later posts. For now, I want to discuss puzzle number 3. Remember: this is aimed at undergraduates in the first term of their first year, so please: no spoilers from more knowledgeable folks. 🙂

Sylvy’s Weekly Puzzle #3

This one is a little more `open ended’ than the previous puzzles. The winner will be the best attempt at an `investigative’ solution.

I tried to describe one of my favourite levels on the computer game Sonic to you (in fact I think it was on Sonic 3 – my bad), here is a screenshot:

[Special stage on Sonic 3 Copyright Sega (fair use of image for educational purposes)]

The game is played on a certain kind of `grid’. It’s an infinite two-dimensional grid, like a chessboard but infinite in all directions. No matter where Sonic goes, his world looks like this. My question is:

What can you say about the topology of his world?

Of course, that’s really an unfair question, because it should be asked to students that have studied a bit of topology or graph theory. Let me rephrase it more simply: could the world Sonic inhabits in the bonus level be:

(i) a sphere?

(ii) a torus?

or (harder)

(iii) a Klein Bottle?

Key things to investigate here are: Euler’s formula \chi=V-E+F and the classification of closed surfaces.

Deadline: 10am Thursday 22nd October (either by email or hand-written solutions in the folder on the outside of my office door)

Prize: something edible (several of the prizes from Puzzle #4 onwards will include a book of Mathematical Puzzles!)

Don’t forget: Class at 10am THIS THURSDAY in my office to go over the previous puzzle.

The webpage for these puzzles is http://anscombe.sdf.org/puzzle.html

Have fun!

Still mostly maths

Originally, I had intended this blog to be a tool I would use to help teach an introductory course on Statistics, but that plan changed when I switched to using UCLan’s own system (`Blackboard’) for managing course materials. So this blog has a new purpose: it will be a random, unplanned, haphazard collection of bits and bobs that pique my interest…. but it will always be `mostly maths’.