V. Serganova. Optimization


Isoperimeter problem


Theorem 1. Among all n-gons (polygons with n sides) of given perimeter a regular polygon has the biggest area.


Theorem 2. A circle is a figure of the biggest area among all plane figures of the given perimeter.


1. Show that among all triangles inscribed in a given circle an equilateral triangle has the maximal area and the maximal perimeter.


2. Show that among all n-gons inscribed in a given circle a regular n-gon has the maximal area and the maximal perimeter.


3. Peter and Jane want to divide a triangular cake. They decided to do it in the following way. Peter chooses a point $ P$ on the cake, and Jane cuts a piece for herself by one straight cut passing through $ P$. How should Peter choose a point to get a piece of maximal possible area?


4. You have to make a rectangular box ( with a top) from a piece of paper of 6 square meters. Show that the box with maximal volume should have a shape of a cube.


Minimize the distance


Theorem 3. Let $ ABC$ be a triangle with all angles less than 120 degrees. Let $ O$ be a point on the plane such that the sum of distances from $ O$ to the vertices is minimal. Then the angles $ AOB$, $ AOC$ and $ BOC$ are equal 120 degrees.


Theorem 4. Let $ A$ and $ B$ be two points on a sphere. Then the shortest path from $ A$ to $ B$ is an arc of a great circle passing through $ A$ and $ B$.


5. Construct the point $ O$ in theorem 3 with ruler and compass.


6. Given an angle and a point $ A$ inside it. Find points $ P$ and $ Q$ on two different sides of the angle such that $ AP+PQ+QA$ is minimal.


7. A river is bounded by two straight parallel banks. Two villages are on the opposite sides of the river. How to choose the place for a bridge across the river so that the distance between the villages is minimal? The bridge must be perpendicular to the banks of the river.


8. What happens if the triangle in theorem 3 has an angle greater than 120 degrees? Given a triangle $ ABC$ with one angle greater than 120 degrees. Find a point $ P$ on the plane such that $ AP+BP+CP$ is minimal.


Combinatorial optimization


9. There are $ n$ points on the plane, some of these points are collinear. Each point has its own price. You need to buy a cheapest triangle, i.e. a set of three non-collinear points. First you buy a cheapest point $ A$. Then you buy a cheapest point $ B$ from what is left and then finally you buy a cheapest point $ C$ from the set of points which do not lie on the line $ AB$. Prove that you have bought the cheapest triangle.


10. Generalize problem 9 for spaces of higher dimension.