next up previous
Next: About this document ...

Solutions:


\begin{picture}(90,90)
\put(0,15){\line(1,0){90}}
\put(15,40){\line(1,0){60}}
...
...(42,22){$3$}
\put(57,25){$7$}
\put(72,22){$5$}
\put(42,0){$17$}
\end{picture}




\begin{picture}(90,90)
\put(0,15){\line(1,0){90}}
\put(15,40){\line(1,0){60}}
...
...(42,22){$6$}
\put(57,25){$1$}
\put(72,22){$8$}
\put(42,0){$20$}
\end{picture}




\begin{picture}(90,90)
\put(0,15){\line(1,0){90}}
\put(15,40){\line(1,0){60}}
...
...(42,22){$8$}
\put(57,25){$2$}
\put(72,22){$4$}
\put(42,0){$23$}
\end{picture}





I grouped the numbers one through nine into three groups of consecutive numbers: X=[1,2,3], Y=[4,5,6], Z=[7,8,9]. I assigned each group to either the three overlapping positions (b, d, g), the three corner positions, or the three remaining positions. This way, it was easy to find the solutions by rotating the three members of the groups through the three positions of that group.

$ n=17$ is the lowest sum arrangement because the lowest numbers are the ones that appear most often in the sums for 2 by 2 triangles, as X is in the overlapping positions. $ n=23$ is the highest sum arrangement because the largest numbers appear most often, as Z is in the overlapping position.






Lemma: n cannot be increased or decreased without changing the numbers in the overlapping positions.

$\displaystyle a+b+c+d=b+e+f+g=d+g+h+i=n$

$\displaystyle a+b+c+d+e+f+g+h+i=1+2+3+4+5+6+7+8+9=45$

b, d, g cannot change.

a, and arbitrary non-overlapping position, is changed to $ a+q$.

$\displaystyle (a+q)+b+c+d=b+e+f+g+q=d+g+h+i+q=n+q$

($ e+f$) and ($ h+i$), also non-overlapping positions, must be increased by q as well to maintain the equalities.

Substitution:

$\displaystyle (a+b+q)+c+d+(e+f+q)+g+(h+i+q)=45$

None of the unchanged variables can be changed. Changing an already changed variable (in the parenthesis) would have no net effect. In this case, $ a+b$ can be considered a single variable because a and b only appear in one expression.

$\displaystyle 3q=0$








Now, suppose q is added to overlapping elements b, d,g.

$\displaystyle a+(b+q)+c+(d+q)=(b+q)+e+f+(g+q)=(d+q)+(g+q)+h+i=n+2q$

We still have the option to change more variables to get the sum from one through nine to equal the sum of a through i, so I added 3q to both sides.

$\displaystyle a+(b+q)+c+(d+q)+e+f+(g+q)+h+i=45+3q$

$\displaystyle [(b+q)+(d+q)+(g+q)]+[(a+c-q)+(e+f-q)+(h+i-q)]=45$

In order to maintain the values of a through i as 1 through 9, the values of b, d, and g must each be switched with one of the values in the pairs (a+c), (e+f), and (h+i). This proves that only sets X, Y, or Z can be in the overlapping positions (b, d, g).

$\displaystyle (b+q)+(d+q)+(h+i-q)=(b+q)+(g+q)+(e+f-q)=(d+q)+(g+q)+(h+i-q)=n+q$

If you take a tiny number a, b, and the next consecutive tiny number c, d:

$\displaystyle (a-b \sqrt{2})(a+b \sqrt{2})=(a+b \sqrt{2})(c-d \sqrt{2})+ad\sqrt{2}-bc\sqrt{2}$

$\displaystyle a^2-2b^2=ac-2bd=z_{a,b}$

$\displaystyle c=\frac{2bd+a^2-2b^2}{a}$

Example:

$\displaystyle 1^2-2 \cdot 1^2=1 \cdot 3 - 2 \cdot 1 \cdot 2 = -1$

Starting with $ a=7$, $ b=5$, and $ z=-1$ some tiny numbers are:




Tiny Numbers  
a b $ z_{a,b}$ Approximation
17 12 1 .0294
41 29 -1 -.0122
99 70 1 .0051
239 169 -1 -.0021
577 408 1 .0009

Case (a): $ 58-41\sqrt{2}$ is not tiny.

Case (b): $ 99-70\sqrt{2}$ is tiny.

Lemma 1: k is an integer. Allowing repeated elements in reciprocally whole sets:

There exists a reciprocally whole set contains only a set L, $ k+1$ and $ k^2+k$ $ \leftrightarrow$ There exists a reciprocally whole set containing L and k.

$\displaystyle \frac{1}{k}=\frac{1}{k+1}+\frac{1}{k^2+k}$

$\displaystyle \frac{1}{k}=\frac{1}{k+1}+\frac{1}{k(k+1)}$

$\displaystyle \frac{1}{k}=\frac{k+1}{k(k+1)}$

$\displaystyle \frac{1}{k}=\frac{1}{k}$








Lemma 2: There can be no reciprocally whole set R with fewer than three elements.

Case 1: If a set were to have one element a, then $ a=\frac{1}{1}$, which is prohibited because the element must be greater than 1.

Case 2: If a set were to have two elements, a and b, then $ \frac{1}{a} \ge \frac{1}{2} \vee \frac{1}{b} \le \frac{1}{2}$.

$ \frac{1}{2}=\frac{1}{2}$, so $ a=2$ is one possible value of a.

$\displaystyle \frac{d\left ( \frac{1}{x} \right)}{dx}=\frac{-1}{x^2}$

$\displaystyle \frac{d^2 \left ( \frac{1}{x} \right)}{dx^2}=\frac{2}{x^3}$

$ \frac{1}{x}$ decreases on $ [1,\infty)$. Therefore $ a=2$ is the only value of a.

$\displaystyle 1=\frac{1}{2}+\frac{1}{b}$

$ a=b=2$, but the elements of R must be distinct. There are no sets R with fewer than three elements.








The reciprocally whole set I={2,3,6} exists. I has the least possible number of elements by lemma 2.

The derivatives used in Lemma 2 Case 2 shows that if either the first or second element (2 or 3) were increased, the total sum of reciprocals would decrease. In order to maintain a reciprocal sum of one without adding elements, the third term (6) would have to decrease. This makes two possible reciprocally whole sets with three distinct elements; {2,4,5} and {3,4,5}. The first results in a reciprocal sum of .95, the second of $ \frac{47}{60}$.

There are no sets other than I={2,3,6} with three members.

Lemma 1 can be used to expand I to get three sets with four members:

{3,3,6,6}, which has repeated elements.

{2,4,6,12}

{2,3,7,42}

If J had three elements in common with I but was distinct from I, then J's reciprocal sum would be greater than 1. J can be either $ \{2,4,6,12\}\wedge\{2,3,7,42\}$.

$\displaystyle S=\{2,3,4,6,12\}\wedge S=\{2,3,6,7,43\}$

One can show the number of combinations of four points out of the nine...

$\displaystyle {9\choose 4}=\frac{9!}{4!(9-4)!}=126 $

This gives the number of possible quadrilaterals.

Next, we eliminate the possible quadrilaterals with straight angles. Any three points lying along the same line form straight angles.

Example:



\begin{picture}(12,12) % (12,12) is size of picture
\par
%start at coordinate (1...
...= 20 units right and 10x1 = 10 units up
\put(1,1){\line(1,1){10}}
\end{picture}




It is easy to see, either graphically or by calculating the line between every pair of points (36 pairs), that there are eight sets of three collinear points, and none with more than three collinear points, lying horizontally, vertically, or along the long diagonals of the figure. Each of these sets are subsets of six of the 126 possible quadrilaterals, because there are six possible points remaining to connect to any of the three collinear points.

$\displaystyle 126-6 \cdot 8=78$

Most of the quadrilaterals form a convex set. These can only form one quadrilateral.



\begin{picture}(12,12) % (12,12) is size of picture
\par
%start at coordinate (1...
...\line(1,0){5}}
\put(1,6){\line(1,0){5}}
\put(6,1){\line(0,1){5}}
\end{picture}




Some form a concave set. These special cases form a triangle with a fourth point on the inside.





\begin{picture}(12,12) % (12,12) is size of picture
\par
%start at coordinate (1...
...1,6){\circle*{2}}
\put(6,11){\circle*{2}}
\put(6,6){\circle*{2}}
\end{picture}



Each convex set can form three quadrilaterals by making any of the outermost triangles' sides concave.

Only the center point of the figure (1,1) can be within a triangle.

All the triangles that surround a point A, regardless of the placement of the points in a finite, discrete set of possible vertices can be found by using the following method on each set of distinct points A, B, C:

  1. Construct a ray $ l$ from B through A.
  2. Construct a ray $ m$ from C through A.
  3. Find the number X of points opposite both $ l$ and $ m$ from B and C. Ignore points on $ l$ and $ m$.
  4. $ X$ is the number of triangles with vertices B and C surrounding A.


\begin{picture}(14,14) % (12,12) is size of picture
\par
%start at coordinate (1...
...
\put(6,3.5){A}
\put(9,12){C}
\put(13.5,6){$l$}
\put(2,0){$m$}
\end{picture}



There are eight concave subsets to the given set of points.

$\displaystyle 78-8+8\cdot3=94$

There are ninety four quadrilaterals.








This solution can be generalized for any n-gon with arbitrary finite set of x possible vertices.

  1. Start with the number of possible sets:

    $\displaystyle {x \neq n \to {x \choose n}=\frac{x!}{(n!)(x-n)!}}=p$

    $\displaystyle x = n \to 1=p$

  2. Find equations for all $ \left( \frac{x!}{2(x-2)!}=\frac{x \cdot (x-1)}{2} \right)$ lines connecting all possible vertices.

  3. Eliminate all p sets that have more than $ \frac{2n}{3}$ collinear vertices $ \left(c \le \frac{2n}{3}\right)$. There are q of these eliminated sets. The minimum order of a polygon with c collinear points can be found by connecting every other pair of collinear points, connecting the remaining gaps using additional points, and connecting the two ends using a final point:


    \begin{picture}(10,10)
\par
%draw colinear dots
\par
\put(1,4){\circle*{2}}
\pu...
...31,0){\circle*{2}
\line(6,1){30}}
\par
\put(1,4){\line(6,-1){30}}
\end{picture}

    Every third point is not in line, hence the $ \frac{2}{3}$ ratio.


  4. Test each set to see if it could include a concave polygon. For each set of points A, B, C, D in each possible n-gon:

    1. Construct a ray $ l$ from B through A.
    2. Construct a ray $ m$ from C through A.
    3. If D is opposite both $ l \vee m$ from B and C, but not on $ l \wedge m$, then A is a point of concavity with level one. The number of sets containing at least one point of concavity is f.
    4. If there is a set A, B, C, E such that A is still a point of concavity, A has a concavity level of two, and so on.
  5. There exists a value $ W_{m,w}$, the concavity level of point w in possible n-gon m.
  6. If a possible n-gon m, for all points w, $ W_{m,w}=0$ then that m defines one (convex) n-gon.
  7. If there is one or more point with a non-zero W then the number of polygons defined by the set of possible n-gon vertices is, for each non-zero W, the product of all $ W+n-1$.

  8. The total number of n-gons in the set, ignoring W when 0, is:

      $\displaystyle p-q-f+((W_{g,1}\cdot n-1)\cdot (W_{g,2} \cdot n-1)\cdot (W_{g,3} \cdot n-1)...)$ (1)
      $\displaystyle +((W_{h,1} \cdot n-1) \cdot (W_{h,2} \cdot n-1) \cdot (W_{h,3} \cdot n-1)...)$ (2)
      $\displaystyle +((W_{i,1} \cdot n-1) \cdot (W_{i,2} \cdot n-1) \cdot W_{i,3} \cdot n-1)...)...$ (3)

Image triangle1

Case (i): $ \frac{3}{2}$

First, divide the segment $ \bar{BC}$ into 16 parts using any method of bisection, such as:

Construct a line between the points of the intersection of two circles with centers at each end of the segment and radii greater than half the segment.

The result is a segment of length $ \frac{12}{16}$. Then construct a circle e of that radius at the center of the large circle closest to the right angle, and a circle f at the point where that large circle is tangent to $ \overline{AC}$. In my diagram, I only show a circle at the point where the two small circles e, f are tangent.

$\displaystyle \frac{2 \cdot 12}{16}=\frac{3}{2}$

Case (ii): $ \frac{\sqrt{5}}{2}$

Case (iii): $ \frac{\pi}{2}$




next up previous
Next: About this document ...
Nicholas Frazer 2004-11-29
Creative Commons License
This work is licensed under a Creative Commons License.