Hot answers tagged

51

JHI's elegant lower bound of $8$ on $N$ is achieved by an explicit dissection. I show my construction below; you might want to try to find a solution yourself before proceeding $-$ it makes for a neat puzzle. There may well be other ways to do it. If somebody can make a "$3$-dimensional" graphic or picture of the $8$-piece dissection, you're welcome to add ...


45

Here's a solution for the case of seven suspects that uses the Fano plane. Let the seven points of the Fano plane represent the seven suspects. Alice and Bob both reveal the name of the suspect completing a line with the two suspects on their list. There are now two cases to consider: Alice and Bob did not name suspects on each other's lists. Then the ...


38

Update. I made a blog post about Infinite Sudoku and the Sudoku game, following up on ideas in this post and the comments below. I claim that the second player wins the even-sized empty Sudoku boards and the first player wins for odd-sized empty Sudoku boards, including the main $9\times 9$ case. (The odd-case solution uses a key idea of user orlp in the ...


31

The solution mentioned in the question consists in fact of $9$ pieces, as shown in the following picture I took yesterday. I don't know whether a solution with $8$ pieces exists.


31

Indeed, there is no solution for $n=5$, and also none for $n=7$. However, for $n=11$ there is a tiling of the requested form. I found it using a straightforward exact cover formulation and Knuth's original exact cover solver. I'm not sure how to best visualize a solution, here is an attempt using random colors for the tiles. It is a little hard to check that ...


26

I can, at least, answer your question 'Is this in fact the correct answer?' with an affirmative 'no'. Specifically, we can replace the upper bound $2^{n/3} \approxeq 1.26^n$ with the slightly better bound $6^{n/9} \approxeq 1.22^n$ by applying the same 'separate into independent blocks' construction to the following (conjecturally optimal) covering set for $...


22

I discussed this with Arvind Singh a while ago and I think we can show the non trivial inequality $p_{opt}\leqslant\frac{3}{8}$ with simple arguments. The proof relies on the symmetry of the problem and the intuition is that one can not find a strategy wich is good simultaneously for a configuration and its inverse. It will be simpler to work with the sets ...


20

This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be. The proof of the lower bound is rigorous, the proof of the upper bound is not. Denote $k=n/3$. Let us say that a binary word $y\in\{0,1\}^{2k}$ covers a word $x\in \{0,1\}^n$ if $y$ can be obtained from $x$ by removing $k$ digits. Our ...


17

This (top half) is a way to cut 49 banknotes into pieces of at least 10% each and (bottom half) reassemble them to 50 "98%" banknotes. Let $w$ denote the width and $h$ the height. The bills below have an aspect ratio of 1:2 but this isn't necessary. (SVG source code) I hope that it's clear how the pattern continues in the center; simply use each leftover ...


16

This is a great question! I've now managed to eliminate the use of countable choice. Theorem. Without using any choice principle, it follows that player I can have no winning strategy in the game. Proof: Working in ZF only, suppose toward contradiction that player I has a winning strategy $\tau$. Look at the set $A$ played by player I on the first move, ...


15

What about the (diagonal) Ramsey Numbers, $k \to R(k,k)$? These are fairly natural to define but notoriously hard to compute. Indeed, only the first two Ramsey numbers $R(3,3)=6$ and $R(4,4)=18$ are known. We do know that $R(5,5) \in [43,49]$, which is the subject of the following joke (I may be butchering the content). Joke. If an omnipotent alien came ...


14

Here is an exponential lower bound. We begin by determining exactly how many strings $Y$ of length $n$ can be reduced to a given string $X=x_1x_2\cdots x_k$. In general $y$ might contain many copies of $X$, but it contains exactly one left-most copy of $X$; that is, the first $x_1$ then the first $x_2$ and so on. The strings with $X$ as a left-most ...


14

First, Alice chooses minimal $n_a$ divisible by 3 such that her bits at positions $n_a, n_a + 1, n_a + 2$ are not all the same, and Bob similarly chooses $n_b$. Looking at triplet $A_{n_a}, A_{n_a + 1}, A_{n_a + 2}$. Alice chooses $m_a$ according to following rule: {010: 2, 011: 2, 001: 1, 110: 0, 100: 0, 101: 1}. Bob chooses $m_b$ in the same way. Now ...


13

[Edit: I had originally posted a proof that finding the minimum value was NP-hard; in the comments below, Brendan McKay pointed out how to convert that into a proof that finding the maximum value is NP-hard, which was the question asked by the original poster. I have edited this to include a complete answer to the original question.] Let's refer to the ...


12

Consider the function $f:n\mapsto k$, where the power set $2^{\aleph_n}$ has the form $\aleph_{\omega\beta+k}$ for some natural number $k$. This function is everywhere defined, since the power set $2^{\aleph_n}$ must be $\aleph_\alpha$ for some ordinal $\alpha$, and every ordinal can be uniquely expressed in the form $\omega\beta+k$. The number $k$ is ...


12

This appears to be a description of the "OK Corral process" as an urn problem. This stochastic process was apparently introduced by David Williams and Paul McIlroy in the 1998 article The OK Corral and the power of the law and was subsequently investigated by J.F.C. Kingman and S. E. Volkov. In the 1999 article Martingales in the OK Corral Kingman proved ...


12

Following David Speyer's improvement, given a rooted tree on $n$ vertices, we number each vertex $v$ with an integer $i_v$ mod $n$ so that the root is numbered $0$ and, if vertex $v_1$ is a child of vertex $v_2$ then $i_{v_1}$ is $i_{v_2}$ plus the number of descendants of $v_1$ (including $v_2$). We say a rooted tree is valid if all the vertices $v$ have ...


11

I searched "Tower of Hanoi" on arXiv (with 18 results at time of last edit): The Group of Symmetries of the Tower of Hanoi Graph The Tower of Hanoi and Finite Automata Shortest paths in the Tower of Hanoi graph and finite automata Asymptotic aspects of Schreier graphs and Hanoi Towers groups A search on Wikipedia returned the Tower of Hanoi and Magnetic ...


11

If a vector has $d$ one-entries, and $d\leq n/2$, then delete as many ones as you can, (and further zeros if necessary). Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can, (and further ones if necessary). Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ ones. The number of such vectors ...


10

Your (1) could be substituted for pedagogical ease of presentation with the Conway's Game of Life "halting problem" (note that they are equivalent). That is, the function which for any starting configuration returns a value indicating whether the system eventually reaches a stationary state (return 0), periodic cycle (return 1), or never becomes stationary ...


8

How about this one: $f(n)=1$ if $2^{2^n}+1$ is prime, and $f(n)=0$ otherwise. Or: $f(n)$ is the largest prime factor of $2^{2^n}+1$. Added 1: Inspired by Barry Cipra's comment, here is a function which is unknown in principle, not just in practice: Let $r(m)$ denote the number of lattice points on the sphere $x^2+y^2+z^2=4m+1$, and define $f(n)$ as the ...


8

How about something based on a generalized twin prime conjecture? That is, $f(n)=1$ if there are infinitely many pairs of primes that differ by $2n$ (and $f(n)=0$ if not). Added 9/15/12: It might be worth modifying the example to say $f(n)=1$ if and only if there are infinitely many pairs of consecutive primes that differ by $2n$. That would bring it ...


8

There is a surprising asymptotic result in 2 dimensions, closely related to your question. See [MR0370368] Erdős, P.; Graham, R. L. On packing squares with equal squares. J. Combinatorial Theory Ser. A 19 (1975), 119–123.


8

For $n=12$ it is possible to use $10$ strings of length $2k=8.$ There is, for $n=3k$, a smallest size $s(n)$ for a set $S$ of strings in $ \{0,1\}^{2k}$ which covers all the strings in $\{0,1\}^n$. We have $s(n_1)s(n_2)\ge s(n_1+n_2)$ so, by Fekete's Lemma there is a constant $\alpha=\inf {s(n)^{1/n}}$ such that $\lim {s(n)^{1/n}}=\alpha.$ We so far ...


8

It is possible to have every mathematician guess the number in one of the boxes with at most one error. Partition the natural numbers into countably many sets, $\{S_i\}_{i=0}^\infty$, where each $S_i=\{n_{i_1},n_{i_2},\dots,\}$ is countably infinite. (There are many ways to do this) Since we have countably many mathematicians, we may list them, and assign $...


8

Typing "undecidable" and "puzzle" into MathSciNet turned up a couple of candidates. Baumeister, Dorothea and Rothe, Jörg, The three-color and two-color Tantrix rotation puzzle problems are NP-complete via parsimonious reductions, Inform. and Comput. 207 (2009), no. 11, 1119–1139, MR2566946 (2011c:68052). According to the summary, the infinite variants of ...


8

Yes, every link can be obtained in this way. Here's an inefficient way to do it. Put the link in braid form (via Alexander's theorem); suppose that we have $b$ strands. We'll achieve each braid generator as a certain pattern among $2b$ people on the circumference of the circle. Here's a picture that explains better than my words can. All the horizontal (...


7

The language which I have usually seen it written in is that of self-similar groups, which are automorphisms of rooted trees. I'd say this mostly falls under the label of geometric group theory, and is quite useful in the study of dynamical systems. The language of finite automata is useful in understanding these groups though. @John Mangual did a fairly ...


7

This answer is not entirely serious, but it does not fit as a comment. Numberwang is undecidable. Numberwang, of course, is a fictional popular game show featured as a running gag in the real sketch comedy show The Mitchell and Webb Look. Here is a sample episode of Numberwang. The rules of the game are never explained, but they seem to follow this format: ...


7

In the comments, Emil Jeřábek and Terry Tao have given an asymptotic lower bound of $4n / \log_2 n$. For the upper bound, $2n$ is trivial, obtained by weighing each ball individually. Here is a solution which only requires $n+1$ weighings. Let $h$ be the weight of a heavy ball and $\ell$ be the weight of a light ball. We consider the version where we ...


Only top voted, non community-wiki answers of a minimum length are eligible