Solutions by H Reuvers, part 1

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 A1, .. , An be the vertices, and AiAi+1 the sides (with n+1 "=" 1).
Choose the first point in the interior of the intersection of the triangles A1A2Ak 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 A1 A3Ak 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 A1Aj+1Ak 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 A1.
Now it is easy to verify that for any i smaller than j and j smaller than k, the triangle AiAjAk 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 = a2b2c2 - (b2+c2- a2)(c2+a2-b2)(a2+b2- c2).

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*r2 = 4*b2-4*b*c*cos(alpha)+c2-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 b2*c2*sin2(alpha) and a bit of calculation:
(12*D*r)2 = b2*c2*(b2+c2+8* (b2+c2)* cos2(alpha)+8*b*c*cos(alpha)*sin2 (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 b2+c2=a2+2*b*c*cos(alpha) and sin2(alpha)+cos2(alpha)=1, and find for the right hand side:
b2*c2*(a2+8*a2*cos2(alpha)-8*b*c*cos(alpha)* sin2(alpha)) = a2*b2*c2(1+8*cos2(alpha)) -2*b*c*cos(alpha)*(16*D2).

By symmetry we find for the right hand side:
a2*b2*c2(1+8*cos2(alpha)) -2*b*c*cos(alpha)*(16*D2) =
a2*b2*c2(1+8*cos2(beta)) -2*a*c*cos(beta)*(16*D2) =
a2*b2*c2(1+8*cos2(gamma)) -2*a*b*cos(gamma)*(16*D2).
We add these three equal expressions, and divide by 3. Then we find for the right hand side, after using all three cosinus-rules:
a2*b2*c2 + (1/3)*a2*b2*c2* (8*cos2(alpha)+8*cos2(beta)+8*cos2(gamma))-(16/3)*D2* (a2+b2+c2).

We use 4*D2 = b2*c2*sin2(alpha) = a2*c2*sin2(beta) = a2*b2* sin2(gamma), and find:
a2*b2*c2 + (1/3)*a2*b2*c2* (8*cos2(alpha)+8*cos2(beta)+8*cos2(gamma)-4*sin2(alpha) -4*sin2(beta)-4*sin2(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)*a2*b2*c2* (8*cos2(alpha)+8*cos2(beta)+8*cos2(gamma)-4*sin2(alpha) -4*sin2(beta)-4*sin2(gamma)) =
a2*b2*c2*( 8-4*sin2(alpha)-4*sin2(beta)-4*sin2(gamma)) =
a2*b2*c2*(8-8*sin2(alpha)-8*sin2(beta)+ 8*sin2(alpha)*sin2(beta)-8*sin(alpha)*sin(beta)*cos(alpha)*cos(beta)) =
8*(1-sin2(alpha))(1-sin2(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
a2*b2*c2 - 8*a2*b2*c2* cos(alpha)*cos(beta)*cos(gamma).

Using the three forms of the cosinusrule, we find that this equals
a2*b2*c2 - (b2+c2-a2)(c2+a2-b2)(a2+b2- c2), 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 M1:(1/(1-b2))*(a*cos(gamma), a*sin(gamma)) and radius r1 = a*b/(1-b2).
And a'/a = c'/c is a circle with center M2:(1/(1-a2))*(b,0) and radius r2 = a*b/(1-a2).
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) r1 + r2 > distance(M1,M2)
3) a2+b2-2*a*b*cos(gamma) < (a2+b2)2
4) c2=1 < a2+b2
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 M1M2 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 M1(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 2e3t5d7v. 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 = R2-b*c*(b+c)/(a+b+c)+2*b2*c2*(1+cos(alpha))/ (a+b+c)2 = R2-a*b*c/(a+b+c) = R2-2*r*R,
(OG)2=R2-(a2+b2+c2)/9,
(IG)2=2*b2*c2*(1+cos(alpha))/(a+b+c)2- 2*b*c*(b+c)*(1+cos(alpha)/(3*(a+b+c))+(2*b2+2*c2-a2)/9 =
= (2*b*c*(b+c)+2*a*c*(a+c)+2*a*b*(a+b)-a3-b3-c3-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+r2+D2/r2, and hence
(OI)2 = R2-2*r*R,
(OG)2 = R2+8*r*R/9+2*r2/9-2*D2/(9*r2),
(IG)2 = -16*r*R/9+5*r2/9+D2/(9*r2).
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 S2 be the unit sphere in R3. Let D be a domain in S2 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-r2)) = -N, with t between 0 and 2*pi and r between 0 and r(t). Then we find after a bit of calculation:
length(xr outerproduct xt) = r/sqrt(1-r2), so d(sigma) = r/sqrt(1-r2) 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-r2)) r/sqrt(1-r2) 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+r2-r4)/sqrt(1-r2) dt.
Furthermore, n has the direction of x outerproduct x', and equals
(-r' sin(t) - r cos(t) (1-r2), r' cos(t) - r sin(t) (1-r2), r2sqrt(1-r2))/sqrt((r')2+r2-r4).
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-r2), r' cos(t) - r sin(t) (1-r2), r2sqrt(1-r2))/sqrt(1-r2) 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(r2/sqrt(1-r2)) = (-r/2)sqrt(1-r2) + arcsin(r)/2 + C, and
INT(0 to 2*pi) (r' sin(t)/sqrt(1-r2) + 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 S2 in R3 by the unit circle S1 in R2 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 Sn in Rn+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-r2)) 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*c3+4*pi*c3 (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=(x1,x2,sqrt(1-x12-x22)), with on the boundary x1=x1(s), x2=x2(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'=(x1',x2', (-x1x1'-x2x2')/ sqrt(1-x12-x22)).
We find the inward normal vector n that is tangent to S2 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 (-x1x2x1'-x22x2')/ sqrt(1-x12-x22) - x2'sqrt(1-x12-x22) ds =
integral (-x1x2)/sqrt(1-x12-x22) dx1 + (x12-1)/sqrt(1-x12-x22) dx2.
Now we apply Stokes' theorem:
integral f1 dx1 + f2dx2 + f3dx3 = double-integral (innerproduct (rotation(f1,f2,f3),-N) d(sigma).
We find after a bit of calculation: double-integral 2x1 d(sigma).
In the same way we find that the second coordinate of the line-integral is equal to
double-integral 2x2 d(sigma), and the third to double-integral 2*sqrt(1-x12-x22) d(sigma).
Hence we have proved the formula of the problem.
One can generalize to D: x=(x1,x2,...,xn,sqrt(1- x12-x22-...-xn2)), 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/qr}. It is known that rho is at least 2 and smaller than 41/5.
For any nonnegative real k, let Lk=liminf nkabs(sin(n)) where n runs through the natural numbers.
a) Prove that Lk is a finite real number if k is smaller than rho-1 (or k=1).
b) Prove that Lk 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/qk+1 and thus abs(q*pi-p) smaller than 1/qk.
For any such p we have: pkabs(sin(p))=pkabs(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)- sin2(u)-sin2(v)-sin2(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) p3 = 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=2km, 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 4pa with 8p3=4pa(p-1), so p=3 and a=3 and n is 2233, that is 108.
If k=1 then n=2pa or n=2p1bp2c.
In the first case we have 8p3=2pa(p-1), so p=5 and a=3, which yields
n is 2*53, so n is 250.
In the second case (with p1 smaller than p2) we have:
8p13p23 = 2p1bp2c (p1-1)(p2-1).
Hence p1=3 and c=3 and 2*33=3b(p2-1).
If b=1 then p2=19, and n is 2*3*193, that is 41154.
If b=2 then p2=7, and n is 2*32*73, that is 6174.
For b=0 and for b=3 we find a contradiction.

Partial solution to b):

Suppose n=p1a1p2a2...pkak (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, p1=2, and aj=1 for some j greater than 1.
The proof is as follows: we have
(*) p12p22...pk2 = (1+p1+...+p1a1)(1+p2+...+p2a2) ...(1+pk+...+pkak).
If k=1 we have (writing p instead of p1 and a instead of a1)
p2=1+p+...+pa.
This is a contradiction, since the right hand side is not divisible by p.
If k=2 we have (writing p,q instead of p1,p2 resp. and a,b instead of a1,a2)
p2q2=(1+p+...+pa)(1+q+...+qb).
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 q2=1+p, a contradiction since p is smaller than q. So b=1 and
p2q2=(1+p+...+pa)(1+q).
Since 1+q is even, we find p=2 and
4q2=(1+2+...+2a)(1+q).
Then 1+q=4 and 9=1+2+...+2a, a contradiction.
If k=3 we have (writing p,q,r instead of p1,p2,p3, and a,b,c instead of a1,a2,a3):
p2q2r2=(1+p+...+pa)(1+q+...+qb)(1+r+... +rc).
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:
4q2r2=(2a+1-1)(1+q)(1+r+...+rc).
If 1+q=4 then 1+r+...+rc 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=2r2 ,(D) 1+q=4r2.
CASE A: We find
2q2r=(2a+1-1)(1+r+...+rc).
If 2a+1-1=r then 1+r+...+rc=2q2=8r2-8r+2. Then r divides 1, a contradiction.
If 2a+1-1=qr then 1+r+...+rc=2q=4r-1. Then r divides 2, a contradiction.
If 2a+1-1=q2r then 1+r+...+rc=2, a contradiction.
CASE B: We find
q2r=(2a+1-1)(1+r+...+rc).
If 2a+1-1=r then 1+r+...+rc=q2=16r2-8r+1.
Hence 9r+..=16r2. So r=3 and a=1 and 1+3+..+3c=q2=121.
This yields n=2*34*11=1782.
If 2a+1-1=qr then 1+r+...+rc=q=4r-1. So r divides 2, a contradiction.
If 2a+1-1=q2r then 1+r+...+rc=1, a contradiction.
CASE C: We find
2q2=(2a+1-1)(1+r+...+rc).
If 2a+1-1=q then 2a+1-1=2r2-1, a contradiction.
If 2a+1-1=q2 then 1+r+...+rc=2, a contradiction.
CASE D: We find
q2=(2a+1-1)(1+r+...+rc).
Then 2a+1-1=q=4r2-1. So 4r2=2a+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+pj is even, we find p1=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 v1,v2,...,vm, and edges e1, e2,...,en. 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 v1',v2',...,vp' and edges e1',e2',..., eq', then p=q=m, and for any i vi' is not incident with ei', and for any i,j vi' is incident with ej' if and only if vj' is incident with vi'. 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 vi is not incident with ei and for all j,k vj is incident with ek if and only if vk is incident with ej. Or, which amounts to the same, such that for each i there exist j,k distinct from i such that ei=vjvk and vk=ei*ej.
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 ei=vjvk and vk=ei*ej.
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).

More solutions: click here .
HOME