| ... and here are Andy's solutions:
From: HERON::BUCHANAN "combinatorial bomb squad" 30-AUG-1991 04:35:22.03
To: CIVAGE::LYNN
Subj:
Lynn,
Answers after spoiler:
Q: What is the smallest n such that any n-subset of {1,2,...,280}
contains at least five elements pairwise coprime?
A: Let's invert the problem, and look for sets containing at least one
representative from each quintet of pairwise coprime elements from U =
{1,2,...280}.
First, let's build such a set, S:
(i) 1 is in S
(ii) every prime from U is in S, except for 2,3,5,7.
(iii) 121, 143, 169, 187, 209, 221, 247, 253 lie in S.
Now suppose if possible that there is a quintet Q = {a,b,c,d,e} which is
disjoint from S. Since Q contains 5 numbers, at least one of them, e, is
coprime with respect to all of 2,3,5 & 7. Yet e is composite, since all
other primes lie in S. Since 17� > 280, one of the factors of e is 11 or
13, and soon we see that there are only eight possibilities for e. (iii)
excludes each of them individually.
Now what we want to prove is that S is the *smallest* set which is disjoint
from no quintet.
Suppose that T is disjoint from no quintet, and does not contain 1. Let t
be any element of T, then T \ {t} + {1} is disjoint from no quintet, and
has the same cardinality at T. So wlog, the smallest set disjoint from no
quintet contains 1.
Now, our smallest set can omit at most four prime powers (for if it omits a
fifth, the five form a quintet).
It is easy to construct eight pairwise disjoint quintets with no element a
prime, as in the following columns, and therefore T must contain at least
eight elements which are not primes.
11*13 11*17 11*19 11*23 13*17 13*19 11*11 13*13
2*17 2*19 2*23 2*29 2*11 2*31 2*13 2*41
3*19 3*23 3*29 3*13 3*31 3*17 3*41 3*37
5*23 5*29 5*13 5*17 5*19 5*37 5*31 5*11
7*29 7*13 7*17 7*19 7*23 7*11 7*37 7*31
Therefore S is of minimal cardinality. Therefore any set of cardinality
>= 1 + 280 - |S| must include a quintet, whereas U\S will not contain a
quintet. Thus n = 281 - |S|.
S = 1 + number of primes in {11,...,280} + 8
= 64.
So n = 217.
-------------------------------------------------------------------------------
Q: Let P be an interior point of a triangle ABC. Show that not all of the
angles PAB, PBC & PCA can exceed 30�.
A: Let PA,PB,PC be a,b,c respectively. Let angle PAB be denoted A, let BPA
be denoted A'. Similarly, B,B',C,C'.
By the sin rule, sin(A)/b = sin(pi-A-A')/a
Rearrranging, sin(A)/sin(A+A') = b/a.
Similarly, sin(B)/sin(B+B') = c/b.
and: sin(C)/sin(C+C') = c/b.
Multiplying these together, we get:
sin(A)sin(B)sin(C) = sin(A+A')sin(B+B')sin(C+C')
Expanding the sin(x+y) terms:
(cos(A')+cot(A)sin(A'))(cos(B')+cot(B)sin(B'))(cos(C')+cot(C)sin(C'))=1
Suppose if possible that A,B,C are all greater than pi/6.
cot(A) < _/3, etc.
Since sin(A') >= 0 (as P lies *inside* the triangle)
cot(A)sin(A') < _/3
Substituting:
(cos(A')+_/3sin(A'))(cos(B')+_/3sin(B'))(cos(C')+_/3sin(C')) > 1
call the lhs f(A',B',C')
Now, A'+B'+C' = 2*pi.
Now, state that the interval [A',B'] contains 2*pi/3 (wlog this is
possible.)
(cos(A')+_/3sin(A'))(cos(B')+_/3sin(B'))
= _/3sin(A'+B') - cos(A'+B') + 2cos|A'-B'|
If A'+B' is fixed, this is concave in A'-B'. So consider A" = 2*pi/3 and B"
= A'+B'-A". Then f(A',B',C') =< f(A",B",C'). SImilarly, considering B" &
C', have f(A",B".C') =< f(2*pi/3,2*pi/3,2*pi/3). But this = 1. So 1 < 1,
which is the required contradiction.
Therefore, not all of A,B & C are greater than pi/6.
|