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

3
votes
1answer
29 views

Intersection of Random Subspace and Hypercube

Suppose that $A \subset \mathbb{R}^n$ is a random linear subspace of dimension $k < n$. I am interested in the event that $A$ intersects the hypercube $[-1,\ 1]^n$ at a specific face. In other ...
1
vote
2answers
58 views

Building a box from smaller boxes

John has 77 boxes each having dimensions 3x3x1. Is it possible for John to build one big box with dimensions 7x9x11? I'm leaning towards no, but I would like others opinion.
15
votes
1answer
239 views

Hypercube and Hyperspheres

Let $n,k\in\mathbb{N}$. In this problem, the geometry of $\mathbb{R}^n$ is the usual Euclidean geometry. The lattice hypercube $ Q(n,k)$ is defined to be the set $ \{1,2,...,k\}^n ...
0
votes
0answers
8 views

Number of triangle that can be formed from l,m,n set of parallel lines.

If we are given $\{l,m,n\}$ set of parallel lines how many triangle can be formed from them after they intersect.
2
votes
1answer
60 views

sample variance of regular polygon upon superimposition of vertices

Given, the vertices of a regular polygon, the centroid here would be the sample mean of the vertices and we assume it to be at the origin. The distance from each vertex to centroid is ...
10
votes
4answers
177 views

A circle with $500$ points in its interior

Given any $1000$ points in the plane, show that there is a circle which contains exactly $500$ of the points in its interior, and none on its circumference. How do I approach this problem? I feel ...
0
votes
0answers
42 views

Countably Infinitely Many Points in a Euclidean Space

Do there exist $d\in\mathbb{N}$ such that there are pairwise distinct points $x_1$, $y_1$, $x_2$, $y_2$, $\ldots$ in $\mathbb{R}^d$ such that (i) $\left\|x_i-y_i\right\|_2 >1$ for ...
0
votes
0answers
13 views

Configurations of eleven (or more) points in the Euclidean plane, such that out of any four there is a pair at unit distance.

Inspired by this question, I was wondering the following: What is the maximal size of a subset $C$ of the Euclidean plane such that out of any four points in $C$ there are two at unit distance ...
1
vote
1answer
29 views

The number of ways to draw boundaries of constituencies, subject to constraints

A state comprises 45 counties arranged as 5 rows, running east and west, of 9 counties each, the nine colums of 5 running north and south. They're connected horizontally and vertically, i.e. ...
0
votes
0answers
24 views

Proof for formula that uses recursion to find combinations.

In a workbook, there this formula: Number of Combinations = $(m-1)[(m-1)^{n-1}+(-1)^n]$. This formula found the number of n-pointed stars colored with m colors without having adjacent points be of the ...
2
votes
0answers
29 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
1
vote
1answer
64 views

Is there a mathematical way to determine a solution for puzzle games?

Or more specifically, a mathematical way to determine HOW to solve a puzzle game. Take a look at this screenshot of a puzzle game "The Talos Principle." As you can see, the purpose of this ...
2
votes
0answers
33 views

An art gallery problem

An art gallery has the shape of a simple $n$-gon. Find the minimum number of watchmen needed to survey the building, no matter how complicated its shape be. I failed to solve the problem. Please help ...
2
votes
1answer
98 views

Prove: $m$ balls in $\mathbb{R^3}$ cut $\mathbb{R^3}$ into less than $m^3$ connected components.

I need to prove or at least to understand why $m$ balls in $\mathbb{R^3}$ cut $\mathbb{R^3}$ into less than $m^3$ connected components. But I've no idea how to deal with it. I even tried to draw it ...
2
votes
0answers
51 views

Fill a rectangle with squares

How many ways are there to fill a $m\times n$ rectangles with squares that have integer side lengths. Both $m$ and $n$ are integers.
2
votes
1answer
52 views

Dominoes on chessboard

A $2016\times 2016$ chessboard is tiled with $2 \times 1$ dominoes. I can prove that there is a grid line that pass through at least $505$ dominoes. But how to prove or disprove that there is a ...
2
votes
1answer
35 views

Maximal Triangle Partitioning in n lines

Recently I was given the following problem at work: Given a 5 pointed star, draw two straight lines through it so that there are 10 minimal triangles within the drawing. It took some work but I ...
2
votes
0answers
61 views

Red and blue balls lined up

On a plane, is it possible to arrange $6$ red points and $6$ blue points such that No $2$ points coincide. For any line containing two or more points, not all the points on that line are of the same ...
2
votes
0answers
40 views

Neighbor-full partition of $\{0,1\}^n$

What is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements? (which we call $k(n)$) We say $A$ and $B$ are neighbors if their ...
17
votes
1answer
231 views

How many planar arrangements of $n$ circles?

Is there a known formula or recursion for the number of distinct arrangements of $n$ distinct circles in a plane, where two arrangements are regarded as distinct unless one can be obtained from the ...
2
votes
0answers
76 views

Is it possible to choose 10 points from 20000 with that property?

A set of $20000$ points is chosen in a ball of radius $6$ in $ \mathbb{R}^3 $. Do there exist $10$ ones of these points s. t. all the distances between them are less than or equal to $1$?
1
vote
1answer
27 views

Hexagon Numbering Problem

So in the above hexagon figure, I have to arrange 1 to 7, inclusive, into the circles such that the three dark red triangles have the same sum. How many distinct arrangements can there be?
21
votes
3answers
395 views

Maximum $C$ such that every shape in $\Bbb R^2$ with area $<C$ can be placed to avoid $\Bbb Z^2$

For $C=1$, it has been proved here that every shape in the plane having area less than $1$ can be translated and rotated so that it does not touch any element of $\mathbb Z^2$. (In fact, for $C=1$, ...
1
vote
1answer
35 views

Combinatorial optimization problem

I'm having trouble writing a general algorithm for what at first glance appears to be a simple problem. If I have a volume $V_{required}$ that can be made from two smaller, different volumes how can ...
2
votes
1answer
28 views

Minimum number of circular segments.

Let K be any natural number. Consider the unit square, and the circle of diameter 1 inside of the square. We then consider circular segments of area $\frac{1}{2K}$ and claim that there exists a ...
2
votes
2answers
127 views

A question about $ (2 \times 3) $-rectangles.

The following is a problem from TopCoder: Problem. Given the width and the height of a rectangular grid, return the total number of non-square rectangles that can be found on the grid. For ...
3
votes
1answer
66 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. ...
10
votes
1answer
182 views

Number of ways to dissect a square into triangles of equal area

Monsky's theorem states that it is impossible to dissect a square into an odd number of triangles of equal area. If $n$ is an even integer, I am interested in the number of ways of dissecting a ...
8
votes
2answers
232 views

Do two closed subsets of $[0, 1]$ with measure $\frac{1}{2}$ intersect?

Let $A$ and $B$ be two closed subsets of $[0,1]$, each with a length of $1/2$. Is it always true that $A\cap B\neq \emptyset$? My intuition is yes, because: Either they intersect in their interior; ...
2
votes
1answer
275 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 ...
0
votes
0answers
29 views

Can you partition a rectangle into exactly 3 congruent non-rectangular parts?

Recently I came upon the following result: Theorem (*): Let $n$ be a positive integer not equal to $1,3,5,7,9$. Then it is possible to partition a rectangle into exactly $n$ congruent non-rectangular ...
2
votes
0answers
58 views

Why is unit circle not sufficient to bound the partial sums?

I want to find vectors $\textbf{v}_1, \dots,\textbf{v}_n$ in $\mathbb{R}^2$ with that $\sum_{i=1}^n\textbf{v}_i=\textbf{0}$ and $\Vert \textbf{v}_i\Vert\leq 1$ for all $i=1,\dots,n$, such that for ...
3
votes
1answer
76 views

Cardinality of a minimal open cover of the disc

Consider $D_1^2(0)=\{x\in\Bbb R^n: ||x||_2\leq 1\}$ and let $\epsilon>0$. Consider the open cover $\mathcal{O}=\{B_\epsilon^2(x):x\in D_1^2(0)\}$ of $D_1^2(0)$. What is the minimum cardinality ...
19
votes
0answers
388 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 ...
1
vote
0answers
27 views

Lattice points-Triangle

We have a triangle $ T $ with vertices at the $ \mathbb{Z} \times \mathbb{Z} $ grid . Now, consider the surface $ 2T= \{x \in \mathbb{R}^2 : \frac{x}{2} \in T \} $ ( so, double $ T $ ). Is it possible ...
2
votes
0answers
72 views

Number of Points Inside a Rectangle

This question is from a Japanese contest: Let $S$ be a set of 2002 points in the coordinate plane, no two of which have the same $x$- or $y$- coordinate. For any two points $P,Q$ in $S$ consider ...
3
votes
1answer
103 views

Sum of the perimeters of the squares intersecting the main diagonal

This question is from an old Russian contest: The unit square $ABCD$ is divided into $10^{12}$ smaller squares (not necessarily equal). Prove that the sum of the perimeters of all the smaller ...
-1
votes
1answer
37 views

Three vertices of a n-gon [closed]

We choose three vertices of a convex n-gon, which form a triangle. If the number of ways we can choose the three vertices so that no sides of the triangle coincide with any sides of the n-gon is 7n, ...
1
vote
0answers
22 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
6
votes
1answer
85 views

When is a graph a triangulation of a polygon?

This question came up in an undergraduate math club meeting yesterday. As we know, a graph is planar if it can be embedded in the plane with no edges crossing. A famous necessary and sufficient ...
1
vote
1answer
64 views

Combinatorics question about alternately-coloured diagonal halves of sides of a cube

Diagonal halves of each side of a cube are painted in alternate colours. Let the vertex at which such a half forms a right angle be its base vertex. What is the minimum number and the maximum number ...
3
votes
1answer
79 views

To determine number of arrangements of 4 letters in a word so that the transitions remains conserved

A 10 letter word is composed of $A,\ B,\ C,\ D$. The problem is to find the number of arrangements of these alphabets which could lead to fixed number of transitions between each pair of alphabets. ...
8
votes
1answer
182 views

Points “seeing” each other in a loop

For two points $P,Q$ with integer coordinates in $2$ dimensions, we say that $P$ "sees" $Q$ iff the segment $PQ$ contains no other points with integer coordinates. Do there exist points ...
0
votes
0answers
44 views

How many regions created by lines,circles, lines and circles, ellipses, spheres, planes from cutting?

I came up with a fantastic exercise (well not so fantastic but I think its a good generalization of classic things). In each of the following cases, find (1) the maximum number of points of ...
2
votes
2answers
81 views

Placing dominoes on a chessboard

Find the smallest number of dominoes we must place on an $8×8$ chessboard, so that in every $2×2$ square, at least one of the squares is covered by a domino. I am getting confused again and again as I ...
1
vote
3answers
46 views

Cutting and reassembling squares

Is there a general way to cut a square into polygonal pieces so that the pieces can be assembled into n equally sized squares for each n? For example, 2 and 4 and n=k^2 is obvious (2 by the diagonals ...
0
votes
1answer
59 views

Prove that every convex polygon with area $1$ is contained in a parallelogram of area $\frac{4}{3}$

Prove that every convex polygon with area $1$ is contained in a parallelogram of area $\frac{4}{3}$ I can only show that polygon is contained in a rectangle of area $2$.
1
vote
0answers
45 views

How many 100 sq km bounding boxes cover the surface are of the earth.

I need to figure out how many 100 square km bounding boxes cover the surface area of the earth. I'm trying to use the Instagram API to download data. Their API supports a lat/long with a maximum ...
3
votes
1answer
38 views

Generating M well separated points in an n-dimensional hypercube

I want to generate M n-dimensional points constrained inside a hypercube such that the points are relatively well separated. I'm playing around with this using a scripting language like R or python. ...
11
votes
2answers
182 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 ...