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.

learn more… | top users | synonyms

-1
votes
2answers
261 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 ...
1
vote
0answers
185 views

Does this hold?

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 ...
3
votes
1answer
440 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 ...
13
votes
1answer
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 ...
6
votes
2answers
227 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 ...
6
votes
0answers
214 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 ...
25
votes
1answer
625 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 ...
26
votes
4answers
672 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 ...
19
votes
6answers
730 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?
11
votes
2answers
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 ...
5
votes
1answer
266 views

How many points you should draw in the square at least?

There is a square, which side length is $2$, To ensure there exists a triangle in the square, with an area less than $0.5$, how many points should you draw in the square at least. the goal is for all ...
3
votes
0answers
111 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$ ...
11
votes
2answers
242 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 ...
6
votes
2answers
433 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})$$ ...
7
votes
3answers
213 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 ...
5
votes
0answers
264 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 ...
4
votes
2answers
275 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 ...
7
votes
2answers
437 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 ...
5
votes
2answers
382 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, ...
3
votes
1answer
92 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. ...
3
votes
1answer
404 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 ...
3
votes
0answers
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]
2
votes
1answer
203 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 ...
0
votes
1answer
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 ...
4
votes
1answer
128 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 ...
4
votes
0answers
125 views

Limits to the growth of the volume of a union of spheres

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 ...
2
votes
0answers
42 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 ...
2
votes
3answers
679 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?
1
vote
1answer
30 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 ...
1
vote
2answers
58 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 ...
0
votes
0answers
11 views

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