10936 * Prove that there exists a set S of n-2 points in the interior of a convex n-gon such
that for any three vertices of the n-gon, the interior of the triangle determined by the three
vertices contains exactly one element of S. *

__Solution:__

Let A_{1}, .. , A_{n} be the vertices, and A_{i}A_{i+1} the
sides (with n+1 "=" 1).

Choose the first point in the interior of the intersection of
the triangles A_{1}A_{2}A_{k} with k at least 3. The points in these n-2 triangles
now must be shaded away, because they no longer may be chosen.

Choose the second point among the points in the unshaded part of the intersection of the triangles A_{1}
A_{3}A_{k} with k at least 4, and shade the points in these n-3 triangles away.

Proceeding in the same way: choose the j-th point (j at most n-2) in the unshaded part of the
intersection of the triangles A_{1}A_{j+1}A_{k} with k at least j+2
(this unshaded part is not empty, because the polygon is convex), and shade these n-j-1 triangles
away.

After n-2 steps the whole polygon is shaded, since any point of the polygon lies in a triangle
with vertex A_{1}.

Now it is easy to verify that for any i smaller than j and j smaller than k, the triangle
A_{i}A_{j}A_{k} contains the point chosen in the (j-1)-th step, and no other
chosen point.

10948 *Let K be the circumcenter and G the centroid of a triangle with side lengths a, b, c
and area D. Let r be the distance between K and G. Show (in a heuristic way) :
(12Dr) ^{2} = a^{2}b^{2}c^{2} - (b^{2}+c^{2}-
a^{2})(c^{2}+a^{2}-b^{2})(a^{2}+b^{2}-
c^{2}).*

__Solution:__

Use coordinates A(0,0), B(c,0), C(b*cos(alpha),b*sin(alpha)).

We have

G((b*cos(alpha)+c)/3,b*sin(alpha)/3) and

K(c/2,lambda) with

(c/2)^{2}+
(lambda)^{2} = (c/2-b*cos(alpha))^{2}+(lambda-b*sin(alpha))^{2},

so lambda=(b-c*cos(alpha))/(2*sin(alpha)).

We find after a bit of calculation:

36*r^{2} = 4*b^{2}-4*b*c*cos(alpha)+c^{2}-4*b*(3*b-3*c*cos(alpha))+
((3*b-3*c*cos(alpha))/(sin(alpha)))^{2}.

We use the formula for the area, 2*D=b*c*sin(alpha). Then we find, after multiplying both sides
with b^{2}*c^{2}*sin^{2}(alpha) and a bit of calculation:

(12*D*r)^{2} = b^{2}*c^{2}*(b^{2}+c^{2}+8*
(b^{2}+c^{2})*
cos^{2}(alpha)+8*b*c*cos(alpha)*sin^{2}
(alpha)-18*b*c*cos(alpha).

Now the left hand side is what we want. We still have to find the right hand side.

We use the cosinus-rule b^{2}+c^{2}=a^{2}+2*b*c*cos(alpha)
and sin^{2}(alpha)+cos^{2}(alpha)=1, and find for the right hand side:

b^{2}*c^{2}*(a^{2}+8*a^{2}*cos^{2}(alpha)-8*b*c*cos(alpha)*
sin^{2}(alpha)) = a^{2}*b^{2}*c^{2}(1+8*cos^{2}(alpha))
-2*b*c*cos(alpha)*(16*D^{2}).

By symmetry we find for the right hand side:

a^{2}*b^{2}*c^{2}(1+8*cos^{2}(alpha))
-2*b*c*cos(alpha)*(16*D^{2}) =

a^{2}*b^{2}*c^{2}(1+8*cos^{2}(beta))
-2*a*c*cos(beta)*(16*D^{2}) =

a^{2}*b^{2}*c^{2}(1+8*cos^{2}(gamma))
-2*a*b*cos(gamma)*(16*D^{2}).

We add these three equal expressions, and divide by 3. Then we find for the right hand side,
after using all three cosinus-rules:

a^{2}*b^{2}*c^{2} + (1/3)*a^{2}*b^{2}*c^{2}*
(8*cos^{2}(alpha)+8*cos^{2}(beta)+8*cos^{2}(gamma))-(16/3)*D^{2}*
(a^{2}+b^{2}+c^{2}).

We use 4*D^{2} = b^{2}*c^{2}*sin^{2}(alpha) =
a^{2}*c^{2}*sin^{2}(beta) = a^{2}*b^{2}*
sin^{2}(gamma), and find:

a^{2}*b^{2}*c^{2} + (1/3)*a^{2}*b^{2}*c^{2}*
(8*cos^{2}(alpha)+8*cos^{2}(beta)+8*cos^{2}(gamma)-4*sin^{2}(alpha)
-4*sin^{2}(beta)-4*sin^{2}(gamma)).

Now, since alpha+beta+gamma=pi, we have sin(gamma)=sin(alpha+beta)=sin(alpha)*cos(beta)+cos(alpha)*sin(beta),

and -cos(gamma)=cos(alpha+beta)=cos(alpha)*cos(beta)-sin(alpha)*sin(beta).

Hence we find:

(1/3)*a^{2}*b^{2}*c^{2}*
(8*cos^{2}(alpha)+8*cos^{2}(beta)+8*cos^{2}(gamma)-4*sin^{2}(alpha)
-4*sin^{2}(beta)-4*sin^{2}(gamma)) =

a^{2}*b^{2}*c^{2}*(
8-4*sin^{2}(alpha)-4*sin^{2}(beta)-4*sin^{2}(gamma)) =

a^{2}*b^{2}*c^{2}*(8-8*sin^{2}(alpha)-8*sin^{2}(beta)+
8*sin^{2}(alpha)*sin^{2}(beta)-8*sin(alpha)*sin(beta)*cos(alpha)*cos(beta)) =

8*(1-sin^{2}(alpha))(1-sin^{2}(beta)) - 8*sin(alpha)*cos(alpha)*sin(beta)*cos(beta) =

8*cos(alpha)*cos(beta)*(cos(alpha)*cos(beta)-sin(alpha)*sin(beta)) =

-8*cos(alpha)*cos(beta)*cos(gamma).

Therefore, we find that the right hand side equals

a^{2}*b^{2}*c^{2} - 8*a^{2}*b^{2}*c^{2}*
cos(alpha)*cos(beta)*cos(gamma).

Using the three forms of the cosinusrule, we find that this equals

a^{2}*b^{2}*c^{2} -
(b^{2}+c^{2}-a^{2})(c^{2}+a^{2}-b^{2})(a^{2}+b^{2}-
c^{2}), that is what we want.

10950 *Consider a triangle T with sides a,b,c and vertices A,B,C, and a point P.
Let a',b',c' be the distances from P to A,B,C. Call P 'good' if the triangle with sides
a',b',c' is similar to T.
a) Show that T has a good point if and only if T is acute or rectangular.
b) Show further that the ratio of similarity a'/a is always at least 1/sqrt(3), with
equality if and only if T is equilateral.*

__Solution to a):__

First suppose a is smaller than b and b smaller than c and c=1
(the angle gamma at C may be obtuse and is at
least 60 degrees).

Use coordinates C(0,0), A(b,0), B(a*cos(gamma),a*sin(gamma)).

Then b'/b = c'/c is a circle with center M_{1}:(1/(1-b^{2}))*(a*cos(gamma),
a*sin(gamma)) and radius r_{1} = a*b/(1-b^{2}).

And a'/a = c'/c is a circle with center M_{2}:(1/(1-a^{2}))*(b,0) and radius
r_{2} = a*b/(1-a^{2}).

Then, with the help of the cosinusrule and a bit of calculation, we find the following equivalent assertions:

1) there exist two good points P

2) r_{1} + r_{2} > distance(M_{1},M_{2})

3) a^{2}+b^{2}-2*a*b*cos(gamma) < (a^{2}+b^{2})^{2}

4) c^{2}=1 < a^{2}+b^{2}

5) T is acute.

Now the assertion 10950 follows, using continuity.

Remark: if gamma=90 degrees, then the circles a'/a = c'/c and b'/b = c'/c are
touching in one good point P on the straight line M_{1}M_{2} outside T.
So if gamma is too great, there is no interior good point.

For instance, if a=b=sqrt(2)/2 and gamma=90 degrees, then we find M_{1}(0,sqrt(2)),
M_{}(sqrt(2),0) and P(sqrt(2)/2,sqrt(2)/2).

__ Concerning b): __Both the statement in a) and that in b) have been proved by Karel Post,
using the Cayley-Menger determinant.
He also investigated for which values of gamma the triangle has an interior good point, using the
theorem of Stewart. If a and b are equal, the outcome is: gamma must be smaller than about 77.3 degrees.

10951 *A game starts with one stick of length 1 and four sticks of length 4. The two
players move alternately. A move consists of breaking a stick of length at least 2 into two
sticks of shorter integer lengths or removing n sticks of length n for some n in {1,2,3,4}.
The player who makes the last move wins. Which player can force a win, and how?*

__Solution:__

At any moment during the game, let e,t,d,v be the numbers of sticks of
length 1,2,3,4 resp. Then (e,t,d,v)=(0,0,0,0) is a losing position, so (1,0,0,0), (0,2,0,0)
(0,0,3,0) and (0,0,0,4) are winning positions (for the player at move). We can make a list of
losing and winning positions, beginning with these five. Any position is winning if one
well-chosen move changes it into a losing position, and losing if every possible move makes it
a winning one.

I wrote a computer program in Pascal to make the list, representing (e,t,d,v) by the
number 2^{e}3^{t}5^{d}7^{v}. I find that (1,0,0,4) is a
__losing position__. The strategy for the winner is: always change your winning position in
a losing one, consulting the list
in reversed order. The Pascal program runs about five hours.
For the Pascal code click here .

10955 *Let ABC be a triangle and denote by O, I and G the circumcenter, incenter and centroid
of ABC. Let r be the radius of the inscribed circle and R the radius of the circumscribed
circle.
a) Show that (OI) ^{2}-(OG)^{2}-2(IG)^{2}=(2r/3)(R-2r), so
triangle OGI is obtuse.
b) Further establish the following inequalities: OI is at least OG, 2*OI is at least 3*IG, 2*OG is
at least IG, and 4*(OI)^{2} is between 4*(OG)^{2}+8*(IG)^{2} and
16*(OG)^{2}+5*(IG)^{2}. Show that in each case the constants are best possible.*

__Solution to a):__

Give coordinates A(0,0), B(c,0), C(b*cos(alpha),b*sin(alpha)) with
a smallest en c largest. We find:

O:(c/2,(b-c*cos(alpha))/(2*sin(alpha)),

I:(b*c*(1+cos(alpha))/(a+b+c),b*c*sin(alpha)/(a+b+c)),

G:((b*cos(alpha)+c)/3,b*sin(alpha)/3,

R=a/(2*sin(alpha))=(a*b*c)/(4*D) (where D is the area of the triangle),

r=b*c*sin(alpha)/(a+b+c)=(2*D)/(a+b+c).

Hence after a bit of calculation we find

(OI)^{2} = R^{2}-b*c*(b+c)/(a+b+c)+2*b^{2}*c^{2}*(1+cos(alpha))/
(a+b+c)^{2} = R^{2}-a*b*c/(a+b+c) = R^{2}-2*r*R,

(OG)^{2}=R^{2}-(a^{2}+b^{2}+c^{2})/9,

(IG)^{2}=2*b^{2}*c^{2}*(1+cos(alpha))/(a+b+c)^{2}-
2*b*c*(b+c)*(1+cos(alpha)/(3*(a+b+c))+(2*b^{2}+2*c^{2}-a^{2})/9 =

= (2*b*c*(b+c)+2*a*c*(a+c)+2*a*b*(a+b)-a^{3}-b^{3}-c^{3}-9*a*b*c)/(9*(a+b+c)).

I guess we must express the elementary symmetric expressions in a,b,c in r,R,D.

We have a+b+c=2*D/r and a*b*c=4*D*R. In calculating a*b+a*c+b*c, we discover that

r=4*R*sin(alpha/2)*sin(beta/2)*sin(gamma/2).

Hence r is at most R/2, with equality if the triangle
is equilateral. Eventually we find

a*b+a*c+b*c = 4*r*R+r^{2}+D^{2}/r^{2}, and hence

(OI)^{2} = R^{2}-2*r*R,

(OG)^{2} = R^{2}+8*r*R/9+2*r^{2}/9-2*D^{2}/(9*r^{2}),

(IG)^{2} = -16*r*R/9+5*r^{2}/9+D^{2}/(9*r^{2}).

Now we see that (OI)^{2}-(OG)^{2}-2(IG)^{2}=(2r/3)(R-2r).
So (OI)^{2}-(OG)^{2}-(IG)^{2} is positive (if O,I,G are distinct),
and the cosine-rule tells it is equal to -2*OG*IG*cos(angle OGI). So angle OGI is obtuse.

__ Concerning b):__
Research of the inequalities amounts to investigating for which constants certain homogeneous
polynomials (for instance of degree 4) are positive-definite.

Both the equality and the inequalities have been proved by Jos Jansen, using the orthocenter H,
the line of Euler and the theorem of Stewart.

10956 *You have three pegs and you have disks of different sizes. You are supposed to transfer the disks
from one peg to another, and the disks have to be sorted so that the biggest is always on the
bottom. You can move only one disk at a time. An order of disks on a peg is acceptable as long
as the disk at the bottom is the largest. Give an algorithm that moves a single stack of n
disks from one peg to another in a minimum number of moves, and find a formula for that
minimum number of moves. The disks are sorted from largest on bottom to smallest on top at the
start, and are to be sorted in the same order, but on a different peg, at the end.*

__Solution:__

The algorithm consists of 2n-1 steps.

In step number k (k ranging from 1 to n-1) you begin with disks k,k+1,...,n-1,n in this order from
top to bottom on the first peg, no disks on a second, and the disks 1,2,..,k-2,k-1 in order
k-2,k-4,...,k-3,k-1 on the third. The step consists of moving k to the empty peg and then
moving k-2,k-4,...,k-3,k-1 on top of k, thus taking k moves. The first n-1 steps take together
1+2+..+n-1=n(n-1)/2 moves.

The n-th step begins with n on the first peg, nothing on a second, and n-2,n-4,...,n-3,n-1 on the
third. It consists of moving n to the empty peg, thus taking 1 move.

In step number n+k (k ranging from 1 to n-1) you begin with n-k-1,n-k-3,...,n-k-2,n-k on one peg,
n-k+1,n-k+2,..., n-1,n on another, and the third empty. The step consists of moving
n-k-1,n-k-3,...,n-k-2 to the empty peg and then moving n-k on top of n-k+1,n-k+2,...,n-1,n,
thus taking n-k moves. So the last n-1 steps take together n(n-1)/2 moves.

The total of moves is n(n-1)/2 + 1 + n(n-1)/2 = 1+n(n-1).

10957 *Let S ^{2} be the unit sphere in R^{3}. Let D be a domain in S^{2}
with piecewise smooth boundary. Let N denote the inward normal vector in any point of D,
and n the inward normal vector tangent to the sphere in any point of the boundary.
Let sigma be the area measure on D and s the arc length on the boundary. Prove that *

2*double-integral-over-D N d(sigma) + line-integral-over-boundary n ds = 0.

__Solution 1:__

If we take for D the northern hemisphere, then the first term of the
left hand side is 2*2*pi*(0,0,-1/2) and the second term 2*pi*(0,0,1), and we get the idea that the
assertion might be always true.

About the general case:

Let D: **x** = (r cos(t), r sin(t), sqrt(1-r^{2})) = -**N**, with t between 0 and 2*pi
and r between 0 and r(t). Then we find after a bit of calculation:

length(**x**_{r} outerproduct **x**_{t}) = r/sqrt(1-r^{2}), so
d(sigma) = r/sqrt(1-r^{2}) dr dt .

So the first term at the left hand side in the problem equals

2*INT(0 to 2*pi) INT(0 to r(t)) (-r cos(t),-r sin(t), -sqrt(1-r^{2})) r/sqrt(1-r^{2}) dr dt.

For the boundary curve we find after a bit of calculation (writing r for r(t)):

ds = length(**x**') dt =
sqrt((r')^{2}+r^{2}-r^{4})/sqrt(1-r^{2}) dt.

Furthermore, **n** has the direction of **x** outerproduct **x'**, and equals

(-r' sin(t) - r cos(t) (1-r^{2}), r' cos(t) - r sin(t) (1-r^{2}),
r^{2}sqrt(1-r^{2}))/sqrt((r')^{2}+r^{2}-r^{4}).

So the second term at the left hand side in the problem equals

INT(0 to 2*pi) (-r' sin(t) - r cos(t) (1-r^{2}), r' cos(t) - r sin(t) (1-r^{2}),
r^{2}sqrt(1-r^{2}))/sqrt(1-r^{2}) dt.

It is now straightforward to verify that each of the three coordinates in the sum at the left
hand side
in the problem is 0. We use:

INT(r^{2}/sqrt(1-r^{2})) = (-r/2)sqrt(1-r^{2}) +
arcsin(r)/2 + C, and

INT(0 to 2*pi) (r' sin(t)/sqrt(1-r^{2}) + arcsin(r) cos(t)) dt =
[arcsin(r) sin(t)](in 2*pi minus in 0) = 0.

If D doesn't fit in one hemisphere, then you can cut D into two pieces with a common boundary
where the inward normal vectors point in opposite directions.

Let us try to generalize. The assertion of the problem does not hold for an arbitrary ellipsoid.
But if we replace the unit sphere S^{2} in R^{3} by the unit circle S^{1}
in R^{2} and D is {(cos(alpha),sin(alpha))/alpha between -phi and phi} with
boundary {-phi,phi}, then we do have: SUM(alpha in {-phi,phi}/**n**) = (sin(phi),-cos(phi)) +
(sin(phi),cos(phi)) = (2*sin(phi),0) = INT(-phi to phi) (cos(alpha),sin(alpha)) d(alpha) =
INT(-phi to phi) (-**N**) ds, so we may try to generalize to S^{n} in R^{n+1}
with in the first term at the left hand side in the problem f(n) instead of 2
(and f(1)=1, f(2)=2).

If D:(r*sin(u)cos(v), r*sin(u)sin(v), r*cos(u), sqrt(1-r^{2})) with u between
0 and pi, v between 0 and 2*pi, r between 0 and a constant c, then the fourth coordinate
at the left hand side in the problem is -f(3)*(4/3)*pi*c^{3}+4*pi*c^{3} (and
the first three are 0). So if the generalisation holds, then f(3)=3.

__Solution 2:__

(with thanks to E.Reuvers, R.Kortram and F.Clauwens, who gave the hint
that one can apply Stokes' theorem to differential forms in each coordinate.)

Suppose D: **x**=(x_{1},x_{2},sqrt(1-x_{1}^{2}-x_{2}^{2})),
with on the boundary x_{1}=x_{1}(s), x_{2}=x_{2}(s) (using for
the boundary arc length s).

For the inward normal **N** on D we have **x**=-**N**, and for the tangent **T** to
the boundary we have

**T**=**x**'=(x_{1}',x_{2}',
(-x_{1}x_{1}'-x_{2}x_{2}')/
sqrt(1-x_{1}^{2}-x_{2}^{2})).

We find the inward normal vector **n** that is tangent to S^{2} as the vectorproduct
of **T** and **N** (or **x** and **x**').

So in line-integral-over-boundary **n** ds we have in the first coordinate

integral (-x_{1}x_{2}x_{1}'-x_{2}^{2}x_{2}')/
sqrt(1-x_{1}^{2}-x_{2}^{2}) -
x_{2}'sqrt(1-x_{1}^{2}-x_{2}^{2}) ds =

integral (-x_{1}x_{2})/sqrt(1-x_{1}^{2}-x_{2}^{2})
dx_{1} + (x_{1}^{2}-1)/sqrt(1-x_{1}^{2}-x_{2}^{2})
dx_{2}.

Now we apply Stokes' theorem:

integral f_{1} dx_{1} + f_{2}dx_{2} + f_{3}dx_{3} =
double-integral (innerproduct (rotation(f_{1},f_{2},f_{3}),-**N**) d(sigma).

We find after a bit of calculation: double-integral 2x_{1} d(sigma).

In the same way we find that the second coordinate of the line-integral is equal to

double-integral 2x_{2} d(sigma), and the third to
double-integral 2*sqrt(1-x_{1}^{2}-x_{2}^{2}) d(sigma).

Hence we have proved the formula of the problem.

One can generalize to D: **x**=(x_{1},x_{2},...,x_{n},sqrt(1-
x_{1}^{2}-x_{2}^{2}-...-x_{n}^{2})), using
the generalized theorem of Stokes.

10961 * Let rho=inf{r:there is only a finite number of rationals p/q with abs(pi-p/q) smaller than
1/q ^{r}}. It is known that rho is at least 2 and smaller than 41/5.
For any nonnegative real k, let L_{k}=liminf n^{k}abs(sin(n)) where n runs through the
natural numbers.
a) Prove that L_{k} is a finite real number if k is smaller than rho-1 (or k=1).
b) Prove that L_{k} is infinite if k is greater than rho-1.*

__Solution to a):__

Suppose k is smaller than rho-1. Then there is an infinite number of naturals p (and for any
such p exactly one natural q) such that abs(pi-p/q) is smaller than 1/q^{k+1} and thus
abs(q*pi-p) smaller than 1/q^{k}.

For any such p we have: p^{k}abs(sin(p))=p^{k}abs(sin(p-q*pi)) is smaller than
(p/q)^{k}, and thus at most (pi+1)^{k}.

So there must be an accumulation point smaller than or equal to (pi+1)^{k}.

__ Concerning b):__ I suspected that this is not true. But it is.

10965 *Given a triangle ABC with unit area and a point P inside the triangle or on its
boundary, show that PA + PB + PC is at least 2*sqrt(sqrt(3)).*

__Solution:__

First suppose that P lies inside.

Let x,y,z be the distances from P to A,B,C.

The problem then is equivalent to minimizing x+y+z under the restrictions that x,y,z are
positive,

and that x*y*sin(u)+x*z*sin(v)+y*z*sin(w)=2 for positive u,v,w (each smaller than pi)
with u+v+w=2*pi.

For fixed u,v,w we find the minimum of x+y+z by Lagrange's method:

x=lambda*sin(w)*(sin(u)+sin(v)-sin(w)),

y=lambda*sin(v)*(sin(u)+sin(w)-sin(v)),

z=lambda*sin(u)*(sin(v)+sin(w)-sin(u)), with

lambda=sqrt(2)/sqrt(sin(u)*sin(v)*sin(w)*(2*sin(u)*sin(v)+2*sin(u)*sin(w)+2*sin(v)*sin(w)-
sin^{2}(u)-sin^{2}(v)-sin^{2}(w)),

so after a bit of calculation (using sin(u)=-sin(v+w), sin(v)=-sin(u+w), sin(w)=-sin(u+v)) we find:

x+y+z has minimum 2*sqrt(cotan(u/2)+cotan(v/2)+cotan(w/2)).

It is straightforward to show that this minimum is at least 2*sqrt(sqrt(3)), with equality
if u=v=w=2*pi/3.

Now the assertion of the problem follows, using continuity.

__Remark:__ Jos Jansen used the point of Torricelli to solve this problem.

10966 a) *Let phi be the Euler phi function, and let gamma(n) = product(p divides n) p,
where p denotes a prime. Prove that there are exactly six positive integers such that phi(n)=
(gamma(n)) ^{2}.*

*
b) (the proposer of this question did not supply a solution) Let sigma(n) be the sum of divisors of n.
Prove or disprove that the only solutions to sigma(n) = (gamma(n)) ^{2} are n=1 and n=1782. *

__Solution to a):__

In the wellknown book "The Theory of Numbers" by Hardy and Wright we find:

phi(n) = n*product(p divides n) (p-1)/p.

If phi(n)=(gamma(n))^{2}, then we deduce:

product(p divides n) p^{3} = n*product(p divides n) (p-1).

We compare the number of prime factors 2 at the left and right hand sides of this equality.

We find, to begin with, that n has at most three prime factors 2. So let n=2^{k}m, with
m odd.

If k=0 we derive from that n must be __1__.

If k=3 then n must be __8__.

If k=2 then n must be 4p^{a} with 8p^{3}=4p^{a}(p-1), so p=3 and a=3 and
n is 2^{2}3^{3}, that is __108__.

If k=1 then n=2p^{a} or n=2p_{1}^{b}p_{2}^{c}.

In the first case we have 8p^{3}=2p^{a}(p-1), so p=5 and a=3, which yields

n is 2*5^{3}, so n is __250__.

In the second case (with p_{1} smaller than p_{2}) we have:

8p_{1}^{3}p_{2}^{3} = 2p_{1}^{b}p_{2}^{c}
(p_{1}-1)(p_{2}-1).

Hence p_{1}=3 and c=3 and 2*3^{3}=3^{b}(p_{2}-1).

If b=1 then p_{2}=19, and n is 2*3*19^{3}, that is __41154__.

If b=2 then p_{2}=7, and n is 2*3^{2}*7^{3}, that is __6174__.

For b=0 and for b=3 we find a contradiction.

__Partial solution to b):__

Suppose n=p_{1}^{a1}p_{2}^{a2}...p_{k}^{ak}
(k at least 1, the k prime factors written down in increasing order, and each exponent at least 1).

Suppose (gamma(n))^{2} = sigma(n).

We will prove that if n is not 1782, then k is at least 4, p_{1}=2, and aj=1 for some j
greater than 1.

The proof is as follows: we have

(*)
p_{1}^{2}p_{2}^{2}...p_{k}^{2} =
(1+p_{1}+...+p_{1}^{a1})(1+p_{2}+...+p_{2}^{a2})
...(1+p_{k}+...+p_{k}^{ak}).

If k=1 we have (writing p instead of p_{1} and a instead of a1)

p^{2}=1+p+...+p^{a}.

This is a contradiction, since the right hand side is not divisible by p.

If k=2 we have (writing p,q instead of p_{1},p_{2} resp. and a,b instead of a1,a2)

p^{2}q^{2}=(1+p+...+p^{a})(1+q+...+q^{b}).

At least one of a,b must be 1, because otherwise the right hand side is greater than the left
hand side.

If a=1 then q^{2}=1+p, a contradiction since p is smaller than q. So b=1 and

p^{2}q^{2}=(1+p+...+p^{a})(1+q).

Since 1+q is even, we find p=2 and

4q^{2}=(1+2+...+2^{a})(1+q).

Then 1+q=4 and 9=1+2+...+2^{a}, a contradiction.

If k=3 we have (writing p,q,r instead of p_{1},p_{2},p_{3}, and a,b,c instead
of a1,a2,a3):

p^{2}q^{2}r^{2}=(1+p+...+p^{a})(1+q+...+q^{b})(1+r+...
+r^{c}).

At least one of a,b,c must be 1.

And a is greater than 1, since otherwise the right hand would
have a prime factor smaller than p.

Since both 1+q and 1+r are even, we find p=2 and, say, b=1 (dropping the condition that
q is smaller than r).

So, after summing up the powers of 2, we find:

4q^{2}r^{2}=(2^{a+1}-1)(1+q)(1+r+...+r^{c}).

If 1+q=4 then 1+r+...+r^{c} is 1,3 or 9, a contradiction. So 1+q is divisible by r.

Now we distinguish the following cases:

(A) 1+q=2r ,(B) 1+q=4r ,(C) 1+q=2r^{2} ,(D) 1+q=4r^{2}.

CASE A: We find

2q^{2}r=(2^{a+1}-1)(1+r+...+r^{c}).

If 2^{a+1}-1=r then 1+r+...+r^{c}=2q^{2}=8r^{2}-8r+2.
Then r divides 1, a contradiction.

If 2^{a+1}-1=qr then 1+r+...+r^{c}=2q=4r-1.
Then r divides 2, a contradiction.

If 2^{a+1}-1=q^{2}r then 1+r+...+r^{c}=2, a contradiction.

CASE B: We find

q^{2}r=(2^{a+1}-1)(1+r+...+r^{c}).

If 2^{a+1}-1=r then 1+r+...+r^{c}=q^{2}=16r^{2}-8r+1.

Hence 9r+..=16r^{2}. So r=3 and a=1 and 1+3+..+3^{c}=q^{2}=121.

This yields n=2*3^{4}*11=1782.

If 2^{a+1}-1=qr then 1+r+...+r^{c}=q=4r-1. So r divides 2, a contradiction.

If 2^{a+1}-1=q^{2}r then 1+r+...+r^{c}=1, a contradiction.

CASE C: We find

2q^{2}=(2^{a+1}-1)(1+r+...+r^{c}).

If 2^{a+1}-1=q then 2^{a+1}-1=2r^{2}-1, a contradiction.

If 2^{a+1}-1=q^{2} then 1+r+...+r^{c}=2, a contradiction.

CASE D: We find

q^{2}=(2^{a+1}-1)(1+r+...+r^{c}).

Then 2^{a+1}-1=q=4r^{2}-1. So 4r^{2}=2^{a+1}, a contradiction.

General conclusion: if n is not 1782 then k is at least 4.

Furthermore we find from (*):

some aj with j greater than 1 must be 1, otherwise the left hand side of (*) is smaller than the
right hand side.

Since 1+p_{j} is even, we find p_{1}=2.

10967 * Let A be the adjacency matrix of a simple graph G.
a) For which G is A the incidence matrix of a simple graph?
b) For which G is A the incidence matrix of a graph isomorphic to G?*

__Solution:__

Let G have vertices v_{1},v_{2},...,v_{m}, and edges e_{1},
e_{2},...,e_{n}. Since G is simple, it contains no loops or multiple edges.
So A is a m by m symmetric matrix with entries 0 and 1 only, and on the main diagonal only 0.

a) If A is equal to the incidence matrix I ' of a simple graph G' with vertices
v_{1}',v_{2}',...,v_{p}' and edges e_{1}',e_{2}',...,
e_{q}', then p=q=m, and for any i v_{i}' is not incident with e_{i}',
and for any i,j v_{i}' is incident with e_{j}' if and only if v_{j}' is
incident with v_{i}'. But these restrictions apply to G', not to G.

Now since I '=A has m distinct columns with in each column exactly two 1's, each vertex of G is
joined to exactly two other vertices (called neighbours), and no two vertices have the same two
neighbours. So G is a (non-empty) collection of disjoint polygons, containing no quadrangles.

b) If G' is to be isomorphic with G, then since p=q=m and q=n, we find next the restrictions found in a)
also m=n. But, at second sight, this applies already to the graphs G found in a).

Furthermore, it must be possible to give to the vertices and edges of G new indexnumbers in such
a way that for all i v_{i} is not incident with e_{i} and for all j,k v_{j}
is incident with e_{k} if and only if v_{k} is incident with e_{j}.
Or, which amounts to the same, such that
for each i there exist j,k distinct from i such that e_{i}=v_{j}v_{k}
and v_{k}=e_{i}*e_{j}.

This can be done with single n-gons if n is odd (for if it can be done with a single
n-gon, a simple procedure shows that it can be done with a single (n+2)-gon; and it can be done
with a triangle). That means, single n-gons with odd n can be "self-dual".

But it cannot be done with single n-gons if n is even (for if it can be done with a single
n-gon, a simple procedure shows that it can be done with a single (n-2)-gon; and it cannot be
done with a single quadrangle).

Furthermore, for any polygon we can number the edges 1 to n and the vertices n+1 to 2n, and associate with it
a "dual" polygon with edges numbered n+1 to 2n and vertices numbered 1 to n, in such a way that
for each i there exist j,k distinct from i with e_{i}=v_{j}v_{k}
and v_{k}=e_{i}*e_{j}.

So G can be any collection of disjoint polygons where for each even n the number of n-gons in the
collection is even.

But can the number of n-gons with even n also be odd? No! In G, any polygon with an even number of edges
must be dual to a distinct polygon with as many edges (though not necessarily with numbering as
described above).

HOME