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.

0
votes
2answers
378 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 ...
6
votes
2answers
192 views

Cases where ANY 2 of 3 +/- choices select one of four possible elements

Edited 1/21/2018 to add the following: Here is a DropBox link https://www.dropbox.com/s/7rtt0iqmgimsgzu/Zumkeller_edge-magic.pdf?dl=0 to a PDF showing how my team used biomolecular first ...
7
votes
3answers
402 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 ...
4
votes
1answer
201 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. ...
4
votes
2answers
164 views

Number of ways to distribute objects, some identical and others not, into identical groups

The question I initially thought of that prompted this was "How many distinct integer-sided cuboids are there with a volume of $60^3$?". A small example to clarify: There are $3$ integer-sided ...
18
votes
1answer
532 views

Shooting Game for Fun

Trigger Warning: Murder is mentioned. Let there be $n>1$ people (players) on a plane, each having a loaded gun and each being a perfect shot (assuming that each bullet is laced with one gram of ...
7
votes
2answers
474 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})$$ ...
11
votes
1answer
133 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 ...
8
votes
1answer
396 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 ...
3
votes
1answer
101 views

Uniformly distributed points distance question

$N$ points are placed randomly according to a uniform distribution in a $1 \times 1$ square. If $M$ is the number of points that have a distance more than $c/\sqrt{N}$ to others, then prove $\exists c,...
7
votes
4answers
908 views

Maximum area of triangle inside a convex polygon

Prove that within any convex polygon of area $A$, there exists a triangle with area at least $cA$, where $c=\tfrac{3}{8}$. Are there any better constants $c$? I'm not sure how to approach this ...
3
votes
2answers
582 views

Height of $n$-simplex

$n$-simplex is a generalization of triangle or tetrahedron (with $n + 1$ vertices). The problem is to find its height. I kindly ask to check my solution. I am not fluent with $n$-dimensional space ...
4
votes
2answers
129 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$...
3
votes
1answer
596 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 ...
2
votes
1answer
2k views

How many shapes can one make with $n$ square shaped blocks?

How many possible shapes can one make by rearranging $n$ square shaped blocks, with and without allowing rotational symmetry? For example, for $n = 4$, there are seven possible shapes after ...
8
votes
0answers
361 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 ...
4
votes
1answer
420 views

Can an 8×8 square be tiled with these smaller squares?

Number of square pieces, Question C Sal has two $4\times 4$ squares, three $3\times 3$ squares, four $2\times 2$ squares and four $1\times 1$ squares. Draw a diagram showing how she can place all ...
28
votes
1answer
1k 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 ...
25
votes
2answers
766 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 ...
25
votes
4answers
779 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
1k 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
553 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
2answers
2k views

Maximum distance between points in a triangle

An equilateral triangle has sides of unit length. a)Show that if five points lie in/on the triangle, then at least two of the points lie no farther than 0.5 units apart. b)Show that 0.5 cannot be ...
3
votes
0answers
195 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
379 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 ...
8
votes
3answers
266 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 ...
8
votes
2answers
583 views

Venn diagram with rectangles for $n > 3$

Is it possible to draw a Venn diagram with rectangles for $n > 3$? If yes, is it possible for all $n\in\mathbb{N}$? If no, up to which $n$ is it possible? Furthermore, the rectangles should have ...
7
votes
1answer
89 views

What is the color number of the 3D space, if we allow only convex regions?

I am thinking on the analogy of the well-known 2D coloring problem for the 3D space (with the trivial geometry & topology). As this reference says, simply increasing the dimensions by one doesn't ...
6
votes
0answers
369 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 ...
6
votes
3answers
645 views

Prove that the shortest side of one triangle is the longest side of another, given 3 pairs of points.

I have received this question and am having great difficulties. I don't even know how to try to solve it. It goes like this: 6 points are given in a room. These points are pairwise differently ...
5
votes
1answer
856 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 ...
3
votes
2answers
214 views

Proof involving Ramsey numbers

$S$ is a set of R(m,m;3) points in the plane in which no 3 points are collinear. I am trying to prove that $S$ contains $m$ points that form a convex $m$-gon. I have tried using similar logic to the ...
9
votes
2answers
1k 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 ...
7
votes
0answers
182 views

Points at Integer Distances in 3-space

With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. 1 For 3-...
7
votes
2answers
156 views

An example of a similar universal cover for 5 points.

Let's say that $A\subset\mathbb{R}^2$ is a similar universal cover for $n$ points if: $A$ is closed. The interior of $A$ is empty. For every finite set $B\subset\mathbb{R}^2$ containing exactly $n$ ...
5
votes
2answers
599 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 ...
5
votes
1answer
205 views

Rectangle with lattice points

Given a positive integer $n\geq 2$, consider all the lattice points with each coordinate between $1$ and $n$, inclusive. At least how many points must we choose to guarantee that some four points form ...
5
votes
0answers
202 views

Points and lines covering them

Let $n$ be a positive integer. A subset $S$ of points in plane satisfies the following conditions: a) We can't find $n$ lines in plane, such that every element of $S$ belongs to at least one of these ...
5
votes
0answers
141 views

Minimum number of points chosen from an $N$ by $N$ grid to guarantee a rectangle?

What is the maximum number of points that can be chosen from an $N$ by $N$ grid such that no $4$ of the chosen points form a rectangle with sides parallel to the axes of the grid? Equivalently, what ...
4
votes
1answer
81 views

Marking the point closest to each point

We have $6000$ points in the plane. All distances between every pair of them are distinct. For each point, we mark red the point nearest to it. What is the smallest number of points that can be marked ...
2
votes
1answer
794 views

Number of points of intersections, no of parts of chords inside circle

$n$ points ($n>1$) are taken on the circumference of a circle. Through any two of them a chord is drawn. No three chords intersect at one point inside the circle. i) Find how many points of ...
2
votes
1answer
290 views

Properties of triangles with integer sides and area

OEIS sequence A051518 describes There exists a triangle of perimeter $n$ having integer sides and area. And begins ...
1
vote
1answer
69 views

Probability that points uniformly distributed are at least $c/\sqrt{N}$ far apart.

$N$ points are distributed randomly, independently according to uniform distributions in a $1 \times 1$ square. What is the probability that for each pair of points $A(x_1,y_1), B(x_2,y_2)$ in the ...
1
vote
2answers
145 views

Tiling a 7×7 rectangle with trominoes [closed]

We are given a $7 \times 7$ array. We want to remove a $1 \times 1$ square, such that the remaining shape can be covered with $1 \times 3$ triomino. What are the possible positions of the eliminated ...
6
votes
1answer
1k views

Strictly convex sets

If $S\subseteq \mathbb{R} ^2$ is closed and convex, we say $S$ is strictly convex if for any $x,y\in Bd(S)$ we have that the segment $\overline{xy} \not\subseteq Bd(S)$. Show that if $S$ is compact, ...
5
votes
2answers
2k 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, ...
5
votes
0answers
50 views

Color the edges and diagonals of a regular polygon

Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $\dfrac{\binom{n}{2}}{3}$ colors, such that you use every color exactly three ...
4
votes
0answers
158 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]
3
votes
3answers
84 views

Prove that there are exactly $k$ pairs $(x,y)$ of rational numbers with $0\leq x,y<1$ for which both $ax+by,cx+dy$ are integers.

Let $a,b,c,d$ are integers such that $(a,b)=(c,d)=1$ and $ad-bc=k>0$. Prove that there are exactly $k$ pairs $(x,y)$ of rational numbers with $0\leq x,y<1$ for which both $ax+by,cx+dy$ are ...
3
votes
3answers
191 views

$0$ interior to the convex hull of rational vectors

Reading a paper by John Franks, at a certain point it is proven that $0$ is in the interior of the convex hull of $v_1, v_2, v_3, v_4$, where the $v_j$ are certain vectors in the plane with rational ...