# Tagged Questions

**69**

votes

**3**answers

2k views

### What do the stable homotopy groups of spheres say about the combinatorics of finite sets?

The Barratt-Priddy-Quillen(-Segal) theorem says that the following spaces are homotopy equivalent in an (essentially) canonical way:
$\Omega^\infty S^\infty:=\varinjlim~ \Omega^nS^n$
...

**56**

votes

**17**answers

36k views

### Google question: In a country in which people only want boys [closed]

Hi all!
Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:
...

**55**

votes

**5**answers

2k views

### Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer.
A polyomino is usually defined to ...

**53**

votes

**6**answers

5k views

### Existence of a zero-sum subset

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...

**51**

votes

**1**answer

3k views

### What is the amplituhedron?

The paper ”Scattering Amplitudes and the Positive Grassmannian” by Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka, introduces ...

**49**

votes

**3**answers

2k views

### Flipping coins on a budget

A coin is flipped $n$ times and you win if it comes up heads at least $k$ times. The coin is unusual in that you're allowed to pick the probability $p_i$ that it comes up heads on the $i$th flip, ...

**47**

votes

**8**answers

6k views

### The “sensitivity” of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).
Let $C$ be a ...

**45**

votes

**9**answers

7k views

### Does War have infinite expected length?

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 ...

**45**

votes

**7**answers

3k views

### Euler-Maclaurin formula and Riemann-Roch

Let $Df$ denote the derivative of a function $f(x)$ and $\bigtriangledown f=f(x)-f(x-1)$ be the discrete derivative. Using the Taylor series expansion for $f(x-1)$, we easily get $\bigtriangledown = ...

**45**

votes

**2**answers

2k views

### vector balancing problem

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.
This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...

**45**

votes

**1**answer

2k views

### A = B (but not quite); 3-d arrays with multiple recurrences

Many years ago, I discovered the remarkable array (apparently originally discovered by Ramanujan)
1
1 3
2 10 15
6 40 105 105
24 196 700 1260 945
...

**43**

votes

**8**answers

2k views

### Puzzle on deleting k bits from binary vectors of length 3k

Question also asked at http://math.stackexchange.com/questions/497343/deletion-puzzle.
Consider all $2^n$ different binary vectors of length $n$ and assume $n$ is an integer multiple of $3$. You are ...

**41**

votes

**7**answers

6k views

### What is Lagrange Inversion good for?

I am planning an introductory combinatorics course (mixed grad-undergrad) and am trying to decide whether it is worth budgeting a day for Lagrange inversion. The reason I hesitate is that I know of ...

**41**

votes

**8**answers

2k views

### What are some examples of interesting uses of the theory of combinatorial species?

This is a question I've asked myself a couple of times before, but its appearance on MO is somewhat motivated by this thread, and sigfpe's comment to Pete Clark's answer.
I've often heard it claimed ...

**40**

votes

**5**answers

6k views

### Identifying poisoned wines

The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned ...

**40**

votes

**2**answers

2k views

### Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$

At MIT all departments have numbers, and math is 18. Last year MIT
math majors produced a tee shirt that said ${i\choose 18}$ ("I choose
18") on the front, and on the back
$$ ...

**39**

votes

**6**answers

4k views

### Why do Bernoulli numbers arise everywhere?

I have seen Bernoulli numbers many times, and sometimes very surprisingly. They appear in my textbook on complex analysis, in algebraic topology, and of course, number theory. Things like the criteria ...

**38**

votes

**3**answers

4k views

### cube + cube + cube = cube

The following identity is a bit isolated in the arithmetics of natural integers
$$3^3+4^3+5^3=6^3.$$
Let $K_6$ be a cube whose side has length $6$. We view it as the union of $216$ elementary unit ...

**38**

votes

**8**answers

4k views

### 1 rectangle <= 4 squares

Almost 25 years ago a professor at Indiana U showed me the following problem:
given a map $\mathbb{Z}^2\rightarrow\mathbb{R}$ such that the sum inside every square (parallel to the axes) is $\leq1$ ...

**38**

votes

**2**answers

3k views

### Collapsible group words

What is the length $f(n)$ of the shortest nontrivial group word $w_n$ in $x_1,\ldots,x_n$ that collapses to $1$ when we substitute $x_i=1$ for any $i$?
For example, $f(2)=4$, with the commutator ...

**37**

votes

**7**answers

3k views

### Conway's game of life for random initial position

What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...

**37**

votes

**2**answers

5k views

### Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly Orthogonal to Morse
!
Harold Calvin Marston Morse (24 March ...

**37**

votes

**2**answers

1k views

### Numbers that are generic w.r.t. exponentiation

This is a follow-up to my old question Number of distinct values taken by $x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x$ with parentheses inserted in all possible ways.
...

**36**

votes

**6**answers

3k views

### Non-enumerative proof that there are many derangements?

Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exclusion principle ...

**36**

votes

**1**answer

3k views

### Why are there 1024 Hamiltonian cycles on an icosahedron?

Fix one edge $e$ of the graph (1-skeleton) of an icosahedron.
By a computer search, I found that there are 1024 Hamiltonian cycles that include $e$.
[But see edit below re directed vs. undirected!]
...

**36**

votes

**3**answers

5k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an ...

**35**

votes

**6**answers

2k views

### Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...

**35**

votes

**4**answers

3k views

### Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...

**35**

votes

**2**answers

912 views

### Is there an analog of Sperner's lemma for the Hopf invariant?

Recall that Sperner's lemma is essentially a combinatorial version of the topological statement "A map from $S^n$ to $S^n$ with degree one cannot be nullhomotopic."
My question is, does there exist ...

**34**

votes

**4**answers

1k views

### A family of words counted by the Catalan numbers

In recent work with Michael Albert and Nik Ruškuc, a family of words has arisen which is counted by the Catalan numbers. I've looked at Richard Stanley's Catalan exercises in EC2 and his Catalan ...

**34**

votes

**1**answer

859 views

### Implications of non-negativity of coefficients of arbitrary Kazhdan-Lusztig polynomials?

In their seminal 1979 paper here,
Kazhdan and Lusztig studied an arbitrary Coxeter group $(W,S)$ and the corresponding Iwahori-Hecke algebra. In particular they showed how to pass from a standard ...

**33**

votes

**12**answers

5k views

### Combinatorial results without known combinatorial proofs

Stanley likes to keep a list of combinatorial results for which there is no known combinatorial proof. For example, until recently I believe the explicit enumeration of the de Brujin sequences fell ...

**33**

votes

**3**answers

3k views

### the following inequality is true，but I can't prove it

The inequality is
\begin{equation*}
\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)
\end{equation*}
for all integer $d\geq 1$. I use computer to verify ...

**33**

votes

**9**answers

3k views

### What proportion of chess positions that one can set up on the board, using a legal collection of pieces, can actually arise in a legal chess game?

Many chess positions that one may easily set up on a chess board
are impossible to achieve in a game of legal moves. For example,
among the impossible situations would be:
A position in which both ...

**33**

votes

**1**answer

1k views

### Wanted: a “Coq for the working mathematician”

Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar ...

**32**

votes

**33**answers

4k views

### Structures that turn out to exhibit a symmetry even though their definition doesn't

Sometimes (often?) a structure depending on several parameters turns out to be symmetric w.r.t. interchanging two of the parameters, even though the definition gives a priori no clue of that symmetry. ...

**32**

votes

**15**answers

6k views

### Strong induction without a base case

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication
"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."
for ...

**32**

votes

**5**answers

2k views

### Icon Arrangement on Desktop

Story
I was bored sitting in front of my computer and using a rectangle to select icons on my screen. I could select $1$, $2$, $3$, $4$, but not $5$ icons.
(Black squares are the icons. Note that ...

**32**

votes

**7**answers

2k views

### The shortest path in first passage percolation

Consider a square planar grid. (The vertices are pair of points in the plane with integer coordinates and two vertices are adjacent if they agree in one coordinate and differ by one in the other.)
...

**31**

votes

**8**answers

4k views

### Help with a double sum, please

Here is a double series I have been having trouble evaluating:
$$S=\sum_{k=0}^{m}\sum_{j=0}^{k+m-1}(-1)^{k}{m \choose ...

**31**

votes

**5**answers

2k views

### Why do wedges of spheres often appear in combinatorics?

Robin Forman writes in "A User's Guide to Discrete Morse Theory":
The reader should not get the
impression that the homotopy type of a
CW complex is determined by the number
of cells of each ...

**31**

votes

**2**answers

1k views

### A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...

**31**

votes

**4**answers

2k views

### Integer-valued factorial ratios

This historical question recalls
Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation
Chebyshev used the factorial ratio sequence
$$
...

**31**

votes

**1**answer

2k views

### orders of products of permutations

Let $p$ be a prime, $n\gg p$ not divisible by $p$ (say, $n>2^{2^p}$). Are there two permutations $a, b$ of the set $\{1,...,n\}$ which together act transitively on $\{1,2,...,n\}$ and such that all ...

**30**

votes

**4**answers

2k views

### Verifying the correctness of a Sudoku solution

A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...

**30**

votes

**1**answer

3k views

### Are the norms of graphs dense in any interval?

It is known that there is a gap between 2 and the next largest norm of a graph.
Is there an interval of the real line in which norms of graphs are dense?

**30**

votes

**4**answers

1k views

### Tiling A Rectangle With A Hint of Magic

Here's a a famous problem:
If a rectangle $R$ is tiled by rectangles $T_i$ each of which has at least one integer sidelength, then the tiled rectangle $R$ has at least one integer side length.
...

**30**

votes

**4**answers

2k views

### “Circular” domination in ${\mathbb R}^4$

The following problem is related to (and motivated by) the first open case of this MO question. It is difficult to believe that this is a hard problem; and yet, I do not have a solution.
For two ...

**30**

votes

**2**answers

1k views

### What is the oriented Fano plane?

One way to remember the multiplication table of the octonions is to use the following diagram (which I got from John Baez's online paper): if $(e_i,e_j,e_k)$ is one of the lines listed according to ...

**30**

votes

**2**answers

2k views

### Difficult examples for Frankl's union-closed conjecture

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there ...