All Questions
2,368 questions
32
votes
0
answers
1k
views
Minimal number of intersections in a convex $n$-gon?
For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
- 1,474
31
votes
3
answers
10k
views
Cutting a rectangle into an odd number of congruent non-rectangular pieces
We are interested in tiling a rectangle with copies of a single tile (rotations and reflections are allowed). This is very easy to do, by cutting the rectangle into smaller rectangles.
What happens ...
- 1,110
31
votes
2
answers
1k
views
The Sylvester-Gallai theorem over $p$-adic fields
The famous Sylvester-Gallai theorem states that for any finite set $X$ of points in the plane $\mathbf{R}^2$, not all on a line, there is a line passing through exactly two points of $X$.
What ...
- 20.8k
31
votes
5
answers
1k
views
Fair cutting of the plane with lines
An infinite countable family $\cal{L}$ of straight lines in the plane $\mathbb{R}^2$ forms a fair cutting of the plane if the following conditions are satisfied:
$\bullet$ No circle intersects ...
- 7,276
31
votes
2
answers
3k
views
Is it possible to dissect a disk into congruent pieces, so that a neighborhood of the origin is contained within a single piece?
Problem: is it possible to dissect the interior of a circle into a finite number of congruent pieces (mirror images are fine) such that some neighbourhood of the origin is contained in just one of the ...
- 375
30
votes
5
answers
9k
views
Six yolks in a bowl: Why not optimal circle packing? [closed]
Making soufflé tonight, I wondered if the six yolks took on the
optimal circle packing configuration.
They do not. It is only with seven congruent circles that the optimal
packing places one in the ...
- 151k
30
votes
5
answers
16k
views
How to check if a box fits in a box?
How could I calculate if a rectangular cuboid fits in an other rectangular cuboid, it may rotate or be placed in any way inside the bigger one.
For example would, (650,220,55) fit in (590,290,160), ...
- 429
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
29
votes
3
answers
2k
views
Growing random trees on a lattice $\rightarrow$ Voronoi diagrams
Imagine growing trees from $k$ seeds on a square $n \times n$ region
of $\mathbb{Z}^2$.
At each step, a unit-length edge $e$ between two points of
$\mathbb{Z}^2$ is added.
The edge $e$ is chosen ...
- 151k
28
votes
5
answers
2k
views
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
- 4,484
28
votes
6
answers
2k
views
How fast are a ruler and compass?
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 ...
- 513
28
votes
2
answers
3k
views
Erdős-Szekeres for first differences
The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$
real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however,
that we want to find a subsequence which is not ...
- 23k
28
votes
3
answers
2k
views
Is the ratio Perimeter/Area for a finite union of unit squares at most 4?
Update: As I have just learned, this is called Keleti's perimeter area conjecture.
Prove that if H is the union of a finite number of unit squares in the plane, then the ratio of the perimeter and ...
- 18.7k
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
27
votes
3
answers
3k
views
A question about subsets of plane
Is there a subset $X$ of plane with two points $x, y$ such that each one of $X \setminus \{x\}$, $X \setminus \{y\}$ is isometric to $X$? I tried hard to construct a counterexample but failed.
Sorry ...
- 271
27
votes
8
answers
1k
views
Area-differences for lattice triangles in a checkerboard
For positive integers $m$ and $n$, what is the integral of the function $(-1)^{\lfloor x \rfloor + \lfloor y \rfloor}$ on the triangle with vertices $(0,0)$, $(m,0)$, and $(0,n)$?
Pictorially, we are ...
- 19.7k
27
votes
2
answers
891
views
Careless packing
The sequence $\frac{1}{2}, \frac{1}{2\cdot 2}, \frac{1}{3\cdot 4}, \frac{1}{4\cdot 6}, \frac{1}{5\cdot 8}, \frac{1}{6\cdot 10},\ldots$ has a curious property, as follows:
a) the series with these ...
- 17.6k
27
votes
6
answers
2k
views
When shorter means smaller?
Assume a convex figure $F\subset \mathbb R^2$ satisfies the following property: if $f:F\to \mathbb R^2$ is a distance-non-increasing map then its image $f(F)$ is congruent to a subset of $F$.
Is it ...
26
votes
7
answers
3k
views
What's that shape? Inferring a 3D shape from random shadows
Let $P$ be a bounded, simply connected region of $\mathbb{R}^3$.
$P$ could be a polyhedron, or a smooth shape, or an arbitrary shape;
I'll assume below that $P$ is a (non-degenerate, perhaps non-...
- 151k
26
votes
3
answers
1k
views
Largest possible volume of the convex hull of a curve of unit length
What is the largest possible volume of the convex hull of an open/closed curve of unit length in $\mathbb{R}^3$?
- 6,819
26
votes
3
answers
3k
views
Research trends in geometry of numbers?
Geometry of numbers was initiated by Hermann Minkowski roughly a hundred years ago. At its heart is the relation between lattices (the group, not the poset) and convex bodies. One of its fundamental ...
- 907
26
votes
2
answers
2k
views
Random points on the unit sphere
Suppose you have $n$ points picked uniformly at random on the surface of $\mathbb{S}^d,$ and let the volume of the convex hull of these points be $V_{n, d}.$ Clearly, $V_{n, d}$ converges to the ...
- 96.4k
26
votes
0
answers
512
views
A non-self-intersecting unit side length polygon in a unit square has odd number of sides unless it is the square itself
This is the same question as here in SE.
I have a conjecture, it is like this:
Suppose there is a non-self-intersecting polygon lies inside a closed square of length $1$. The polygon has every side ...
- 843
26
votes
0
answers
359
views
Can 4-space be partitioned into Klein bottles?
It is known that $\mathbb{R}^3$ can be partitioned into disjoint circles,
or into disjoint unit circles, or into congruent copies of a real-analytic curve
(Is it possible to partition $\mathbb R^3$ ...
- 151k
25
votes
5
answers
3k
views
Sperner Lemma Applications
I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of ...
25
votes
3
answers
994
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
- 513
25
votes
3
answers
945
views
Are there arbitrarily large families of lines in $\Bbb R^3$ with average angle $\ge \pi/3$?
Question: Can I have an arbitrarily large finite family of lines $\ell_1,\dotsc,\ell_n\subset\Bbb R^3$ so that the average angle between two (distinct) lines is $\ge \pi/3$?
We can assume that all ...
- 13.6k
25
votes
1
answer
2k
views
Polyomino that can tile itself
Find all polyomino $P$ such that we can tile $nP$ with $n^2$ copies of $P$ for all $n\in \mathbb{N}$. ($nP$ is a polynomino similar to $P$ with scale factor $n$)
I conjecture that there are only $4$ ...
- 1,462
25
votes
1
answer
667
views
Is there a short proof of the decidability of Kepler's Conjecture?
I've believed that the answer is "yes" for years, as suggested in various sources with reference to Tóth's work. For example, the Wikipedia article for Kepler Conjecture says:
The next step toward ...
- 353
25
votes
1
answer
1k
views
Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$
The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (...
- 32.5k
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 363
25
votes
1
answer
513
views
Is there an inventory of closed billiard paths in a regular tetrahedron?
Conway found a closed billiard-ball trajectory in a regular tetrahedron:
Image: Izidor Hafner
Since then Bedaride and Rao
Bedaride, Nicolas, and Michael Rao. "Regular simplices and periodic ...
- 151k
25
votes
1
answer
3k
views
Number of hypercube unfoldings
While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...
- 10.7k
25
votes
3
answers
2k
views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 33.8k
24
votes
3
answers
3k
views
Polyomino that can cover an arbitrarily large square but not the entire plane
https://userpages.monmouth.com/~colonel/nrectcover/index.html
For a polyomino with no holes that cannot tile the plane, we may ask what are the maximal rectangles and infinite strips that it can ...
- 359
24
votes
3
answers
3k
views
Can a unit square be cut into rectangles that tile a rectangle with irrational sides?
For arbitrary positive integers $m$ and $n$, if we dissect a unit square into an $m\times n$ rectangular grid of $1/m\times 1/n$ rectangles, we can reassemble these $mn$ rectangles into an $n/m\times ...
- 2,437
24
votes
5
answers
3k
views
What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs?
This problem was posed in March 2010 at G4G9 in a talk by the Japanese mathematician Hirokazu "Iwahiro" Iwasawa. He claims there is a simple proof that N > 10, though he did not share it with the ...
- 349
24
votes
3
answers
1k
views
Tetrahedron insphere iteration
I know that iterating the following incircle construction approaches an equilateral triangle in the limit:
Starting with any triangle $T$, one forms $T'$ by connecting ...
- 151k
24
votes
6
answers
3k
views
Shortest grid-graph paths with random diagonal shortcuts
Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of ...
- 151k
24
votes
8
answers
4k
views
Higher-dimensional Catalan numbers?
One could imagine defining various notions of higher-dimensional Catalan numbers,
by generalizing objects they count.
For example, because the Catalan numbers count the triangulations of convex ...
- 151k
24
votes
3
answers
4k
views
What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
- 4,922
24
votes
3
answers
2k
views
Gauss-Bonnet Theorem for Graphs?
One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an $n$-cycle has $\chi = 0$ and $K_4$ has $\chi=-2$.
Is there an analog for the ...
- 151k
24
votes
2
answers
1k
views
A geometric Ramsey problem
The following problem seems like one to which the answer could well be known: if so, I'd be interested to have a reference.
How large does n have to be such that among any n points in the plane you ...
- 29k
24
votes
1
answer
770
views
Given a group action on a simplex, can I always find a fundamental region that is a simplex?
Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...
- 13.6k
24
votes
1
answer
2k
views
Building a genus-$n$ torus from cubes
I wonder if this has been studied:
What is the fewest number of unit cubes
from which one can build an $n$-toroid?
The cubes must be glued face-to-face,
and the boundary of the resulting object ...
- 151k
24
votes
1
answer
622
views
Polytope where each vertex belongs to all but two facets
Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
- 4,653
24
votes
2
answers
754
views
Expected number of vertices of a hypercube slice -- is this new/interesting?
I am a (mostly) amateur mathematician, but my education and work have featured a lot of mathematics, and recently I bumped into a mathematical problem for which I can find no references, and I am ...
- 241
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
23
votes
1
answer
1k
views
Covering of a surface of a cube $n\times n \times n$ by pieces of paper $1\times 6$
When I was too young one of my problems was in the list of problems of All-Russian Olympiad. The problem is the following:
Problem. We have a surface of a cube $n\times n \times n$ such that each ...
- 508
23
votes
3
answers
2k
views
Rolling-ball game
The analyses
in two recent MO questions
("recent" with respect to the original posting in 2011),
"Rolling a random walk on a sphere"
and
"Maneuvering with limited moves on $S^2$,"
suggest a Rolling-...
- 151k