Conference rusure::math

Yes.  The key is to notice that an important quantity is the product of all 8
vertex numbers.  If this product is -1 (which happens, e.g., if exactly one
vertex number is -1) then opposite faces will have their values sum to 0, so the
total will be 0.

If not, the sums of opposite faces will be +2 or -2, and it is easy to see that
three such numbers can't sum to 0.

(b) no: cut off teeth at 0, 1, 3, and 9 (mod 13).  Every difference mod 13
occurs as some difference between two cut locations, so no matter how you rotate
one cog with respect to the other, two cut locations land on top of one another.

+-1 to +-6 occur as the differences between 1-0, 3-1, 3-0, 0-9, 1-9, 9-3
respectively.

(a) yes: the number of nonzero differences that can occur are at most 4(4-1) =
12, and there are 13 nonzero values mod 14.  So some difference must be
unaccounted for, and if you rotate the cogs by that relative amount, there will
be no matching cut-off teeth.

    re .1
    
    This answer seems a bit brief. I interpretted the problem to be to show
    that the sum of the numbers assigned to the 8 vertices and the 6 faces
    cannot be 0. You talk about the face sum but not the vertex sum.
    
    Where the vertex product is -1 (the face sum is 0 ) it is easy to see that
    the vertex sum cannot be 0 and hence that the total sum cannot be 0.
    
    Where the vertex product is 1 (the face sum cannot be 0) it is not
    totally obvious to me that the total sum cannot be 0.

Assuming the interpretation where we are summing 8+6 numbers, it is impossible
to obtain a zero sum.  If the number of -1 vertices is n, the vertex total is
8-2n.  By the argument presented in .1, if n is odd, the face total is 0, so we
would need to have 8-2n = 0, which would make n = 4 contrary to the assumption
that n is odd.

Otherwise, n is even, so 8-2n is divisible by 4; but the total of opposite faces
is always +2 or -2 in this case, so the face total is == 2+2+2 == 2 (mod 4).  So
in any case, the total of all 14 numbers can't be 0.

If the solutions will be published, I'm curious what their interpretation was.

Let A and B be adjacent vertices.  Consider starting in a configuration in which
all diagonals pass through A, and ending with all passing through B.

Initially, no diagonals pass through B, and finally n-3 of them do.  But each
perestroyka can change the number of diagonals passing through B by at most 1,
so P(n) >= n-3.

Actually, I would consider P(3) well defined and = 0, which means that 4(b)
should have the condition n >= 4.  I will prove the stronger result that

    P(4) = 1, and P(n) <= 2n-8 for n > 4.

P(4) = 1 is easy: there are only two configurations, and a perestroyka changes
one for the other.

Lemma 1.  If n > 3, for every vertex P, either a diagonal passes through P or
there is a diagonal connecting P's two neighbors.

Proof.  (By induction on n) If n > 3, there is a diagonal.  If P is on it, we
are done; otherwise the diagonal divides the n-gon into smaller polygons. 
Consider the polygon containing P.  If it is a triangle, we are done, otherwise
we use induction on the number of vertices in the polygon to obtain our result.

Lemma 2.  Let C be a configuration in which d diagonals pass through the vertex
P. Then changing C to the configuration with all diagonals through P (or vice
versa) requires at most n-3-d perestroykas.

Proof (by induction on n).  If d > 1, we take some diagonal through P; it
partitions the n-gon into polygons with k sides and d' diagonals through P, and
one with n-k+2 sides and d-d'-1 diagonals through P.  So by induction we can
transform the subpolygons separately in at most (k-3-d')+(n-k+2-3-(d-d'-1)) =
n-3+d steps.

If d = 0, there is a diagonal through P's neighbors, and 1 perestroyka will move
that diagonal to be through P, and then we can apply the d > 0 case.

Lemma 3.  If n > 4, there is some vertex with two diagonals through it.

Proof. Left to the reader.

We can now combine these lemmas as follows.  Let the initial configuration be A,
and the final one B.  In B, choose a vertex P with at least 2 diagonals through
it, and let C be the configuration with all diagonals through P.  We can move
from A to C in at most n-3 steps, and C to B in at most n-5, so P(n) <= 2n-8.

By the lemmas in .6 it suffices to show that if n >= 13, for any two
configurations A and B there exists some vertex P such that there are at least 4
diagonals through P in A and B combined.  (We convert to an intermediate
configuration with all diagonals through P.)

Assume for any vertex there are at most 3 such diagonals; let us count endpoints
of diagonals in A and B combined.  (That is, we count ordered pairs <D, P> where
D is a diagonal and P an endpoint of D.)  By the assumption, counting around the
n vertices, the count is at most 3n; but the count must be exactly 2(2n-6) =
4n-12, since there are exactly n-3 diagonals in each of A and B, each with two
endpoints.  So 3n >= 4n-12, which implies n <= 12.

Apologies for an imprecision.  When dealing with diagonals in the preceding
proof, the diagonals of A must be considered distinct from those of B even when
they connect the same points.  Consider them painted red and blue, or tagged in
some other manner; more precisely, consider them to be triples <X, D, P> where X
is either A or B.  (If A=B we don't have any trouble :-)

re .4
    
>If the solutions will be published, I'm curious what their interpretation was.
    
    A thousand pardons! I went back and checked the actual problem
    statement and in fact it should have read:
    
1. One of the numbers 1 or -1 is assigned to each vertex of a cube. To each
face of the cube is assigned the integer which is the product of the four
integers at the vertices of the face. Is it possible that the sum of the 14
assigned integers is 0?			(3 points)
    
    in which case there is no ambiguity. Aaaaaaaarrrrrrgggggghhhhh!
    
    Given the competition date (November 1988) I would imagine that
    solutions are already available (and if not, they never will be).
    
    
    For the record, I offer my approach to this problem.
    
    Claim: The sum can never be 0.
    
    Proof:
    
    It will be shown that the sum is always congruent to 2 (mod 4). This
    will be shown by
    
    1. Finding an assignment to the vertices that satisfies this condition,
    
    and
    
    2. Showing that this condition is invariant under the operation of
    negating one vertex (and adjusting the three affected faces
    accordingly i.e. negating them too).
    
    The first point is clearly satisfied by assigning 1 to each vertex
    which results in 1 being assigned to each face for a total sum of 14.
    
    The second point can be established simply but tediously by enumerating
    the eight cases for the configuration before the vertex is negated and
    the change to the total sum that arises from negating the vertex.
    
    Vertex	Faces		Change to total sum
    ======	=====		===================
    
    1		1,1,1		-8
    1		1,1,-1		-4
    1		1,-1,-1         0
    1		-1,-1,-1        +4
    -1		1,1,1		-4
    -1		1,1,-1          0
    -1		1,-1,-1         +4
    -1		-1,-1,-1        +8
    
    Since the change to the total sum is always a multiple of 4, the
    condition is invariant.
    
    Clearly a maximum of eight vertex negations is sufficient to derive any
    possible assignment of the vertices from the assignment of 1 to each
    vertex.
    
    So the result follows.

The point M can't be within the triangle ABC, as then ACM would be less than
pi/4 and MCD would be greater than pi/4.  Similarly it's not on AC, so it is
within ACD.  Now ACM+MCD = pi/4, so ACM = pi/4-x and AMC = pi-(x+pi/4-x) =
3pi/4.  Therefore, by Euclid, M is on the quarter circle with center B and
radius AB that is within the square.  So AB = BM, and angles BAM and BMA are
both equal to x+pi/4.  Thus ABM = pi - 2(x+pi/4) = pi/2 - 2x.

Yes; such a number is q = 10^221 - 1.  I assume that the question disallows 0 as
a natural number divisible by q.  ("Natural number" nowadays is usually taken to
include 0 nowadays and hereabouts, but presumably isn't here.)

We wish to show that no nontrivial sum of <= 1988 distinct powers of 10 is == 0
(mod q).  So suppose the contrary; since 10^(n+221) == 10^n (mod q) for all n,
we can rewrite this as

    sum   k[i]*10^i  == 0 (mod q), all k[i] integers >= 0, not all k[i] = 0,
  0<=i<221
                                              and sum(k[i]) <= 1988

So assume we have such a sum with minimal sum of k[i].  I claim all k[i] < 10,
otherwise we could reduce (say) k[j] by 10 and add 1 to k[(j+1) mod 221] and get
a different nontrivial sum with smaller sum of k[i].

In this sum, then, all k[i] are at most 9, but if all of them were 9 the sum of
k[i] would be 9*221 = 1989, so at least one of the k[i] is less than 9. 
Therefore the sum of k[i]*10^i is at most 9+...+9*10^220 - 1 = 10^221 - 2 = q -
1.  But the sum is greater than 0 and == 0 (mod q), which is a contradiction.

    re .10
    
>Therefore, by Euclid, M is on the quarter circle with center B and
>radius AB that is within the square.
    
    I wasn't previously familiar with this theorem.
    
    It is easy to show that...
    
    If O is the centre of a circle and A, B and C are on the circumference
    of the circle and angle AOC = � then angle ABC = pi - �/2. For �=pi
    this is the special case of the angle in a semi-circle.
    
    However the proof in .10 relies on the converse of the above theorem
    which one could state as...
    
    If OABC is a quadrilateral and the length of OA equals the length of OC
    and angle ABC = pi - �/2 where � denotes angle AOC then the length of
    OB equals the length of OA (i.e. A, B and C are on a circle centred at O).
    
    It is easy to prove this converse for the case �=pi but I can only come
    up with a somewhat hand-wavy proof for general �. Can anyone provide a
    proof for �=pi/2 (as required for .10) or, better still, for general �?
    
    re .11
    
    Neat proof!

M is not on the line AC, so there is a unique circle through AMC; the center of
this circle must lie on the perpendicular bisector of AC, which is BD. 
Furthermore the circle AMC cuts BD in two points, one of which is on the same
side of AC as M.  Call this point P.  Then angle AMC equals angle APC; but it is
easy to see that, for any given angle between 0 and pi, only one such point on
BD (and on the same side of AC as D) subtends just that angle.  So (taking the
angle to be 3pi/4) the point P must be that point such that the circle APC has
center B.