The original problem was: given 4 cities arranged as the vertices of a square of side length 8 km find a way to connect the cities together using 22km of road or less. The solution can be seen as follows:      Constructing the road in this manner is "less" symmetric than just making the road with the diagonals of the square yet it is shorter. This intrigued me and I decided to see how much we could optimise this approach of leaving a space of length x in the middle. With a bit of simple calculus I found the length of the road is minimised for $$x = 2 \times (4 - \sqrt{\frac{16}{3}})$$ The length of the road is minimised to approximately 21.856 for this value of x.  Given all this I have numerous questions: 1. Could I have an intuitive explanation for why a "less" symmetric solution is actually better than the "optimally" symmetric solution of two diagonals even though the problem relates to a square which is very symmetrical. 2. Is this value of 21.856 the best we can do? Is there a better solution? Is there an optimal solution? If there is an optimal solution can we prove it is optimal?
33362
I have four cities in $A=(0,0),B=(1,0),C=(1,1),D=(0,1)$. I am asked to build the shortest motorway to connect the cities. How can I do that?  I was thinking that first I need some compactness argument to prove that there really is the shortest way to connect cities. Or if one can prove that one can travel via finitely many line segments, the existence of minimal way migth be possible to prove via some olympiad-level inequalities.  Then I think I need to find points $E,F$ such that $\angle AEB=\angle CFD=120^\circ$. But I think it is difficult to prove that such a configuration is really a minimal.  Could anyone give hints/solution how to fill the details?  Bonus: Has anyone generalized this problem to $n$ cities in a regular $n$-gon?
90533
Question I found in "Introduction to Graph Theory" by Douglas B. West:     Let $G$ graph on $n$ vertices with connectivity $\kappa(G)=k \geq 1$. Prove that $$n \geq k(\operatorname{diam}(G)-1)+2$$ where $\operatorname{diam}(G)$ is the the maximal (edge) distance between a pair of vertices in $G$   Seems easy and I've seen the answer, too, which goes the same as thought: by taking the vertices the end vertices of the path of length $\operatorname{diam}(G)$, and applying Menger's Theorem. I'm having a hard time understanding one part - it seems like all the paths need to be of the same length for the $n \geq k(\operatorname{diam}(G)-1)+2$ to apply. Am I missing some part here?
110366
In  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 is the maximum number of regions into which n circles can divide the plane?  After some exploration it seems to me that in order to get maximum division the circles must intersect pairwise, with no two of them tangent, none of them being inside another and no three of them concurrent (That is no three intersecting at a point).  The answer seems to me to be affirmative, as the number I obtain is $n^{2}-n+2$ different regions. Is that correct?
123910
Consider the $n$-dimensional quadratically constrained quadratic optimization problem  $$\begin{array}{ll} \text{maximize} &amp; \frac12 x^T A x + b^T x\\ \text{subject to} &amp; \| x \|_2 \le 1\end{array}$$  where $A$ is a symmetric $n\times n$ matrix that may be indefinite. Given the symmetry of the constraint, is there a nice closed-form solution, perhaps in terms of the eigendecomposition of $A$?
92342
Let both ends of a string of length $L$ be tied to a stick of length $S$. Among all plane regions enclosed by this contraption, it achieves maximum when the string forms a circular arc.  It is noted that if $S=0$, this theorem is reduced to the isoperimetric theorem, which states, for the length $L$ of a closed curve and the area $A$ of the planar region that it encloses,   $4\pi A \le L^2$,  and that equality holds if and only if the curve is a circle.  Your comments and ideas are greatly appreciated!
48976
I'm assuming this theorem was found by someone else before, but I found this relationship between square numbers of 3 digits or less. The theorem is this: If you reverse the digits in a square number, then the result will also be a square number. Take the square 961. It is 31 squared, and if you reverse the digits you will get 169, which is also a square number. Plus, 31 and 13(the roots of these reversed squares) are also reverses of eachother. The problem is this breaks with 4 or more digits. If I take the square 1024 and reverse the digits, I get 4201, which is not a square. How can I expand this theorem to fit 4 or more digits?
36759
I posted a similar  about geodesics on Math.SE. Many sources ( for instance) claim that the light could maximize the optical path length in some cases. But I don't think it's actually true since between two points I can always imagine a path with arbitrary length. Therefore, or the light minimizes the optical length or it's stationary (neither maximum nor minimum). My question is: is the trajectory in red in the figure below a local minimum or a stationary curve?   If I'm wrong, please provide some examples which the light propagates in trajectory of maximum length.
114324
Prove that having 6 points in the interior of a square of side length 3, we can choose 2 of them so that the distance between them is less than 2.  Looks obvious, but I can't get a rigorous demonstration.   I tried to cover the square with 6 circles of radius 1, having the centers inside the square, to prove they must intersect at least once.  Note:  This partition leads to solution.  The rectangles on the first row: $3/2 * (3 - \sqrt3) $   The rectangles on the second row: $1 * \sqrt3 $   The 5 zones are so that the distance between any 2 points inside the same zone is less than 2.
428
Let $p &lt; q &lt; r &lt; s$ be real numbers. Let $l$ be the geodesic with endpoints at $p$ and $q$ and let $m$ be the geodesic with endpoints at $r$ and $s$. (a) Prove that there is a unique geodesic segment from $l$ to $m$ that is perpendicular to both. (We sometimes say $l$ and $m$ are ultraparallel since they are not only parallel but they do not share endpoints also.)  (b) Now suppose $p &lt; q &lt; r$ are real numbers and $l$ is a geodesic whose endpoints are $p$ and $q$ and $m$ is a geodesic whose endpoints are $q$ and $r$. Then $l$ and $m$ are parallel, but prove that there is not geodesic segment from $m$ to $l$ that is perpendicular to both. That is, unlike the ultraparallel case, there are no points on $l$ and $m$ that realize the shortest distance from $l$ to $m$.
58646
The problem states that:     A simple (or strict) graph with $n$ vertices and $m&gt;\dfrac{3(n-1)}{2}$ edges, has two vertex   joined by three independent paths.   Any hints, ideas or useful results, to attack this problem?
111342
I was given this question by a friend and after working tirelessly on it I have not come up with anything substantial. I was hoping someone in the community could provide a pointer or possibly a solution. The person who gave me the question says he has the answer to it, but I am more curious about the working.  Here is the question:     Three points $(B, C, D)$ lie on parabola  $y = x^2$ and a fourth point $A$ is placed such that $ABCD$ forms a square. Find the minimal area of $ABCD$.   So far my working out has involved a collection of distance/mid-point formula's and I haven't even reached the point where I differentiate to minimize the area.  Any pointers would be welcome.   Edit  Apparently the correct answer is $\sqrt{2}$ units squared.
24298
Let's say we are given a race track, which may be described as a closed curve of given width (it may differ along the curve). My task is to implement an algorithm which finds two kinds of trajectories for the car. The first one is the shortest path, i.e. such closed curve contained in the race track that enables the car to drive the shortest distance per lap, the speed is irrelevant. The second one is minimum curvature path where the car can achieve higher speeds in the corners, the length is irrelevant.  The following picture shows the two kinds of paths for an example race track:   I found a paper () that describes the two problems in such way that they can be presented as quadratic programming problems. The problem is that I don't have sufficient knowledge to convert the input data to the appropriate matrices, needed in the quadratic equation. I can only understand the transformations up to some moment.  Here are the descriptions of the algorithms, found in the mentioned paper:   Could someone please help me and explain the transformations done in the equation (6) and (7) for the SP problem and virtually all equations for the MCP problem? The format of representation of all the coordinates, depicted in Fig. 2 in the document, is perfectly clear for me. I realize that some equations are just the intermediate steps to achieve the goal, so maybe there's an easy, algorithmic way to explain a newbie like me how I should transform the given coordinates to get the matrices for the quadratic programming solver.
70573
Consider a square of sidelength $n$ and $ (n+1)^{2} $ interior points. Prove that we can choose 3 of these points so that they determine a triangle (eventually degenerated) of area at most 1/2.  I couldn't get started on this. Any ideas?
5520
I was asked to find the no. of ways to get from (0,0) to (8,8) with the 4 points of the shaded box unpassable, aka I can't use the 4 points namely (3,3)(4,4)(3,4)(4,3) while on my way to (8,8). Right and up movements.  I know it is something like a pascal triangle and worked out the solution of 4050 ways.  May I know if there are any faster means using permutation formula?  Thank you in advance.
42787
I'm supposed to find a quadrangle of the smallest perimeter possible inscribed in a rectangle. The inscribed quadrangle has each of its four vertices on another side of the rectangle.   Let's call the rectangle ABCD and let the shorter side be $a$ and the larger $b$. Let's call the quadrangle $KLMN$.   So for example $K$ lies on $AB$, $L$ on $BC$, $M$ on $CD$, $N$ on $AD$.  I think that the sides of $KLMN$ would be the shortest of its diagonals intersected at the right angle, because then by the law of cosines, we have $KL^2 + LM^2= KM^2 + 2 KL \cdot LM \cdot \cos  \angle KLM$, and $\cos  \angle KLM \le 0$ if $\angle KLM \ge 90 ^{\circ}$ and $KM$ is the shortest if it is parallel = equal to the proper side of the rectangle.  Could you tell me if I'm right or correct me if I'm wrong?  Thank you.
112207
I'm not sure how to go about this. One of my thoughts was to take the number of edges in a complete graph, and subtract all of the edges that would be needed to make a smaller cycle.   If you have $C_5$, there is only one way to make a $5$-cycle on $5$ vertices, but there's $10$ ways to make a $3$-cycle, and...  I have no idea how to do this without counting things multiple times.
9840
For one of my homework problems, we had to try and find the maximum possible length $L$ of a pipe (indicated in red) such that it can be moved around a corner with corridor lengths $A$ and $B$ (assuming everything is 2d, not 3d):    My professor walked us through how to derive a formula for the maximum possible length of the pipe, ultimately arriving at the equation $L = (A^{2/3} + B^{2/3})^{3/2}$.  The issue I have is understanding intuitively why this formula works, and exactly what it's doing. I understand the steps taken to get to this point, but there's an odd symmetry to the end result -- for example, is the fact that $\frac{2}{3}$ and its inverse are the only constants used just a coincidence, or indicative of some deeper relationship?  I also don't quite understand how the formula relates, geometrically, to the diagram. If I hadn't traced the steps myself, I would have never guessed that the formula was in any way related to the original problem.  If possible, can somebody give an intuitive explanation as to why this formula works, and how to interpret it geometrically?    Here's how he found the formula, if it's useful:  The formula is found by finding the maximum possible length of the pipe by expressing the length in terms of the angle $\theta$ formed between the pipe and the wall, and by taking the derivative to find when $\frac{dL}{d\theta} = 0$, which is the minimum of $\frac{dL}{d\theta}$ and is therefore when $L$ is the smallest:  $$ L = \min_{0 \leq \theta \leq \frac{\pi}{2}} \frac{A}{\cos{\theta}} + \frac{B}{\sin{\theta}} \\ 0 = \frac{dL}{d\theta} = \frac{A\sin{\theta}}{\cos^2{\theta}} - \frac{B\cos{\theta}}{\sin^2{\theta}} \\ 0 = \frac{A\sin^3{\theta} - B\cos^3{\theta}}{\sin^2{\theta}\cos^2{\theta}} \\ 0 = A\sin^3{\theta} - B\cos^3{\theta} \\ \frac{B}{A} = \tan^3{\theta} \\ \theta = \arctan{\left( \frac{B}{A} \right)^{\frac{1}{3}}} \\ $$  At this point, we can substitute $\theta$ back into the original equation for $L$ by interpreting $A^{1/3}$ and $B^{1/3}$ as sides of a triangle with angle $\theta$ and hypotenuse $\sqrt{A^{2/3} + B^{2/3} }$:  $$ \cos{\theta} = \frac{A^{1/3}}{ \sqrt{A^{2/3} + B^{2/3} }} \\ \sin{\theta} = \frac{B^{1/3}}{ \sqrt{A^{2/3} + B^{2/3} }} \\ \therefore L = A^{2/3} \sqrt{A^{2/3} + B^{2/3} } + B^{2/3} \sqrt{A^{2/3} + B^{2/3} } \\ L = (A^{2/3} + B^{2/3}) \sqrt{A^{2/3} + B^{2/3} } \\ L = (A^{2/3} + B^{2/3})^{3/2} \\ $$  The equation for the formula for the maximum length of the pipe is therefore $L = (A^{2/3} + B^{2/3})^{3/2}$.