Questions tagged [combinatorial-geometry]

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.

Filter by
Sorted by
Tagged with
0
votes
1answer
21 views

Configuration of high-dimensional spheres

Let $S = \{S_1, \dots ,S_n\}$ be a finite set of $d$-dimensional spheres, and let $E$ be a combination of intersections between them, where an intersection is a rule of the form $S_i \cap S_j \subset ...
0
votes
1answer
25 views

A combinatorial problem in geometry (inequality)

In their 1935 paper, A combinatorial problem in geometry, Erdos and Szekeres prove Ramsey's Theorem. One of the cases is: If $i = 1$, the theorem holds for every $k$ and $l$. For if we select out ...
0
votes
1answer
56 views

Proof of the Polynomial Ham-Sandwich Theorem

I'm currently reading through Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique and I have what might be a very silly question, but I'm not ...
4
votes
0answers
69 views

Tiling a rectangle with both rational and irrational sided squares

We define a 'tiling of rectangle with squares' as the process of dividing the rectangle into finitely many squares so that they do not overlap and cover up the whole rectangle. Here is my question: ...
2
votes
0answers
54 views

In an $n\times n$ grid with diagonals, how to count number of paths along the diagonals?

Given an $n\times n$ grid, with two diagonals in each unit square. I am interested in the number of (directed) paths or walks from one side of the grid to the opposite side, walking along the ...
2
votes
0answers
42 views

Show that there exist distinct positive integers $a,b,c,d$ such that all of these three conditions are satisfied simultaneously.

Question: Let $n\in\mathbb{N}$. We colour every positive integer by one of $n$ colours. Show that there exist distinct positive integers $a,b,c,d$ such that: (i) they are of same colour (ii)...
1
vote
1answer
30 views

Show that there exists a rectangle such that each of its four vertices are of same colour and its sides are parallel to the X and Y axes.

Question: Let $n\in\mathbb{N}$. We colour every lattice point on X-Y plane by one of $n$ colours. Show that there exists a rectangle such that each of its four vertices are of same colour and its ...
1
vote
0answers
26 views

Given a specific number of rectangles, determine their size for them to fit in another larger rectangle

I am trying to find a formula for the height (or width) of the smaller rectangles in the following problem along with the number of rows they require: A given number $N$ rectangles (all of which are ...
0
votes
1answer
30 views

Maximum number of subrectangles that lie completely within a rectangle

Suppose I have $n$ rectangles in the 2D plane, as shown on the left. I am interested in partitioning the region inside these rectangles into disjoint sub-rectangles and counting the number of ...
5
votes
0answers
47 views

Prove that every point has been assigned the same number.

Question: Every point in a plane is assigned some real number. It is found that for any triangle, the number at its incenter is the arithmetic mean of numbers at the vertices. Prove that every ...
2
votes
2answers
74 views

Connected path of diagonals across an $n\times n$ grid, and Lemma of Sperner

Given an $n\times n$ grid where we draw at random one diagonal in each of the 1×1 unit squares. Then we can always find a connected path using these small diagonals that goes from one side of the grid ...
2
votes
1answer
50 views

How to find vertices of a $5$-dimensional simplex, where the vertices are formed by zeroes and ones?

I'm trying to find the vertices of a simplex in the $5$-dimensional space, where the vertices are formed by only zeros and ones, similarly to these coordinates that represent a simplex in the $7$-...
12
votes
1answer
196 views

Which sets are “connectable”?

Let's name each set of more than three points "connectable", when it is possible to connect all of the points that belong to set with n line segments (where n is number of points) in such a way that ...
0
votes
0answers
32 views

Chocolate Bar Game (Disguised Nim)

An $m * n$ chocolate bar can be broken in the usual way, players take turn to break the bar and the last player is the one who is left with the poison square which is marked somewhere on the bar and ...
1
vote
0answers
28 views

Problem about Tverberg number: Let $d,r_1,r_2$ natural numbers then we have $T(d,r_1r_2)$ $<=T(d,r_1)T(d,r_2)$

Im studying the book "Lectures on Discrete Geometry" of Jiri Matousek. The chapter 8.3 is about the Theorem of Tverberg which says: Let d and r natural numbers. For any set $A\subset R^d$ of at least ...
6
votes
2answers
62 views

The Maximum number of points of intersection of 4 distinct circles and 8 distinct straight lines is

The Maximum number of points of intersection of 4 distinct circles and 8 distinct straight lines is 1)66 2)64 3)104 4)40 Can anyone please help me to solve this problem? My attempt : I have ...
0
votes
0answers
23 views

(Extended?) Travelling salesman Problem

I've had a problem for several years, I can't get to solve : it seems similar to Travelling Salesman Person (I guess), except I need to visit a specific number of times the "distance criterion" is ...
0
votes
0answers
33 views

About vertex cut set

Suppose there is an undirected, connected graph $G=(V,E)$. Let $U\subseteq V$. Define vertex-deletion subgraph $G−U$ as the graph obtained from $G$ by deleting from $G$ the vertices in $U$ and ...
3
votes
1answer
88 views

Choosing representatives with spatial separation

There are $n$ sets of $k$ points in the 2-dimensional plane. Following the recent social distancing instructions, the distance between each two points in the same set is at least 2. We would like to ...
1
vote
0answers
18 views

$E1\otimes E2\,\iff\,Q1WQ2=(Q1E1)\otimes(E2Q2)$ - Meshulam's “On the maximal rank in a subspace of matrices”

I'm trying to prove to myself why the following claim is true. I think there is some "trivial" explanation, but I'm missing something. The claim is: Let $ E_1, E_2 \subset F^n, W \subset M_n(F)$ and ...
2
votes
1answer
46 views

Show that there are $3$ vertices of the same color forming an isosceles triangle.

Question: Let each of the vertices of a regular $9-$gon be colored black or white. (a) Show that there are two adjacent vertices of the same color. (b) Show that there are $3$ vertices of the ...
0
votes
1answer
42 views

Essentialization of hyperplane arrangement

I have started reading the following lecture notes on hyperplane arrangements and I am having some trouble with the essentialization of an arrangement explained at the start of the first lecture. A ...
9
votes
0answers
1k views

Fractal Pattern from Queen's Move Construction

This question relates to the OEIS sequence A279212. Fill an array by antidiagonals upwards; in the top left cell enter $a(0)=1$; thereafter, in the $n$-th cell, enter the sum of the entries of ...
1
vote
0answers
30 views

On subsets of $\mathbb N^2$ with elements not comparable w.r.t. componentwise order

Let $\mathbb N$ denote the set of nonnegative integers . For $(a,b);(c,d)\in \mathbb N^2$, define $(a,b)\le (c,d)$ iff $a\le c$ and $b\le d$. Let us call call a subset $S\subseteq \mathbb N^2$ to ...
1
vote
1answer
44 views

Counting number of points on plane in special procedure

Lets define following function $f : \mathbb{N} \rightarrow \mathbb{N}$ First consider arbitraty four points on plane $\mathbb{R}^{2}$, that are corner of some square. We write then $f(1)=4$ Later we ...
2
votes
1answer
58 views

Use Szemerédi-Trotter to show that $n$ points in the plane determine at most $O(n^{7/3})$ triangles that contain a fixed acute angle $\alpha$.

I'm doing exercises in Lectures on Discrete Geometry by Jiri Matousek. There's an application of the Szemerédi-Trotter Theorem to a problem of acute-angled triangles: Fix an acute angle $\alpha$. ...
0
votes
1answer
85 views

bricks of integer side lengths tiling a cube of volume $10^3$

At least 100 bricks, of integer side lengths, are used to completely fill a $10 \times 10 \times 10$ cube. What's the shortest way to show that there are at least two bricks of exactly the same ...
6
votes
2answers
113 views

Number of $2$-colorings of edges of the $n$-dimensional cube?

I'm interested in counting the number of $2$-colorings of the edges of an $n$-cube up to rotations and reflections. For $n=1$ there are two colorings—either color the edge or don't. For $n=2$ there ...
0
votes
0answers
76 views

The adjacent number game.

Preface: Four years ago, when I was in Grade 6 and in the Hanoi team training for the International Math Tournament of the Towns (IMTT), the leader of the Vietnam IMO team came and first provided me ...
7
votes
1answer
50 views

Counting polysticks on the $n$-cube.

Over at Code Golf Stack Exchange, I put up a challenge asking people to count, among other things, the number of ways to take an $n$-cube and color $k$ (connected) edges up to isometries of the $n$-...
9
votes
1answer
156 views

How many ways can we divide the Space with $N$ lines?

We know that the maximum number of pieces that can be created with a given number of cuts (lines) $n$, is given by the formula: $$P_{\max} = \frac{n^2 + n + 2}{2}$$ This is the problem of dividing a ...
5
votes
1answer
175 views

Probability Based on a Grid of Lights

The question is as follows : A grid of $n\times n$ ($n\ge 3$) lights is connected to a switch in such a way that each light has a $50\%$ chance of lighting up when switched on. What is the ...
2
votes
2answers
81 views

A game of tourism

CONTEXT Currently I am reading a series of book by Martin Gardner, the one I am working on is "The colossal book of Mathematics". Knowing that this man is hail as the greatest Math-Magician of the ...
2
votes
2answers
54 views

A fantasy game on the Angels&Demons novel

CONTEXT Recently, I have been reading the novel "Angels & Demons" by Dan Brown and I was kind of fascinated by the plot. This problem is inspired by the novel. PROBLEM Assume that the Vatican ...
1
vote
1answer
150 views

A problem on the $n\times n$ square [closed]

This problem is stated directly as following Problem A $n\times n$ square that satisfies the following conditions: $n\geq 4$ In each unit square we write a number $x$, with $0\le x \le 1 $. No ...
0
votes
0answers
14 views

Average number of blocks in a large cube

Let's say we have 1000 small, indivisible cubes of the same weight. We can glue 2 or more of these cubes together to form "blocks". What is the average number of blocks required to make at least the ...
3
votes
1answer
361 views

The spreading game and its expansion

For all those who lost their lives and due to this tragic disease CONTEXT This question is inspired by the following question that was proposed by my math teacher Lam Nguyen, I shall cite this ...
3
votes
0answers
38 views

A game on a regular (2n+1)-agon

A and B play a game on a $(2n+1)$-agon where $n\ge 1, n\in\mathbb{N}$ They draw diagonals such that every diagonal drawn i) Cannot be previously drawn ii) only intersect an EVEN number of drawn ...
2
votes
1answer
33 views

What is the smallest regular $n+1$-gon that contains a regular $n$-gon with unit length sides?

Given a regular $n$-gon with sides of unit length, what is the side length of the smallest regular $n+1$-gon containing it? For $n=3$ a bit of calculus yields a square of side length $$\cos\frac{\pi}{...
9
votes
1answer
256 views

Can we place $18$ points in a regular hexagon of side $2$ such that the minimal distance between points is $>1$?

Can we place $18$ points in a regular hexagon of side $2$ such that the minimal distance between points is $>1$? This a follow-up of this question. In the answers provided for it there are ...
2
votes
5answers
142 views

$14$ points in a regular hexagon of side $2$

Can we place $14$ points in a regular hexagon of side $2$ such that the minimal distance between points is $>1$? Background: We can place $13$ points in a regular hexagon of side $2$ so that the ...
7
votes
1answer
92 views

We have $n$ points in a plane. Show that there is at least $\lfloor {\sqrt{n\over 2}} \rfloor $ different distances between them.

We have $n$ points in a plane. Show that there are at least $\lfloor \sqrt{n\over 2} \rfloor $ different distances between them.
2
votes
1answer
29 views

How many divisions could be made from the parent size so that minimum paper gets wasted

Parent Paper size is (11.69 inches x 16.54 inches) Child paper size is (2 inches x 3 inches) How many divisions could be made from the parent size so that minimum paper gets wasted. I need some ...
1
vote
1answer
87 views

What is the maximum number of squares we can compact within a defined area?

What is the maximum number of squares (with sides equal to $a$) that we can compact within a region limited by curves or lines defined by functions? Note: So as not to make the problem more complex ...
0
votes
3answers
33 views

How to do these type of solid object questions in general?

Assume that n copies of unit cubes are glued together side by side to form a rectangular solid block. If the number of unit cubes that are completely invisible is 30, then what is the minimum possible ...
2
votes
1answer
58 views

Inequality for convex polygons

I have the following problem: Problem. Let $P$ be a convex $n$-gon on the plane. For $k=\overline{1,n}$ define $a_k$ as the length of $k$-th side of $P$ and $d_k$ as the length of projection of $P$ ...
1
vote
0answers
34 views

Restriction on distance between two points in a dense subset.

Consider a metric space $(M,d)$. Under what conditions is it the case that there exists some dense subset $D$ of $M$ such that $$\forall x,y \in D \, d(x,y) \neq 1$$ So far I have proven that such a ...
2
votes
0answers
26 views

In how many ways can you color the edges of the triangle using only reflection?

In how many ways can you color the edges of the triangle with 2 color (e.g. red and blue)? There are $m^3$ triangles fixed by the identity (1)(2)(3) There are $m^2$ triangles fixed under reflection, ...
2
votes
0answers
33 views

Dissecting a hypercube into specific hypercubes

The problem We define "$m$-cube" as an $m$-dimensional hypercube. ($m=2$ is square, $m=3$ is cube, ...) $(\mathbf Q):$ Given a container $m$-cube of integer side length $a$, and $n$ many $m$-cubes ...
0
votes
1answer
20 views

Colorings in 3D and beyond with equal number of black and white neighbours

Represent the three-dimensional space as a grid of unit cubes. Is there a way to colour each cube in black or white so that each cube has half of its $26$ neighbours (sharing a common side, face, or ...

1
2 3 4 5
13