# Tagged Questions

Combinatorial geometry is concerned with combinatorial properties and constructive methods of discrete geometric objects. Questions on this topic are on packing, covering, coloring, folding, symmetry, tiling, partitioning, decomposition, and illumination problems.

264 views

### Tiling problem: 100 by 100 grid and 1 by 8 pieces

Why can't I tile a $100 \times 100$ table with $1$ by $8$ pieces? If we look at the number of tiles, $100^2$ is divisible by $8$. So this does not contradict existence of such tiling. The standard ...
83 views

### Coloring $\mathbb R^n$ with $n$ colors always gives us a color with all distances.

I wanted to share a really cool but simple problem. Consider a coloring of the points of $\mathbb R^n$ with $n$ colors. Prove that there is a color $c$ such that for any $r>0$ there are two points ...
230 views

### Squaring the plane, with consecutive integer squares. And a related arrangement

Q1. I was fiddling around with squaring-the-square type algebraic maths, and came up with a family of arrangements of $n^2$ squares, with sides $1, 2, 3\ldots n^2$ ($n$ odd). Which seems like it would ...
216 views

### Expected Number of Convex Layers and the expected size of a layer for different distributions

It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a ...
632 views

### Can Three Equilateral Triangles with Sidelength $s$ Cover A Unit Square?

A previous question on the site asked for a short proof of the fact that three equilateral triangles with unit side length cannot be arranged to cover a square with unit side lengths. Given the truth ...
677 views

### square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
739 views

### Circle enclosing all but one of $n$ points

It looks like a simple question but it turns out rather difficult to me. Here is the question: Given $n$ points on the plane, can we always draw a circle that includes exactly $n-1$ of them?
470 views

### Is the figure the circumference of a unit circle?

A friend of mine taught me the following question. I've never heard such a strange and interesting question! Qustion: Supposing that a figure $S$, which is constituted by points, satisfies the ...
112 views

### Trajectories on a circular billiards table

This question is related to The case of Captain America's shield: a variation of Alhazen's Billard problem, but more focused. Let the unit disc in the plane be our billiards table, and let $C$ ...
244 views

### Is every shape possible with a snake?

Imagine a 2d snake formed by drawing a horizontal line of length $n$. At integer points along its body, this snake can rotate its body by $90$ degrees either clockwise or counter clockwise. If we ...
435 views

### Positivity of the alternating sum associated to at most five subspaces

Let $V_1 , V_2 , \dots , V_n$ be vector subspaces of $\mathbb{C}^m$ and let $$\alpha = \sum_{r=1}^n (-1)^{r+1} \sum_{ \ i_1 < i_2 < \cdots < i_r } \dim(V_{i_1} \cap \cdots \cap V_{i_r})$$ ...
463 views

### Squaring rectangles

it is a nice high-school exercise to prove that a square can be tiled with n squares if and only if n=1, 4 or is any integer greater or equal to 6. A direct consequence is that any rectangle that can ...
214 views

### Is there a non-constant function $f:\mathbb{R}^2 \to \mathbb{Z}/2\mathbb{Z}$ that sums to 0 on corners of squares?

A problem in the 2009 Putnam asks about functions $f:\mathbb{R}^2 \to \mathbb{R}$ such that whenever $A,B,C,D$ are corners of some square we have $f(A)+f(B)+f(C)+f(D)=0$. Without spoiling the problem ...
267 views

### dissection of rectangle into triangles of the same area

Given $m \times n$ rectangle with area $A$, and $m,n \in \mathbb{N}$. Let $S_k(m,n)$ be the number of way to dissect this rectangle into $k$ non-overlapping triangles whose area is $\frac{A}{k}$. It ...
279 views

### Find the smallest triangulation of the n-dimensional

How to find the smallest triangulation of the n-dimensional cube into n- simplices? It is known, for example, that the 4D cube (the hypercube) may be partitioned into 16 4-simplices, and this is ...
451 views

### Is there a simple proof of Borsuk-Ulam, given Brouwer?

(Brouwer) Any continuous function from a convex compact subset K of a Euclidian space to itself has a fixed point. Given this lemma, is there a simple proof of: (Borsuk-Ulam) Any continuous ...
423 views

### An Olympiad Problem (tiling a rectangle with the L-tetromino)

An L block that is 3 unit blocks high and 2 unit blocks wide . It is true that if an n by m rectangle can be covered by such L blocks with out overlap that we would require an even amount of L blocks, ...
94 views

### Maximum number of acute triangles

Given $n$ points on the plane, no three of which are collinear, what is the maximum number of acute triangles formed by them? [Source: Based on Hungarian competition problem]
414 views

### Combinatorics - Integer sided triangles with integer median

The original problem states: "Given a number N, how many integer-sided triangles $(a,b,c)$ with an integer median $m_{c}$ exist, provided that $a \leq b \leq c \leq N$?". I've managed to get it down ...
94 views

### Is there an equidissection of a unit square involving irrational coordinates?

An equidissection of a square is a dissection into non-overlapping triangles of equal area. Monsky's theorem from 1970 states that if a square is equidissected into $n$ triangles, then $n$ is even. ...
204 views

### minimum lines, maximum points

There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these ...
249 views

### Set of points in the plane which is intersected by every line on the plane and in which no more than K points are collinear

Question Let $K \in \mathbb{N} (K \geq 3)$ and $r \in \mathbb{R}^+$. Either find a set $S$ of points in the plane such that every line on the plane intersects atleast one point in $S$ and that no ...
131 views

### Covering all the edges of a hypercube?

Consider an arbitrary $n$- dimensional hypercube: If we select $n - 1$ corners of that hypercube and highlight all $(n - 2)$ dimensional elements that originate from each of the corners is it ...
125 views

Assume that $x_i$, $i=1,\ldots,m$ are points in $\mathbb{R}^n$, with the maximal distance between any two of them being at most $1$. Define $$a(r)=\mu\Bigl(\bigcup_{i=1}^m B(x_i,r)\Bigr),$$ where $\... 3answers 696 views ### Geometry - Equilateral triangle covered with five circles I have to cover an equilateral triangle (whose sides are 1m long) with 5 identical circles: what's the minimum radius of the circles? 0answers 46 views ### A circle can include all but one of n points, but which one can it be? The answers to the question "Circle enclosing all but one of n points" demonstrate that, given$n$points, it is possible to construct a circle such that all but one of the points is inside the circle ... 1answer 33 views ### Scalene rectangulation of a square: let me count the ways A rectangulation of a square is a dissection of the square$S$into smaller rectangles$R_i$,$i=1,\ldots,n$with the usual caveats:$S = \cup_i R_i$and the interiors of distinct rectangles$R_i,R_j$... 2answers 59 views ### Choosing sets of vectors on a complex sphere Consider a complex$t$dimensional unit sphere. Can we have$t$sets of$2^t$vectors$v_{ij}\in \Bbb C^t$on the sphere where$i=1$to$t$and$j=1$to$2^t$on this with inner products satisfying$...
Strayed on the following question. Assume that $x_{1}$,$\ldots$, $x_{d}\ge0$ with $x_{1}+\ldots+x_{d}=1$ and $y_{1},\ldots,y_{d}\in\mathbb{R}$. Does  \min_{1\le i\ne j\le d}\left(x_{i}+x_{j}-\sqrt{...
### Minimal diameter of a connected subset of $\mathbb{Z}^d$
Let $A \subset \mathbb{Z}^d$ be a connected set of cardinality $|A|$. Let the diameter of the $A$ be defined as the length of the longest path of distinct, nearest neighbor sites which is entirely ...