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

2
votes
1answer
91 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
19 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
51 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 ...
1
vote
0answers
22 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
60 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
79 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
33 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
18 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
58 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
55 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
71 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
180 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
33 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
72 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
35 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
45 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
28 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
24 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. ...
9
votes
2answers
161 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 ...
0
votes
0answers
44 views

Combinatorial approach to calculate determinant

Suppose you have set of $n*n$ matrices with entries from the set $\{1,-1\}$. Then what can be the maximum determinant which you can obtain from such type of matrices.
1
vote
1answer
107 views

there's a circle with area at least n with n+1 lattice points

Prove that we can perform a translation on a circle of area at least $n$, for $n$ being a positive integer, such that there are at least $n+1$ points enclosed or in the boundary of the circle.
8
votes
1answer
89 views

Minimum number of circles with 3 neighbors

It is possible to arrange congruent circles on the plane in such a way that no two circles overlap and each circle adjoins exactly three other circles. The picture shows an example with 16 circles. ...
1
vote
0answers
42 views

How prove $ \frac{2}{\sqrt3}F \geq s-1 $ for convex quadrilateral?

Let $Q$ be any convex quadrilateral of area $F$ and semiperimeter $s$. Suppose that length of any diagonal of $Q$ $ \geq$ length of any side of $Q$ $\geq 1$ How prove $ \frac{2}{\sqrt3}F \geq s-1 ...
5
votes
0answers
62 views

How many unit squares can overlap a given unit square without overlapping each other?

How many unit squares can overlap a given unit square without overlapping each other? @calculus has managed to arrange 7 squares (see this GeogebraTube page). This seems like the maximum ...
5
votes
1answer
73 views

Inequality on length of intervals

Let $n\ge 1$ and $\{I_j\}_{j=1}^{n}$ is a set of non-degenerate subintervals of $[0,1]$. Then show that : $$ \overline\sum \dfrac{1}{|I_j\cup I_k|}\geq n^2$$ Here $\overline\sum$ denotes ...
11
votes
1answer
71 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
1answer
141 views

In a planar 6-point set of diameter at most 2, how many distances can be greater than $\sqrt{2}$?

I found a tough combinatorial geometry problem. Any discussion or advice is helpful. 6 points are on the plane such that any 2 points are at most distance 2 apart. What is the most number of pairs of ...
1
vote
1answer
26 views

Example of an hyperplane arrangement whose bounded region is not star-shaped

Could anyone provide an example of an (essential) hyperplane arrangement whose bounded region is not star-shaped? (Appears as exercise 4.29 in "Oriented Matroids". Hint: six lines in the plane are ...
3
votes
0answers
38 views

How many spherical caps of height $h$ and base circle radius $a$ can cover a sphere of radius $R$?

Question How many spherical caps of height $h$ and base circle radius $a$ can cover a sphere $\mathbb S $ of radius $R \quad (R \gg a)$? What I have thought so far Since the area of the ...
0
votes
0answers
36 views

Coloring a circle

A circular spintop is colored in blue, red and green. Whenever the spintop is rotated 120 degrees, the pattern of colors looks exactly the same, only that blue becomes red, red becomes green and green ...
0
votes
2answers
27 views

Every circle passes through points of all colors

Let $n$ be a positive integer. Is it possible to color every point in the plane in one of $n$ colors so that every (nondegenerate) circle contains points of every color? If we can do the coloring so ...
3
votes
1answer
49 views

Inequality between area and boundary length, $4\pi A \leq L^2 $

Suppose we have a simply connected region $R$ in $\mathbb{R}^2$ with area $A$ and the boundary of $R$ is a curve sufficiently well behaved (say piecewise $C^1$) that we can say it has length $L$. Then ...
4
votes
1answer
103 views

Cutting a pie with a fork

You baked a pie in the shape of a disc, with some cherries spread unevenly on its top. You want to give each of your two children a piece of cake such that: The pieces are congruent - have the same ...
0
votes
1answer
51 views

Beautiful Problem about pairwisely non-similar n-gons.

Let n be an integer (n>2). Show that there exists an infinite number of pairwisely non-similar inscribed n-gons, lengths of all sides and diagonals and areas of each of which are integers. My ...
1
vote
1answer
48 views

How to determine if the given points form a convex irregular Hexagon.

Say I have a collection of points (x,y). From the given points, I want to determine if it forms a convex irregular Hexagon. My goal is to determine that the points I have gathered form an irregular ...
1
vote
1answer
54 views

Arrange 10 points on five lines where each line(intersecting) has exactly 4 points

One possible case is that forming a star and then arranging 10 points on its vertices. Is there any other possible case for this arrangement? If not then how can we prove it mathematically? ...
1
vote
0answers
37 views

Determine the formula for hexagon arrangements.

The puzzle to be solved is similar to a jigsaw but using n regular hexagons of equal size for pieces. The pieces are to be placed within a defined perimeter to create a picture. Q: If we let the ...
0
votes
1answer
21 views

Relating maximal elements of downsets to minimal elements of the complement

Denote by $\mathcal{P}(S)$ the set of non-empty subsets of a finite $S$. Suppose that $A\subset \mathcal{P}(S)$ is a downset, i.e., every subset $Q$ of any $P\in A$ is also contained in $A$. We can ...
4
votes
0answers
36 views

Area covered by one disk more than by two disks

Given are three unit disks on the plane. Let $A$ be the area of the plane covered by exactly $1$ disk. Let $B$ be the area of the plane covered by exactly $2$ disks. Prove that $A\geq B$. ...
2
votes
1answer
37 views

Polygons with fixed number of axes of symmetry

Let $k$ be a positive integer. Suppose a polygon has exactly $k$ axes of symmetry. How many sides may the polygon have? A regular $n$-gon has $n$ axes of symmetry, so one answer is $k$. What are ...
4
votes
1answer
40 views

Repeated projection of points onto lines

Consider a point $P$ on the Euclidean plane, and lines $l_1,l_2,\ldots,l_n$. Project $P$ onto $l_1$. Then project the resulting point onto $l_2$. Then project the resulting point onto $l_3$, and so ...
6
votes
1answer
143 views

Partition rectangle into finite number of squares

For what positive real numbers $x,y$ can an $x\times y$ rectangle be partitioned into a finite number of squares? When $\dfrac{x}{y}$ is a rational number, it is not hard to see that we can partition ...
0
votes
3answers
37 views

Is there a theorem or axiom which shows that permutations of step sequences through a lattice graph result in the same destination?

I have been searching for a theorem, lemma, or even an axiom which shows that the permutations of a step sequence in Taxicab Geometry result in the same destination in such a lattice graph. To ...
10
votes
2answers
169 views

Partitioning the plane into three sets each intersecting the vertices of every square with side 1?

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? (I mean all squares of side-length 1, not just those with ...
5
votes
1answer
64 views

Bounded area for any triangle formed by polygons

Let $P_1,P_2,P_3$ be closed polygons on the plane. Suppose that for any points $A\in P_1$ (meaning $A$ can be inside or on the boudary of $P_1$), $B\in P_2,C\in P_3$, we have $[ABC]\leq 1$. Is it ...
3
votes
0answers
55 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]
8
votes
0answers
49 views

Ratio of product from one point and minimum distance

Given points $A_0,A_1,\ldots,A_n$ in the plane, let $m$ denote the minimum distance among any two points. What is the minimum value of $$\dfrac{|A_0A_1|\cdot|A_0A_2|\cdot\ldots\cdot|A_0A_n|}{m^n}?$$ ...
2
votes
1answer
91 views

partition of convex n-gon with triangles.

A convex $n$-gon is partitioned into $n-2$ triangles with non-intersecting diagonals. For each vertex of the original polygon, odd number of the partitioning triangles share that vertex. Is it ...
2
votes
1answer
34 views

Reflection to get within convex polygon

Let $P$ be a convex polygon, and let $A_1$ be a point on the same plane as $P$. Prove that we can find an integer $n$, and points $A_2,A_3,\ldots,A_n$, such that $A_{i+1}$ is a reflection of $A_i$ ...
1
vote
0answers
47 views

Number of vectors which are $\alpha$ angle apart

Let, $A\subseteq\{z=(z_1,z_2)\in\mathbb{C}^2:|z|^2=|z_1|^2+|z_2|^2=1\}$ such that any two vectors in $A$ have angle between them $\ge\alpha$ for some $0<\alpha<1$. I want to prove that ...