Coffee-Break Problem, 24/08/20

Consider noughts-and-crosses on a 3\times 3\times 3 grid. There are multiple possible interpretations of the rules: we can choose any of

A: No gravity, so that any cell can be played at any time;
B: Gravity, but no rows: any cell can be played so long as all the cells under it have been played;
C: Rows: the first horizontal layer must be completed before the second layer can be started, and the second layer must be completed before the third layer can be started;

and either of

L: Long Diagonals allowed for a victory condition, or
NL: No Long Diagonals.

With each possible set of rules and perfect play, who wins?

Coffee-Break Problem, 17/08/20

Walking from Athens to Thebes, I am stopped by a Sphinx who has a grudge against pure mathematicians, and does not wish to allow me to pass.

The Sphinx proposes the following game: they think of a number, and I can ask yes/no questions; I win by finding the Sphinx’s number. Unknown to me, the Sphinx never actually chooses a number, and makes up the answers as they go along; being a perfect logician, these answers are chosen consistently so that I can never catch them in a lie.

Prove that the Sphinx has a winning strategy: the answers can be chosen so that the game never terminates.

What if the Sphinx is constrained to choose all the yes/no answers before I start my questions?

For bonus points: relate your solution to this previous problem.

Coffee-Break Problem, 10/08/20

Consider a network of queues, each with one server. At the i^\text{th} queue, the first customer in the queue is served with rate \mu_i , and moves to another queue j with probability p_{ij} , or leaves the system with probability 1-\sum_j p_{ij} .

Customers enter the network in queue 1 , and arrive opportunistically: when the system is non-empty, customers arrive \lambda , but if the system is already empty, they arrive at some other rate \lambda' .

Fixing \lambda , show that the proportion of customers arriving when the system is in a given state does not depend on \lambda' .

Coffee-Break Problem, 27/07/20

Today’s problem is not particularly deep, but made me smile when I first realised it.

Let G=(V,E) be a (potentially infinite) graph, and let \mathcal{F}=\{E'\subset E: (V,E') \text{ contains no cycles}\} be the space of forests – that is, subgraphs of G made of unions of trees.

Equip \mathcal{F} with the topology whose basic open sets are U=\{E'\in \mathcal{F}: e_1\in E', ....e_n\in E', e_{n+1}\not \in E',...., e_{n+m}\not \in E'\} , for n, m\ge 0 and e_1, ...e_{n+m} \in E . Show that this topology is compact and Hausdorff, and if E is countable, then it admits a metric.

The significance is that compact and Hausdorff spaces have very nice properties when we look at the space of probability measures – for instance, given a sequence \mu_n, n\ge 1 of Borel probability measures on \mathcal{F} , we can always pass to a weakly convergent subsequence.