All Questions
Tagged with polygons combinatorics
66
questions
1
vote
1
answer
54
views
Maximal irregular polygon inside a regular polygon
Problem:
We have a regular $n$-gon. We want to choose some of it's vertices ($A_1, A_2, \ldots, A_m$), so these vertices form a completely irregular $m$-gon. Meaning that all of it's sides have ...
- 47
0
votes
1
answer
100
views
Understanding a proof on IMO shortlist 2016 C3
The problem goes as follow:
Let $n$ be a positive integer relatively prime to 6. We paint the vertices of a regular
$n$-gon with three colours so that there is an odd number of vertices of each colour....
- 800
7
votes
2
answers
241
views
How to enumerate unique lattice polygons for a given area using Pick's Theorem?
Pick's Theorem
Suppose that a polygon has integer coordinates for all of its vertices. Let $i$ be the number of integer points interior to the polygon, and let $b$ be the number of integer points on ...
- 1,913
2
votes
0
answers
80
views
How many ways to glue a $4n$-gon to a genus $n$ surface?
In this question :
Two Fundamental Polygons for the Double Torus?
Lee Mosher says
There are four octagon gluing patterns (up to rotation and relabelling) which give a double torus.
It is a very ...
- 21
0
votes
2
answers
124
views
Number of diagonals in polygon connecting different vertices
I run into a combinatorics problem recently. Let's imagine we have a n-sided polygon, the number of diagonals is easily
$$N=\frac{n(n-3)}{2}$$
However, for my work, I need to group the vertices in ...
- 29
1
vote
0
answers
36
views
Proving Lagrange four square theorem from the "sum of three triangle" theorem
It was proven by Gauss that every integer is the sum of at most three triangle numbers, and by Lagrange that every integer is the sum of at most four squares.
The triangles are the set $\big\{1,3,6,...
- 702
3
votes
1
answer
80
views
Maximal cliques on graphs on the vertices of regular $2n$-gons
Consider the vertices of a regular $2n$-gon in the plane, and label the points clockwise $1,\dots,2n$. For any vertex $v$ let $-v$ denote its opposite vertex on the polygon.
Define a graph $G$ which ...
- 2,454
1
vote
1
answer
70
views
What is the largest possible value of the smallest angle between the diagonals of an $n$-gon for even $n$?
In this answer, I showed that the maximum value of the smallest angle between two diagonals of a $21-$gon is $8\frac{4}{7}$ degrees. The method given generalizes to all polygons with an odd number of ...
- 4,057
1
vote
2
answers
300
views
Consider the diagonals of a 21-gon. Prove that at least one angle of less than 1 degree is formed.
I think it should be solved using the pigeonhole principle. The answer is:
A $21-$gon has $189$ diagonals. If through a point in the plane, we draw parallels to these diagonals, $2 × 189 = 378$ ...
- 11
0
votes
0
answers
31
views
Collinear points in the Happy Ending Problem
Recalling the statement of the Happy Ending Problem, we see that
For any $k \in \mathbb{N}$ we may find a $n=n(k) \in \mathbb{N}$ such that every $n$ points in the plane, where no 3 are collinear, ...
- 466
5
votes
1
answer
293
views
Efficient way to find all polygons of the same shape within a set, regardless of position, scale, or rotation
I've got a big set of 2D polygons described as a set of points. I would like to take this set of polygons and find any that are the same shape, regardless of rotation, translation, or scale.
Each ...
- 295
4
votes
0
answers
84
views
For which natural numbers 𝑛 ≥ 3 is it possible to cut a regular 𝑛-gon into smaller pieces with regular polygonal shape?
I have been working on this question and I found that any regular polygon with n sides works.My claim is that we can cut any regular polygon of n sides into smaller regular polygons with n sides.And ...
- 81
0
votes
1
answer
389
views
A polygon has 60 diagonals. How many sides does it have?
I've used this formula to calculate the solution.
The number of diagonals of a polygon is $(n(n-3))/2$, where $n$ is the number of sides of a polygon.
But I'm getting answer as decimal point. Is the ...
user956073
4
votes
1
answer
896
views
Recursivley count triangulations of a convex polygon
I am trying to find a recursive number of different triangulations of a convex polygon with $n$ vertices.
After some searching I found that the number can be expressed using catalan numbers, this ...
1
vote
0
answers
80
views
Convex hull of combinatorial Zonotopes
Given a set of vectors/generators $V \subset \mathbb{R}^2$, one can obtain a Zonotope via Minkowski Sum $Z = \bigoplus_{i \in V} i$.
On the other hand, Given a set of sets of generators $C = \{ V_1, ...
- 1,271
7
votes
0
answers
372
views
When is it possible to find a regular $k$-gon in a centered $n$-gon?
For $n \geq 3$, say that a centered $n$-gon with $L$ layers is given by the origin, $(0,0)$ together with the points $$
\left\{\alpha\zeta_n^j + \beta\zeta_n^{j+1}\ \middle\vert\ 0 \leq j < n, 1 \...
- 5,072
3
votes
2
answers
140
views
Combinatorics Problem: Building numbers from the difference of the first 2021 numbers
I recently found this problem, it was part of a regional qualifier in Southern America (Venezuela- I believe) in January 2021. As I can’t find the solution anywhere and it is very different from the ...
user901311
0
votes
1
answer
788
views
How many obtuse angle triangles are possible in a regular Heptagon by joining its vertices?
I am only able to make one possible case,
Where we take any 3-consecutive vertices, since one of the vertices contains angle of Heptagon, which is approximately 128.57°, we get 7 such triangles.
I am ...
- 19
8
votes
2
answers
541
views
Number of points chosen form a polygon to have no isosceles and equilateral triangles.
Let $\Omega$ be a regular polygon with $n$ sides. Let's choose $\Gamma$ a set of vertices, for which any triangle with the vertices in $\Gamma$ is neither isosceles, nor equilateral. Find $\max |\...
0
votes
1
answer
167
views
Polytope of cone over a rational normal curve
Consider a rational normal curve $C\subset\mathbb{P}^d$ of degree $d$, and let $W\subset\mathbb{P}^{d+1}$ be a cone over $C$.
Since $C$ is a toric variety $W$ is toric as well. I would like to ask ...
- 838
3
votes
2
answers
577
views
Catalan numbers in polygons
I'm stuck on such problem: triangulation of the $n$-gon is division of said $n$-gon into $(n-2)$ triangles whose sides are either sides of the $n$-gon or certain non-intersecting diagonals. How many ...
- 49
2
votes
2
answers
193
views
Binomial identity of alternating sum of products of binomial coefficients taken two at a time
I came across this identity a while back and wasn't able to prove it.
$$\sum_{i=1}^{n-3}\frac{\binom{n-3}{i}\binom{n+i-1}{i}}{i+1}\cdot(-1)^{i+1}=
\begin{cases}
0& \text{if $n$ is odd,}\\
2& \...
- 45
1
vote
1
answer
332
views
Polygon Diagonal Combinatorics
A diagonal for a polygon is defined as the line segment joining two non-adjacent points. Given an n-sided polygon, how many different diagonals can be drawn for this polygon?
I know that the number of ...
- 150
2
votes
1
answer
393
views
Number of isoceles triangles formed by the vertices of a polygon that are not equilateral
QUESTION: Let $A_1,A_2,...,A_n$ be the vertices of a regular polygon with $n$ sides. How many of the triangles $△A_iA_jA_k,1 ≤ i < j < k ≤ n,$ are isosceles but not equilateral?
MY APPROACH: ...
- 1,323
10
votes
1
answer
398
views
Intersections of circles drawn on vertices of regular polygons
Using only a compass, draw all possible circles on the vertices of a regular $n$-sided polygon.
(That is, in every ordered pair of vertices one is the center, and their distance is the radius.)
...
- 12.5k
1
vote
1
answer
251
views
Number of circles on vertices of a regular polygon
How many unique circles can we draw on vertices of a $n$-sided regular polygon? To draw a circle, pick two distinct vertices. One is the center of the circle, and the other determines the radius.
Let ...
- 12.5k
1
vote
2
answers
772
views
Schlafli symbol determining number of faces
Schlafli symbols are used to describe polytopes, but can also be used to describe more general objects through the use of flags. In particular, some information can be readily 'read-off' from a ...
- 1,903
0
votes
1
answer
178
views
Number of ways to choose a closed path of given length on a square lattice
Also known as self-avoiding polygons, this is an unsolved problem. However, to leading order in the asymptotic limit, the number of polygons of a given perimeter scales exponentially with perimeter ...
- 1,191
1
vote
1
answer
894
views
Number of right angled triangles formed by vertices of a 14-gon
Here's a question that I found on the website of International Kangaroo Maths Contest. The question goes like this:
What is the total number of right angled triangles that can be formed by joining ...
- 1,313
0
votes
1
answer
33
views
Minimum $k$ vertices that a 4 form a quadrilateral with common sides with a 2018-gon
$\mathbb{P}$ is a regular polygon with 2018 sides.
What is the minimum number $k$ of vertices that 4 of them form a convex quadrilateral with 3 common sides with $\mathbb{P}$.
My idea is to color ...
- 467
9
votes
1
answer
460
views
Number of chords in a $n$-gon if each chord is crossed at most $k$ times
Consider an $n$-gon where we denote the points by $v_1, \dots, v_n$.
If we allow each chord (internal edge of the $n$-gon) to have at most $k$ crossings, how many chords can we put into the $n$-gon (...
- 61
6
votes
1
answer
599
views
Smallest circumscribed polygon around regular polygons
Given a regular $n$-gon $Q$, there are many polygons $P$ that entirely contain $Q$, and such that all $n$ vertices of $Q$ lie on edges of $P$. These circumscribing polygons $P$ have different numbers ...
- 63
3
votes
2
answers
64
views
Need a hint regarding this question...
In how many ways can we select three vertices from a regular polygon having $2n+1$ sides ($n>0$) such that the resulting triangle contains the centre of the polygon?
- 31
3
votes
2
answers
4k
views
Number of Quadrilaterals that can be formed in Decagon
Find number of Quadrilaterals that can be formed in a Decagon such that no side of Quadrilateral is common to side of Decagon.
I tried as follows:
Arbitrarily choose $6$ points on a circle. Then we ...
- 10.2k
2
votes
1
answer
128
views
Looking for a formula that counts the number of unique constructions of "coffee tables" that have an n-gon tabletop.
Coffee tables are build by placing legs under vertices of an n-gon in such a way that the table won't tip over. Here are the rules:
If n is even we can use (2, ..., n) legs. Every valid table must ...
- 351
2
votes
1
answer
606
views
The travelling salesman problem for a regular n-gon
The TSP asks, given a finite set $V$ of points in $\Bbb R^2$, to find the shortest path that passes through all points and returns to the starting point. Trivially, one reduces to the case of a path ...
- 27.7k
5
votes
3
answers
151
views
Lattice embeddings of a polygon
Consider the four lattice polygons below. Each shape is over the coordinates.
If reflected or flipped on the major axes and diagonals, these four polygons remain distinct. However, this is the ...
- 21.4k
0
votes
2
answers
232
views
How many common points do two regular polygons in a circle have?
I was attempting to solve the following question:
In a circle you have a $27$ sided regular polygon and a $297$ sided polygon $($all vertices are on the circle$).$ How many common points do they ...
- 1,368
2
votes
1
answer
156
views
Number of regular (not necessarily simple) polygons on $n$ equidistant points on a circle.
I need to find the number of regular $n$-polygons on $n$ equidistant points on a circle (that is, adjacent points are equally distant from each other). There's a hint saying the answer is related to ...
- 107
6
votes
0
answers
297
views
Counting Regular polygons in Complete Graphs
The figure shows the correct $24-$gon, which held all the diagonals.
a) Find out how we got right triangles and squares (question for arbitrary $n$)?
b) How this problem can be generalized (if it is ...
- 17.9k
4
votes
2
answers
5k
views
Ways to create a quadrilateral by joining vertices of regular polygon with no common side to polygon
How many ways are there to create a quadrilateral by joining vertices of a $n$- sided regular polygon with no common side to that polygon?
It's quite easy to solve for triangles for the same question,...
- 199
2
votes
1
answer
107
views
Prove the number of red sides are always larger than $\frac{n^{2}-2n}{2}$
Every side and diagonal of a polygon (n-sided) is colored in red or blue. If there are no triangles with all sides colored in blue, prove that the number of red sides is always greater than $\frac{n^{...
1
vote
2
answers
265
views
number of subset forming polygon
Given a set $S = \{ 1 , 2 , 3,\ldots, n\}$. How can I find number of subsets of size $K$ ($K < n$) whose elements taken as length of edges can form a convex polygon ($K$-sided).
- 9
0
votes
1
answer
67
views
Number of Pieces a regular $n$-gon is cut into by its diagonals [closed]
In how many pieces a regular n-gon is cut into by its diagonals?
I need a general formula.
By inspection, I have the solution to some lower values of $n$.
For $n=3,4,5,6$ solutions are $1, 4, 11, ...
1
vote
0
answers
243
views
Minimal diagonal intersections in a convex polygon
OEIS A006561 gives the number of intersection points in the diagonals of a regular polygon. There's a paper by Poonen. For 4 vertices to 12, the number of intersection points is:
$$1, 5, 13, 35, 49, ...
- 21.4k
1
vote
1
answer
83
views
Moving between polygons drawn within a convex polygon with parts of diagonals
My question is about one problem given in last round of codeforces, pretty easy to handle it, but I do not understand the other players` solutions.
We have a convex polygon and numbers it's ...
- 663
23
votes
4
answers
93k
views
How many triangles can be formed by the vertices of a regular polygon of $n$ sides?
How many triangles can be formed by the vertices of a regular polygon of $n$ sides? And how many if no side of the polygon is to be a side of any triangle ?
I have no idea where I should start to ...
- 335
1
vote
0
answers
80
views
All polygons satisfy the "normal" property.
A fancy explanation is below, but here's an edited simpler explanation because I think the jargon makes the problem seem inaccessible. In reality this problem is super accessible and I'm sure the ...
- 31
1
vote
0
answers
67
views
What is the probability to pass through $1\le m\le n$ vertices of an $n$-sided polygon after $t$ seconds?
Suppose a flea is on a vertex of an $n$-sided polygon. It stays still for exactly one second, and then jumps instantly to an adiacent vertex. Let us assume it has no memory of its previous jumps and ...
- 7,299
22
votes
8
answers
3k
views
Number of ways to connect sets of $k$ dots in a perfect $n$-gon
Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices in a given perfect $n$-gon such that no two lines intersect at the interior of the $n$-gon and no vertex remains ...
- 821