Tagged Questions
3
votes
2answers
47 views
Geometric solution to classic committee problem
Most people know the classic committe style problems.
I read this solution to one of the basic version of the committe problem and was impressed, but not sure why it works.
I was hoping someone ...
3
votes
1answer
29 views
Formula for lines that can be drawn using $n$ points
Please help me!
How many lines can be drawn using $6$ points? Each line is made by connecting $2$ points.
0
votes
3answers
84 views
Maximizing triangle area
Here is the problem:
We start with a triangle ABC with area 1. We choose a point (F) on side AB, then someone else chooses a point (G) on side BC. We then choose the last point (H) on side CA. Our ...
18
votes
4answers
103 views
Ways to fill a $n\times n$ square with $1\times 1$ squares and $1\times 2$ rectangles
I came up with this question when I'm actually starring at the wall of my dorm hall. I'm not sure if I'm asking it correctly, but that's what I roughly have:
So, how many ways (pattern) that there ...
1
vote
1answer
56 views
Convex polygon with 18 vertices and points of intersection of the diagonals.
I have the following problem:
I'm given convex polygon with 18 vertices. It is known that no 3 diagonals of the polygon intersect in a single point.
How many points of intersection of the diagonals ...
0
votes
0answers
161 views
2d bin packing problem, with opportunity to optimize the size of the bin
I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the ...
0
votes
1answer
44 views
Counting lattice points interior to a polygon
If I define an integer lattice $\Lambda \subseteq \mathbb{Z}^2$ with a basis given by
$$\omega_{1} = a \hat{i} + b\hat{j}, \;\;\; \omega_{2} = -b \hat{i} + a\hat{j}$$
How can I count how many lattice ...
0
votes
1answer
29 views
Dividing an arbitrary $2-D$ shape with integer area into arbitrary shapes of unit area
The name explains it all. I searched for it in MSE and came across a similar [one] but more simpler1. I was interested to know if we can prove that, i.e., given an arbitrary shape (closed and ...
5
votes
3answers
205 views
How to show that all points are inside of unit circle?
There are $n$ points on the plane. Any $3$ of them are inside of a unit circle. How to show that all points are inside of unit circle?
It is needed to prove that if there is a unit circle for each ...
1
vote
0answers
36 views
geometric method to distinguish free groups?
Denote $F_n$ to be the free non-abelian group on $n$ generators, so $F_n$ is just the free product of $n$ copies of $\mathbb{Z}$.
Till now, we have many methods to prove that $F_m\not \cong F_n$ for ...
2
votes
0answers
73 views
Number of collinear subsets in a set
Call a set of points $(x,y)$ good if all the points in the set are collinear (i.e. they all lie on a line).Let S be the set of points $(x,y)$ such that $0\leq x,y \leq n$ ( $ x,y $ are restricted to ...
0
votes
0answers
92 views
How to divide plane with four circles to get Maximum number of region [duplicate]
I started to divide flat plane with one circle to get maximum number of regions and I got 2.
Then I tried to do this with two circles And I got 4 different regions. Then I did this with tree circles ...
3
votes
0answers
307 views
An easy question on geometry.
The question says that I have to derive a formula to find the maximum number of enclosed regions formed by $n$ lines. This is how I proceeded:
Let $f(n)$ be the maximum number of enclosed regions ...
4
votes
1answer
153 views
Five points in a disk
Why is
$$
\min_{1\le i,j,k\le5}\frac{\mbox{Area}\left(\triangle P_{i}P_{j}P_{k}\right)}{\mbox{Perimeter}\left(\triangle P_{i}P_{j}P_{k}\right)}<\frac{4}{25}
$$ for any five points $P_{1}$, ...
2
votes
0answers
32 views
Kmeans on “symmetric” data
A set is said to be fully-symmetric if for every $x$ in it, negating one of its components results in $y$ such that $y$ is in the set as well.
A set is said to be semi-symmetric if for every $x$ in ...
2
votes
4answers
283 views
How many tetrahedrons in a tetrahedron?
Given a regular tetrahedron. All the edges were divided into N equal segments. How many non-degenerate ($|\text{volume}| > 0$) tetrahedrons with vertices at the points of division can be built ...
0
votes
2answers
29 views
Maximum number of middle-points of sides and diagonals of polygon that can lie on a single circle
Notice middle-points of all diagonals and sides of a $2010$-gon. What's the maximum number of those points which can lie on a single circle?
The solution goes like this:
Note point $O$ which ...
3
votes
1answer
112 views
Triangle from a given rectangle
We are given a set of (marked) points in a 2D coordinate system and function $f(x,y)$ which counts number of points marked in the rectangle $(0 , 0), (x , y)$ - where $(0 , 0)$ if down-left corner, ...
8
votes
2answers
106 views
Why does the term ${\frac{1}{n-1}} {2n-4\choose n-2}$ counts the number of possible triangulations in a polygon?
In the given picture bellow, it counts the number of different triangloations in a polygon, how do the get to this expression, why is it:
$$
{2n-4\choose n-2}
$$
and why do we multiply it by ...
0
votes
2answers
40 views
Property of nonconvex polygons
How to prove that each non-convex polygon with no self-intersecting parts, has at least one interior angle which size is less then $180$ degrees.
4
votes
0answers
53 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 ...
9
votes
1answer
209 views
What is the probability of having a pentagon in 6 points
If the probability that $5$ random points in the plane whose horizontal
coordinate and vertical coordinate are uniformly distributed on the
interval $\left(0,1\right)$ occur to be the vertices of a ...
14
votes
1answer
213 views
Expected size of subset forming convex polygon.
If there are $4$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the interval
$\left(0,1\right)$, what is the expected largest size (or ...
0
votes
2answers
69 views
Counting the number of diagonals?
In a heptagon not more than two diagonals intersect at any point other than the vertices, then the number of points of intersection of the diagonals is (excluding the vertices of this heptagon)....???
...
2
votes
0answers
48 views
Convex polyhedral decomposition of spheres
Is there a decomposition of $S^2$ into $k$ (geodesically) convex polyhedra that are congruent to each other? What about $S^n$ for $n>1$?
Remarks:
A polyhedron is defined as an area enclosed by a ...
1
vote
1answer
134 views
Dissection of a chess board into 4 congruent pieces
Consider a standard $8\times 8$ chessboard where a pawn is placed on each of the squares $d1,d2,d3,d4$ . Dissect the board into $4$ congruent pieces (reflections are allowed) such that each piece ...
0
votes
2answers
131 views
Number of triangles formed by $m$ lines
Problem:
How many triangles do $m$ lines form if
a) Every two lines intersect and no three lines intersect at one point.
b) There are $n$ lines among $m$ lines that are parallel to each other. ...
1
vote
3answers
152 views
What is the maximum number of regions produced, i.e. $f(n)$, by joining all vertexes with line segments of a convex polygon with $n$ sides?
What is the maximum number of regions produced, i.e. $f(n)$, by joining all vertexes with line segments of a convex polygon with $n$ sides?
For example, for the hexagon on the left, number of ...
2
votes
1answer
86 views
Unfolding Polyhedra
I'm interested in learning more on unfolding polyhedra.
Are there any known algorithms that unfold polyhedra into nets? I'm interested in writing code on this in either MATLAB, Python, or C#.
On ...
2
votes
0answers
132 views
Finding the number of intersections of chords within a circle
There are n points on a circle that are pairwise connected by a chord in the circle. What is the maximum and the minimum number of points within the circle that are intersections of the chords?
3
votes
0answers
39 views
How many unique centroids? [duplicate]
Possible Duplicate:
How many positions for centroid of triangle?
Suppose that we are given 40 points equally spaced around the perimeter of a square, so that four of them are located at the ...
0
votes
1answer
29 views
Inequivalent Arrangements on a ring
I am having some difficulty trying to understand how to do this problem. Any help would be great. I'm new to this site. Thanks in advance.
Count the number of in-equivalent arrangements of
1) six ...
0
votes
1answer
55 views
Probability/Polytope concept
Let $X$ be a real random variable, with real values $X_i$ associated with probabilities $p_i \ge0, p_1 \le 1$, $i=1$ to $n$.
The variance $V_p(X)$, is, as usual:
$$V_p(X) = \sum^n_{i=1} p_i X_i^2 ...
2
votes
2answers
109 views
Joint density of the smallest and largest random variables among finite independent random variables with common density
I am trying to show the following result.
Let $X_1, \ldots,X_n$ be independent random variables with the common density $f$ and distribution function $F$. If $X$ is the smallest and $Y$ the largest ...
2
votes
1answer
214 views
Counting Hexagons in Triangle Grid Recurrence?
(This is from a long finished programming competition)
Consider a triangle grid with side N. How many hexagons can fit into it?
This diagram shows N = 4:
I need a recurrence for it:
I tried the ...
7
votes
1answer
379 views
Into how many parts do $n$ ellipsoids divide $\mathbb{R}^{3}$?
What is the maximum number of regions into which $\mathbb{R}^{3}$ can be divided by $n$ ellipsoids? (Each ellipsoid has the same size). Let´s denote this number by $r_{n}$.
Clearly $r_{1}=2$. But ...
36
votes
4answers
2k views
Do circles divide the plane into more regions than lines?
In this post it is mentioned that $n$ straight lines can divide the plane into a maximum number of $(n^{2}+n+2)/2$ different regions.
What happens if we use circles instead of lines? That is, what ...
0
votes
2answers
124 views
Convex Polyhedron: How many corners maximum?
How many corners can a $n$-dimensinal convex polyhedron have at tops? Is it the same as the number of corners a $n$-dimensional simplex has?
EDIT:
By polyhedron $P$, I mean, that for some matrix $A ...
1
vote
0answers
60 views
Count Exclusive Partitionings of Points in Circle, Closing Double Recurrence?
I am studying a problem that I have worked out is equivalent to the following:
Problem Description
Given N distinct points on the border of a circle, there are $B_N$ ways to partition them - where ...
2
votes
1answer
172 views
Turning affine planes into projective planes
How can we show that an affine plane of order $n$ can always be turned into a projective plane of order $n$?
Say I start with an affine plane, and split it into $n+1$ parallel classes, add a point ...
2
votes
1answer
634 views
How many triangles with integral side lengths are possible, provided their perimeter is $36$ units?
How many triangles with integral side lengths are possible, provided their perimeter is $36$ units?
My approach:
Let the side lengths be $a, b, c$; now,
$$a + b + c = 36$$
Now, $1 \leq a, b, c ...
6
votes
2answers
332 views
Sword, pizza and watermelon
Suppose that we have a sword and cut a pizza and watermelon. What is the maximum number of pieces of pizza or watermelon obtained after 10 cuts. Is there a general formula
21
votes
3answers
904 views
Guaranteed Checkmate with Rooks in High-Dimensional Chess
Given an infinite (in all directions), $n$-dimensional chess board $\mathbb{Z^n}$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite ...
6
votes
3answers
243 views
Puzzle: A coin rolls without slipping around another coin
If a coin rolls without slipping around another coin of the same or
different size, how many times will it rotate while making one
revolution?
The proof given is like this:
Cut the curve ...
2
votes
1answer
47 views
Convex hull of a triangle and a translation of it
Say you are given triangle ABC in $\mathbb{R}^n$, and its translation A'B'C' such that A'B'C' is not coplanar with ABC. Must it be the case that the convex hull of ABC and A'B'C' is a triangular ...
12
votes
2answers
187 views
Given $n$ points on the plane, find a circle which contains only three
Given $n$ points on $\mathbb{R}^{2}$, s.t no three are on the same straight line, and not all the points are on the same circle, prove that there exists a circle which contains only three of those ...
1
vote
1answer
176 views
To find the number of points on a 2D grid?
Given N points on a 2D grid of the form (X,Y) we need to find to find all the points (R,S) such that the sum of the distances between the point (R,S) and each of the N points given is as small as ...
0
votes
1answer
74 views
A lemma regarding cones covering $\mathbb{R}^d$
Added: Pointers to some references with the same conclusion as the wolloing lemma may be helpful to understand it, and are appreciated.
In A Probabilistic Theory of Pattern Recognition By Luc ...
2
votes
1answer
56 views
Can a rectangle tiled by squares be written as a union of two rectangular subtilings?
Suppose I have a rectangle $R$ tiled by finitely many squares - i.e. written as a finite almost disjoint union $$R = \bigcup_{i=1}^n S_i $$ where each $S_i$ is a square and such that $S_i^\circ \cap ...
6
votes
2answers
263 views
Tiling pythagorean triples with minimal polyominoes
Given a Pythagorean triple $(a,b,c)$ satisfying $a^2+b^2=c^2$, how to calculate the least number of polyominoes of total squares $c^2$, needed, such that both the square $c^2$ can be build by piecing ...
