recreational Questions - MathOverflow

And old hat with a new plume

2013-06-17T13:40:08Z

The story of the blue-eyed islanders is well known, I assume. http://mathoverflow.net/questions/29323/math-puzzles-for-dinner-closed http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ So I will not repeat it here. But yesterday, not over dinner but over tea, I heard this version of a possible (?) solution:

Since all islanders including the blue-eyed ones know that a big number of blue-eyed islanders is around, they will never expect that anybody would commit suizide after one night. Therefore, and since they are intelligent enough to know that they have not got additional information by the stranger, they will never start to count the nights. So they will never commit a mass-suicide.

Perhaps not a research level question. But I have no idea about it. So I would like to get the correct answer if possible. (This story is probably related to "announcing an unannounced exam this week".)

Thanks in advance. During the rest of the week I will not be in contact with civilisation, so I cannot respond to any answers or comments before next Sunday.

Which popular games are the most mathematical?

2010-02-01T09:42:11Z

I consider a game to be mathematical if there is interesting mathematics (to a mathematician) involved in

the game's structure,
optimal strategies,
practical strategies,
analysis of the game results/performance.

Which popular games are particularly mathematical by this definition?

Motivation: I got into backgammon a bit over 10 years ago after overhearing Rob Kirby say to another mathematician at MSRI that he thought backgammon was a game worth studying. Since then, I have written over 100 articles on the mathematics of backgammon as a columnist for a backgammon magazine. My target audience is backgammon players, not mathematicians, so much of the material I cover is not mathematically interesting to a mathematician. However, I have been able to include topics such as martingale decomposition, deconvolution, divergent series, first passage times, stable distributions, stochastic differential equations, the reflection principle in combinatorics, asymptotic behavior of recurrences, $\chi^2$ statistical analysis, variance reduction in Monte Carlo simulations, etc. I have also made a few videos for a poker instruction site, and I am collaborating on a book on practical applications of mathematics to poker aimed at poker players. I would like to know which other games can be used similarly as a way to popularize mathematics, and which games I am likely to appreciate more as a mathematician than the general population will.

Other examples:

go
bridge
Set.

Non-example: I do not believe chess is mathematical, despite the popular conception that chess and mathematics are related. Game theory says almost nothing about chess. The rules seem mathematically arbitrary. Most of the analysis in chess is mathematically meaningless, since positions are won, drawn, or tied (some minor complications can occur with the 50 move rule), and yet chess players distinguish strong moves from even stronger moves, and usually can't determine the true value of a position.

To me, the most mathematical aspect of chess is that the linear evaluation of piece strength is highly correlated which side can win in the end game. Second, there is a logarithmic rating system in which all chess players say they are underrated by 150 points. (Not all games have good rating systems.) However, these are not enough for me to consider chess to be mathematical. I can't imagine writing many columns on the mathematics of chess aimed at chess players.

Non-example: I would exclude Nim. Nim has a highly mathematical structure and optimal strategy, but I do not consider it a popular game since I don't know people who actually play Nim for fun.

To clarify, I want the games as played to be mathematical. It does not count if there are mathematical puzzles you can describe on the same board. Does being a mathematician help you to learn the game faster, to play the game better, or to analyze the game more accurately? (As opposed to a smart philosopher or engineer...) If mathematics helps significantly in a game people actually play, particularly if interesting mathematics is involved in a surprising way, then it qualifies to be in this collection.

If my criteria seem horribly arbitrary as some have commented, so be it, but this seems in line with questions like Real world applications of math, by arxive subject area? or Cocktail party math. I'm asking for applications of real mathematics to games people actually play. If someone is unconvinced that mathematics says anything they care about, and you find out he plays go, then you can describe something he might appreciate if you understand combinatorial game theory and how this arises naturally in go endgames.

How fast are a ruler and compass?

2010-07-22T18:06:18Z

This may be more of a recreational mathematics question than a research question, but I have wondered about it for a while. I hope it is not inappropriate for MO.

Consider the standard assumptions for ruler and compass constructions: We have an infinitely large sheet of paper, which we associate with the complex plane, that is initially blank aside from the points 0 and 1 being marked. In addition we have an infinite ruler and a compass that can be stretched to an arbitrary length.

Let us define a move to be one of the two actions normally associated with a ruler and compass:

Use the ruler to draw the line defined by any two distinct points already marked on the paper.
Stretch the compass from any one marked point to another and draw the resulting circle.

Assume that all intersection points among lines and circles drawn by these operations are automatically marked on the paper.

Now define $D(n)$ to be the maximum distance between any two marked points that can be constructed in this way with $n$ moves.

Questions:

Is anyone aware of results about the function $D(n)$ or something equivalent?
It is not difficult to prove $D(n) > 2^{2^{cn}}$ for some positive constant $c$ for sufficiently large $n$. Can one do better? If so, can one prove an upper bound on $D(n)$?

Increasing sequence of normal magic squares

2013-04-05T08:56:12Z

The questions below are motivated by pure curiosity. I heard of the first question from my former advisor. I have no idea how difficult they are, since I have no experience with magic squares.

By a normal magic square of order $n$ I mean a $n\times n$ magic square whose terms are all of the numbers $0,1,\ldots,n^2-1$.

Is it possible to construct an infinite sequence $M_n$ of normal magic squares such that $M_{n}$ is a block submatrix of $M_{n+1}$ lying in the centre of $M_{n+1}$ (i.e. to obtain $M_{n}$ we remove from $M_{n+1}$ the $k$ top rows, $k$ bottom rows, $k$ columns from the left and $k$ columns from the right)?

Can one construct a normal magic square of odd order (greater than $1$) with $0$ as the central element of the square?

Note that a positive answer to the second question gives a positive answer to the first one. Let $A=[a_{ij}]_{0\leq i,j\leq n}$ be a magic square as in question 2. For a number $c$ we shall use the notation $A+c=[a_{ij}+c]_{0\leq i,j\leq 2n}$ Then: $$A'=\left[\begin{matrix}A+(n+1)^2a_{00} & \dots & A+(n+1)^2a_{0n} \\ \vdots & \ddots & \vdots\\ A+(n+1)^2a_{n0} & \dots & A+(n+1)^2a_{nn}\end{matrix}\right]$$ is a normal magic square with $A$ in the centre.

easter problem - egg shapes

2013-03-29T22:39:03Z

Inspired by an exceptionally silly article in today's newspaper I pose the following "egg parametrization problem".

Give an explicit function $ f(x,y,t) : \mathbb{R}^2\times I \to \mathbb{R}$ such that for each $t$ from interval $I$ the solution set of equation $f(x,y,t) = 0$ looks like an egg.

I'm looking for function that provides most of the various egg shapes found in nature.

Are there results in "Digit Theory"?

2013-03-21T10:46:41Z

Results about numbers that are related to their decimal representation are usually confined to recreational mathematics. There I have seen mainly questions about individual numbers, like finding a number that is the sum of the cubes of its digits. But I have not yet seen a systematic study of such questions.

A result that prompted me to asked this question was the following from Kurt Hensel's "Zahlentheorie". There he shows that the exponent of highest power of a prime $p$ that divides the number $n$ is $$\frac{s_{n-1} - s_n + 1}{p - 1},$$ where $s_n$ is the sum of the digits in the representation of $n$ with base $p$. From this he derives that the highest power of $p$ that divides $n!$ is $$\mu_n = \frac{n - s_n}{p - 1}.$$ This is a different and much simpler formula than the representation $\mu_n = \sum_{k = 0}^\infty \left\lfloor \frac{n}{p^k} \right\rfloor$ by Legendre, which I usually see in the literature.

I would like to know whether there are more results of this type. To be more precise, I define the not-yet-existing field of "Digit Theory" as the study of number-theoretic questions with help of the positional representation of numbers, and the study of the positional representation itself.

So are there already systematic treatments of "Digit Theory" or of parts of it? Are there other interesting results like that one above?

Examples of interesting false proofs

2012-04-21T14:26:12Z

According to Wikipedia False proof

For example the reason validity fails may be a division by zero that is hidden by algebraic notation. There is a striking quality of the mathematical fallacy: as typically presented, it leads not only to an absurd result, but does so in a crafty or clever way.

The Wikipedia page gives examples of proofs along the lines $2=1$ and the primary source appears the book Maxwell, E. A. (1959), Fallacies in mathematics.

What are some examples of interesting false proofs?

Generalizing square wheels rolling on inverted catenaries

2010-06-30T00:22:42Z

It is not uncommon to see in a science museum a bicycle with square wheels that rides smoothly over a washboard-like surface made from inverted catenary curves (e.g., at the Münich museum). The square wheel may be generalized to any regular polygon (except the triangle), which rolls on a similar curve without slippage. Here, for example, is a nice Mathematica demo.

My question is: For which wheel shapes does there exist a matching road shape that permits the wheel to roll over it without slippage so that: (a) the wheel center remains horizontal throughout its motion, (b) the wheel can turn at constant angular velocity, and (c) if possible, the wheel center also moves at constant horizontal velocity?

The square satisfies (a) and (b), but only regular hexagons and beyond satisfy (c). If you've experienced a square-wheel bicycle ride, you can feel it jerk because (c) fails to hold. It would be interesting to know the class of closed wheel curves that satisfy (a) and (b), and also those that in addition satisfy (c). For example, must all (a,b) curves be star-shaped from the wheel center $x$? (star-shaped: every point of the curve is visible from $x$).

This is probably all known, so an appropriate reference may suffice.

Addendum1 (1July10). The delightful Hall-Wagon paper that user abel found (below) answers many of my questions, and may be the last word (or the most recent work) on the topic. However, it does not seem to address the broader question I posed: For which class of wheel shape curves is a such a wheel-road construction possible? I'll update further if anything comes to light.

Addendum2 (8June11). A paper just appeared in the Amer. Math. Monthly (Vol.118, No.6, 2011), "Roads and Wheels, Roulettes and Pedals," by Fred Kuczmarski, which seems to establish that a wheel-road construction is possible for every

continuously differentiable plane curve such that the angle of rotation of its tangent lines, as measured relative to some initial position, is a strictly monotonic function of arc length. We call such curves rollable. The monotonic condition implies that rollable curves have no inﬂection points, while the strictness of the monotonicity precludes rollable curves from containing line segments.

Certainly this is not the full class (as he mentions), but he has a nice theorem that constructs a road for any rollable-curve wheel.

Randomly switching street lights, in a square city

2013-01-19T18:40:51Z

This is a combinatorics-probability question, best stated however in "recreational" terms. Imagine a $N\times N$ city, meaning that we have $N$ horizontal streets, and $N$ vertical streets. At each crossroads there is a street light.

When evening comes, some of the lights are switched on, namely those corresponding to a certain given subset $E\subset(1,\ldots,N)\times(1,\ldots,N)$.

Now assume that $2N$ kids come at night and start randomly playing with the switches: there is one such on/off switch at the end of each of the $2N$ streets.

Problem: for each of the $4^N$ overall choices for the various switches, we count the number $K$ of street lights that are switched on. What is the law of this random variable $K$, as a probability measure on $(1,2,\ldots,N^2)$, depending on the initial set $E$?

[Edit, Jan 20. As signaled by Joseph O'Rourke in his answer below, computing the upper edge of the support of the measure $\mu_E$ in my problem is known as the Gale-Berlekamp game, a difficult question (details can be found via Google search). So I realise that my problem is probably extremely difficult, adding the "open-problem" tag. I'd be interested however in the case where $E$ is an Hadamard matrix, cf. discussion with Gerhard Paseman in the comments below. Is there anything known about this measure $\mu_E$? (I mean, not only about its support.)

Btw here is the only non-trivial complete computation that I have so far: concerns the case $N=4$, where there are exactly $|E|=4$ street lights, positioned on the main diagonal of the city. Here $\mu_E=\frac{1}{32}(\delta_4+12\delta_6+6\delta_8+12\delta_{10}+\delta_{12})$. Plus an experimental remark, that I'm not able to prove abstractly: the support of $\mu_E$ seems always to be an arithmetic progression.]

Proving a determinant = 0

2013-01-13T08:45:29Z

The two most elementary ways to prove an N x N matrix's determinant = 0 are:

A) Find a row or column that equals the 0 vector.

B) Find a linear combination of rows or columns that equals the 0 vector.

A can be generalized to

C) Find a j x k submatrix, with j + k > N, all of whose entries are 0.

My minor question is: Is C a named theorem that one can easily reference?

My major question is: Are there are other canonical ways of proving a determinant = 0?

The context is that I'm trying to solve the generalized form of what was, as stated, a very easy Putnam Exam problem, and I last took a linear algebra class in 1974.

In response to comments below, let me say: - Thanks! - This isn't about computational efficiency. - Frobenius-Koenig looks very helpful.

Reconstructing the argument that yields Graham's number

2012-12-22T03:43:26Z

Graham's number achieved a kind of cult status, thanks to Martin Gardner, as the largest finite number appearing in a mathematical proof. (It may no longer hold that record, but that is not my concern here.) I was surprised to learn relatively recently that it is not actually the best known bound for that particular Euclidean Ramsey problem, and that the original paper by Graham and Rothschild, which predates "Graham's number," explicitly derives a better bound. I'm left to assume that Graham later found a simpler argument that gave a weaker bound, that we now know as Graham's number.

Some time ago, before I realized the above facts, I asked Graham about his "Graham's number" proof. As I recall the conversation, he no longer had the argument at his fingertips and did not seem too interested in trying to reconstruct it. This brings me to my question:

Can someone reconstruct a simple argument for the Euclidean Ramsey problem in question that naturally yields Graham's number as an upper bound?

This would not normally be that interesting a question except that Graham's number still circulates in recreational mathematics circles, so it's a bit embarrassing if nobody knows how to "derive" it.

Neutral tic tac toe

2010-05-15T04:01:26Z

I heard this puzzle from Bob Koca. Suppose we play misere tic-tac-toe (a.k.a. noughts and crosses) where both players are X. Who wins?

That particular puzzle is easy to solve, but more generally, has $n \times n$ impartial tic tac toe, in both normal and misere forms, been studied before?

Smallest square to wrap a cylinder

2012-12-25T20:54:11Z

Suppose you need to gift-wrap a cylinder (e.g., a can of tennis balls, or a large candle) of height $h$ and radius $r$. Here wrap is the natural sense of covering the surface area of the cylinder completely, without cutting the square, creasing however needed. What is the smallest square that suffices for a given $h$ and $r$? For example, a rectangle of dimensions $(h+2r) \times (2 \pi r)$ suffices for how one might wrap a can of tennis balls or a stout candle:

In this $h=3$ and $r=1$ case, the rectangle has dimenions $5 \times 6.28$, and so a square of side $2 \pi$ suffices. But is that optimal?

Merry Christmas!

2D visualization of sum of divisors using Cantor pairing

2012-11-28T08:52:42Z

Related to Gerhard's question about ascii plots. On the SeqFan mailing list was suggested to plot an integer sequence this way:

Let $F(x,y)= (x+y) (x+y+1)/2+y$ be the Cantor pairing. To plot an integer sequence $a(n)$, for a point $(x,y)$ compute $a(F(x,y))$ and assign color to the integer, e.g. in grayscale smaller is darker, for RGB/HSV there are other choices to map to color.

When $a(n)=\sigma_0(n)$ where $\sigma_0(n)$ is the number of divisors of $n$, the 2D plot shows some structure (hopefully not caused by visual artifacts).

Is there an explanation for the structure in the plot?

Color plot of $\sigma_0(F(x,y))$, smaller is darker (grayscale is quite similar):

When examining the integer values there are some large diagonals indeed.

Does War have infinite expected length?

2010-01-12T04:58:10Z

My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.

The question is: Is the expected length of the game infinite?

The Rules. (from http://en.wikipedia.org/wiki/War_(card_game)) The deck is divided evenly among the two players, giving each a face-down stack. In unison, each player reveals the top card on his stack (a "battle"), and the player with the higher card takes both the cards played and moves them to the bottom of his stack. If the two cards played are of equal value, each player lays down three face-down cards and a fourth card face-up (a "war"), and the higher-valued card wins all of the cards on the table, which are then added to the bottom of the player's stack. In the case of another tie, the war process is repeated until there is no tie. A player wins by collecting all the cards. If a player runs out of cards while dealing the face-down cards of a war, he may play the last card in his deck as his face-up card and still have a chance to stay in the game.

Let us assume that the cards are returned to the deck in a well-defined manner. For example, in the order that the cards are played, with the previous round's winner's cards going first (and a first player selected for the opening battle).

On the Wikipedia page, they tabulate the results of 1 million simulated random games, reporting an average length game of 248 battles. But this does not actually answer the question, because it could be that there is a devious initial arrangement of the cards leading to a periodic game lasting forever. Since there are only finitely many shuffles, this devious shuffle will contribute infinitely to the Expected Value. Thus, the question really amounts to:

Question. Is there a devious shuffle in War, which leads to an infinitely long game?

Of course, the game described above is merely a special case of the more general game that might be called Universal War, played with N players using a deck of cards representing elements of a finite partial pre-order. Any strictly dominating card wins the trick; otherwise, there is war amongst the players whose cards were not strictly dominated. Does any instance of Universal War have infinite expected length?

Does there exist $a,n \in \mathbb{Z}^+$, where $n \geq 2$, such that $a, an, an^2,an^3,\ldots,an^5$ are all palindromes in base 10?

2012-11-05T01:46:46Z

Question: Does there exist $a,n \in \mathbb{Z}^+$, where $n \geq 2$, such that $$a, an, an^2,an^3,\ldots,an^5$$ are all palindromes in base 10?

We see that $a=1$ and $n=11$ give rise to $$1, 11, 121, 1331, 14641$$ which is basically the first few rows of Pascal's triangle. There are infinitely many other examples of length 5, which we can generate by generalising the Pascal's triangle construction, giving $$11, 1111, 112211, 11333311, 1144664411$$ $$111, 111111, 111222111, 111333333111, 111444666444111$$ and so on.

Some other examples are:

$$147741, 13444431, 1223443221, 111333333111, 10131333313101$$

$$1478741, 134565431, 12245454221, 1114336334111, 101404606404101$$

However, I checked for $a,n \leq 10^7+1$, and didn't find any of length greater than 5.

A sudden smiley? :-)

2012-10-27T00:50:24Z

This is a vague question, and I will no doubt be (properly!) chastised for posing it. I would like to generate a set $S$ of points in $\mathbb{R}^3$—$|S|$ finite or infinite—which has the property that, viewing $S$ under orthogonal projection along a random direction $\vec{u}$ results in a more-or-less generic, undistinguished cloud of points. But, there is some specific projection direction $\vec{u^*}$, where suddenly (if one were 3D-rotating the points under mouse control) the cloud resolves itself, through unlikely point alignments, to paint a recognizable image, e.g.,

Is this an impossible :-) hope?

Update. Following Michael Murray's recipe, with $10,000$ points within a cube in $\mathbb{R}^3$, three different viewpoints:

(Somehow my analytical smiley has a Halloween evil glint!)

PS(31 Oct 2012). Happy Halloween!

Titles composed entirely of math symbols

2011-07-11T00:02:26Z

I apologize for burdening MO with such a vapid, nonresearch question, but I have been curious ever since Suvrit's popular October 2010 Most memorable titles MO question if there were any "$E=mc^2$-titles", as I think of them—how Einstein in retrospect might have entitled his 1905 paper (instead of "Zur Elektrodynamik bewegter Körper"!)—paper/book titles composed entirely of math symbols.

There are two close misses in the responses to that MO question: Connes et al.'s "Fun with $\mathbb{F}_{1}$", and Taubes's "${\rm GR}={\rm SW}$: Counting curves and connections." The only title entirely composed of math symbols with which I'm familiar is the delightful book A=B, by Marko Petkovsek, Herbert Wilf, and Doron Zeilberger. Can you identify others?

Please interpret this question in a weekend-recreational spirit! :-)

Covering a Cube with a Square

2012-05-03T14:24:05Z

Suppose you are given a single unit square, and you would like to completely cover the surface of a cube by cutting up the square and pasting it onto the cube's surface.

Q1. What is the largest cube that can be covered by a $1 \times 1$ square when cut into at most $k$ pieces?

The case $k=1$ has been studied, probably earlier than this reference: "Problem 10716: A cubical gift," American Mathematical Monthly, 108(1):81-82, January 2001, solution by Catalano-Johnson, Loeb, Beebee.

(This was discussed in an MSE Question.) The depicted solution results in a cube edge length of $1/(2\sqrt{2}) \approx 0.35$.

As $k \to \infty$, there should be no wasted overlaps in the covering of the 6 faces, and so the largest cube covered will have edge length $1/\sqrt{6} \approx 0.41$. What partition of the square leads to this optimal cover?

Q2. For which value of $k$ is this optimal reached?

I have not found literature on this problem for $k>1$, but it seems likely it has been explored. Thanks for any pointers!

Nonexistence of high dimensional perfect magic hypercubes of fixed side length

2012-08-07T08:33:33Z

I apologize in advance if this question is not of sufficient level. Define a perfect magic hypercube of side length $k$ and dimension $n$ to be one in which the cells are filled with consecutive integers and the sum of numbers over cells in any geometric line is equal to the appropriate constant depending on $n$ and $k$.

From the density Hales-Jewett theorem it follows that for fixed $k$, there cannot exist perfect magic hypercubes of fixed side length $k$ and arbitrarily large $n$. My question is: what are simpler ways to prove the nonexistence of perfect magic hypercubes of fixed $k$ and arbitrarily large $n$? Thanks very much.

Generalized tic-tac-toe

2012-08-02T14:28:01Z

We begin with $2n+1$ cards, each with a distinct number from $-n$ to $+n$ on it, face up in between the two players of the game. The players take turns selecting a card and keeping it. The first player to collect three cards that sum to zero wins the game. If the cards are exhausted and neither player has won, a draw is declared.

Tic-tac-toe, or noughts and crosses, is of course the special case $n=4$, by using the essentially unique $3\times3$ magic square:

$$\begin{matrix} 3 & -4 & 1 \\ -2 & 0 & 2 \\ -1 & 4& -3\end{matrix}$$

Has the case of general $n$ been studied?

Groebner basis for Sudoku

2012-03-19T20:44:26Z

I'm trying to write a program that solves sudoku's using a Groebner basis. I introduced 81 variables $x_1$ to $x_{81}$, this is a linearisation of the sudoku board.

The space of valid sudokus is defined by:

for $i=1,\ldots,81$ : $F_i = (x_i - 1)(x_i - 2)\cdots(x_i - 9)$ This represents the fact that all squares have integer values between 1 and 9.

for all $x_i$ and $x_j$ which are not equal but in the same row, column or block: $G_{ij} = (F_i - F_j)/(x_i - x_j)$ This represents that the variables $x_i$ and $x_j$ can not be equal.

All these $F_i$ and $G_{ij}$ together define the space of valid sudokus. This conists of 891 polynomials.

Now to solve a sudoku we can add the clues to the space, so by example if the clue of a sudoku is the first square is a 5, then we add $(x_1 - 5)$ to the space. If we now take the groebner basis of this space we can directly see the solution for it.

I understand what I am doing this far. But I have trouble finding a computable manner for finding the groebner bases. I have succesfully done everything for 4*4 sudokus (or so-called shidokus). But Maple nor Singular are giving me a result for the groebner basis of the 9*9 sudoku space. You can see the commands I gave to Maple here: http://dl.dropbox.com/u/16797591/mapleSudoku.txt. (First I define the 891 polynomials, then I ask for a basis of it) I read papers saying it's feasible although imperformant to do what I strive for but I don't see how to find the solution, as they don't include many implementation details. Can anyone point me to a direction, making this problem easier for Maple or other software?

Bounding a signed sum of complex numbers

2012-05-29T15:17:11Z

Let $z_i \in \mathbb{C}\:$ for $i=1,\dots, n\;$ be complex numbers, all with absolute value $|z_i|\le 1\;$.

Prove (or disprove) that there exists a choice of signs $s_i \in \{\pm 1\}$ such that $$\left|\sum_{i=1}^n s_i\cdot z_i\right| \le \sqrt{2}.$$

[My interest in this problem is purely for fun. I couldn't solve it a long time ago, forgot about it, but shortly ago it came back into my mind again.]

Looking for a "scientific" application of a recreational puzzle.

2012-05-14T21:19:23Z

First of all the puzzle.

A barman's got 15 glasses which are initially somehow divided into several stacks. The barman repeats the following process a thousand times. He takes the top glass from each (nonempty) stack and forms a new stack with these glasses. Which set of stacks (in terms of their heights) will he come up with?

It's a nice one, give it some thought =)

Having toyed with this problem and its obvious generalizations for an arbitrary number of glasses I came up with the (totally intuitive) hypothesis that such a process and its long-term behavior might emerge in some more-or-less advanced field of research (algebra/geometry/mathematical physics). Can anybody comment?

Update. One can also notice that in this special case of 15 glasses both the problem's statement and the answer are pleasantly simple. I'd be very interested and even somewhat surprised to hear an accordingly simple proof.

Exploding primes

2012-05-10T19:04:42Z

Suppose every prime $n$ could "explode" once. An explosion results in $\lfloor \alpha \ln n \rfloor$ particles being uniformly distributed over the integers in a range $n \pm \lfloor \beta \ln n \rfloor$. If a particle hits a composite or a previously exploded prime, nothing happens. If a particle hits a new prime $p$, then $p$ explodes under the same rules. Here is a little simulation starting at $n=23$, with $\alpha=10$ and $\beta=5$:

So, on the first step, $n=23$ explodes into $\lfloor 10 \ln 23 \rfloor = 31$ particles, uniformly spreading over $23 \pm 15$. In the run depicted, these particles hit four primes:$11, 13, 29, 31$. Then each of those explodes; and so on. In the last frame, $199$ is hit.

Q1. For which $\alpha$ and $\beta$, if any, will this process almost surely explode an infinite number of primes?

I am hoping the answer is independent of the starting $n$.

Being largely ignorant of number theory, I am wondering if current knowledge of the distribution of the primes is sufficient to answer this question. Thanks for insights or even speculations!

Q1 Answered. quid shows that a ballistic range of $\pm \beta \log n$ is not enough to bridge the prime gaps: $\pm \beta \log^2 n$ conjecturally suffices, but a range of more than $\pm \beta \sqrt{n}$ is all that current technology can prove.

Addendum. Both quid and joro confirm that even assuming RH (the Riemann Hypothesis), the range needed for my simulation to provably explode all primes is at least $\pm \beta \sqrt n \log n$. May I add this question:

Q2. What is the minimum ballistic $\pm$-range that would suffice to provably (under "current technology") explode (with sufficent $\alpha$) all primes without any RH or otherwise conjectural assumptions?

Generalizing a square wheel to a body rolling on a surface

2012-04-07T19:38:31Z

A square wheel rolling on a catenary road maintains the wheel center at a fixed height, a well-known construction previously discussed on MO (e.g., "Generalizing square wheels rolling on inverted catenaries"). I wondered if this fundamentally one-dimensional example could be generalized to two dimensions, in the following sense:

Is there a solid body $B$ and a non-flat surface $S$ which together have the property that, from some one, special fixed position of $B$ resting on $S$, $B$ can roll on $S$ in any horizontal direction $v$ so that some point in $B$ (its center) remains at a fixed height?

Of course if $B$ is a sphere and $S$ is a plane, then the constant-height property holds. Note I am asking that this only hold for some special initial position of $B$, but demand that rolling in any direction of the full $360^\circ$ retains constant height along that ray.

My guess is that the requirement that this hold for every position of $B$ on $S$ forces a sphere on a plane.

The following is meant to be suggestive only!

What brought this to mind is the traditional Easter Egg Roll. :-)

Addendum. Here is another suggestive image, not metrically accurate, of a revolved square diamond that can roll on a revolved catenary, as per Anton's answer.

How to get rich in a Hilberts Hotel?

2012-02-12T16:59:55Z

Suppose you can make infinitely many copies of yourself. Each of them starts his/her life in a Hilberts Hotel, where each room is labeled by an element in the free group with two generators, and structured as the Cayley graph of the group. (All the room have the same size, so in particular this hotel is not embedded in $\mathbb{R}^3$!) In the beginning, each clone have 1£. If they all cooperate, they can get richer exponentially fast: If they all give all their money to the neighbor in the direction of $e$, then everyone except the person in $e$ will receive money from three persons, so after n transactions he will have $3^n$£ (and $e$ will receive money from 4 persons, so he will be even richer).

Question: Suppose instead that the rooms were unlabeled. You can decide on a strategy before being copied, and you are allowed to use randomness in this strategy. However, all the copies will be identical, so all of them will think that they are the original "you". Each of the copies can send money and information to each of their four neighbors once each day. Is there a strategy that will make each of them rich exponentially fast?

Comment: If only one of the copies thought he/she was the original you, you could solve the problem: The real you is consider to be $e$. The first day he/she tells his/her neighbors. The next day the neightbors send 2/3 of their money to $e$ and tell their neighbors that "the original you" is in this direction, and so on. With this strategy, each copy become rich exponentialy fast, although it will take some time ("distance to $e$" +3 days) before it starts.

I originally asked the question on my blog, here.

Die-rolling Hamiltonian cycles

2012-02-03T14:07:55Z

Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$, each of whose unit squares is labeled with a number in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$. Say that such a labeled $R$ is die-rolling Hamiltonian, or simply rollable, if there is a Hamiltonian cycle obtained by rolling a unit die cube over its edges so that, for each square $s \in R$, the cube lands on $s$ precisely once, and when it does so, the top face of the cube matches the number in $s$. For example, the $4 \times 4$ "board" shown below is rollable.

Q. Is it true that, if $R$ is die-rolling Hamiltonian, then the Hamiltonian cycle is unique, i.e., there are never two distinct die-rolling Hamiltonian cycles on $R$?

This "unique-rollability" question arose out of a problem I posed in 2005, and was largely solved two years later, in a paper entitled, "On rolling cube puzzles" (complete citation below; the $4 \times 4$ example above is from Fig. 17 of that paper). Although the original question involved computational complexity, the possible uniqueness of Hamiltonian cycles is independent of those computational issues, so I thought it might be useful to expose it to a different community, who might bring different tools to bear. It is known to hold for $R$ with side lengths at most 8. If not every cell of $R$ is labeled, and unlabeled cells are forbidden to the die, then there are examples with more than one Hamiltonian cycle.

Edit1. Rolling a regular tetrahedron on the equilateral triangular (hexagonal) lattice is not as interesting. See the Trigg article cited below.

Edit2. Serendipitously, gordon-royle posted a perhaps(?) relevantly related question: "Uniquely Hamiltonian graphs with minimum degree 4."

The computational version is Open Problem 68 at The Open Problems Project.
"On rolling cube puzzles." Buchin, Buchin, Demaine, Demaine, El-Khechen, Fekete, Knauer, Schulz, Taslakian. Proceedings of the 19th Canadian Conference on Computational Geometry, Pages 141–144, 2007. PDF link to full paper.
Charles W. Trigg. "Tetrahedron rolled onto a plane." J. Recreational Mathematics, 3(2):82–87, 1970.

The sequence $a_{n+1}=$ the greatest prime factor of $(xa_n+y)$

2012-02-12T15:37:44Z

Let $\operatorname{ GPF}(n)$ be the greatest prime factor of $n$, eg. $\operatorname{ GPF}(17)=17$, $\operatorname{ GPF}(18)=3$.

Is there a way to prove that the sequence $a_{n+1}=\operatorname{ GPF}(xa_n+y)$, eventually enter a cycle for all positive integers $x,a_0,y>0$?

Is there any set of positive integers $x,a_0,y>0$ such that $a_{n+1}=\operatorname{ GPF}(xa_n+y)\operatorname{ LPF}(xa_n+y)$ diverges?

Where $\operatorname{ LPF}(n)\geq2$ is the least prime factor of $n$.

Self-tightening knot

2012-01-08T13:01:49Z

Is there a way, for some finite L>1, to tie two pieces of rope together, such that any finite force is not enough to pull them apart?

The type of rope I have in mind is something like cylindrical with radius 1, unbreakable, unstretchable, perfectly flexible, non-self-intersecting and have length L, but I am open to other models.

If rope 1 has ends A and B, rope 2 have ends C and D, we tie B and C together, then pull A and D. Is there a knot that holds for every coefficient of friction e>0 and every force F>0 applied to the two ends?