Solutions by H Reuvers, part 4

11082 Let k be an odd positive integer. Determine the number Mk of positive integers n such that (7n-16) divides kn, and determine k such that Mk=2004.

Solution:

If 7n-16 divides kn, we have
m(7n-16) = kn for some integer m;
each odd prime divisor of n does not divide 7n-16, so must divide m; we get
m'(7n-16) = k*2a, where a is the number of factors 2 in n.

If a=0 we find that 7n-16 can be any divisor d of k such that d+16 is a positive 7-tuple;
If a=1 we find that 7(n/2)-8 can be any divisor d of k such that d+8 is a positive 7-tuple; (note that d can be -1)
If a=2 we find that 7(n/4)-4 can be any divisor d of k such that d+4 is a positive 7-tuple;
If a=3 we find that 7(n/8)-2 can be any divisor d of k such that d+2 is a positive 7-tuple;
If a is at least 4, we find that 7(n/16)-1 can be any divisor d of k such that d+1 is a positive 7-tuple;
we check that these possibilties exclude each other.
So Mk is twice the number of positive divisors of k that are congruent to 5 or 6 modulo 7, plus the number of positive divisors of k that are congruent to 3 modulo 7, plus 1 (corresponding to d=-1).

In order to make Mk=2004, we put k=3t, and note that the powers of 3 that divide k are congruent to (respectively) 3,2,6,4,5,1; each six powers give five solutions; therefore we must choose t equal to 2403, yielding (5/6)*2400 + 1+0+2 plus 1 = 2004 solutions.

11095 A trapezoid ABRS with AB parallel to RS is inscribed in a noncircular ellipse E with axes of symmetry l and m. The points A and B are reflected through l to points P and Q on E.
a) Show that P,Q,R and S are concyclic.
b) Show that if the line PQ intersects the line RS at T, then the angle bisectors of angle PTR are parallel to the axes.

Sketch of a solution:

Give coordinates A(a*cos(t4),b*sin(t4)), B(a*cos(t1),b*sin(t1)), R(a*cos(t2),b*sin(t2)), S(a*cos(t3),b*sin(t3)), P(a*cos(t4),-b*sin(t4)), Q(a*cos(t1),-b*sin(t1)).
Since AB is parallel to RS, we have
(&&&): (cos(t4)-cos(t1))/(sin(t4)-sin(t1))=(cos(t2)-cos(t3))/(sin(t2)-sin(t3)).
a) It is sufficient to show that the angle PQR is equal to the angle PQS. This can be done using the cosine rule and (&&&).
Alternatively, we could use (&&&) to show that the intersection point of the line through the midpoint of PQ and perpendicular to PQ, and the line through the midpoint of RS and perpendicular to RS, intersect in a point lying at equal distances from all four points P,Q,R,S.
b) Using (&&&), we easily show that the direction coefficients of the straight lines PQ and RS add to zero. So the bisectors are parallel to the axes.

Jubilee session problem
Find the maximal area of a square inscribed in some triangle with area 1.

Solution:

Let gamma be the greatest angle.
Give coordinates A(0,0), B(c,0), C(b*cos(alpha),b*sin(alpha)) with tan(beta) = b*sin(alpha)/(c-b*cos(alpha)).
Since the area is b*c*sin(alpha)/2=1, we deduce c2tan(alpha)*tan(beta)/(tan(alpha)+tan(beta))=2.
The maximal square has vertices (s,0), (s+t,0), (s,t) and (s+t,t) with t/s = tan(alpha) and t/(c-t-s) = tan(beta). We deduce that its area t2 equals c2tan2(alpha)tan2(beta)/(tan(alpha)+tan(beta)+tan(alpha)*tan(beta))2 =
2*u/(1+u)2 with u=tan(alpha)*tan(beta)/(tan(alpha)+tan(beta)).
This is maximal if u=1 and the maximum is 1/2.

11225 Find lim (n->inf) (1/n)*INT (0 to n) (x*log(1+x/n))/(1+x) dx.

Solution:

Substitute u=x/n. We get lim (n->inf) INT (0 to 1) (u*log(1+u))/(1/n+u) du.
Now the integrand converges uniformly to log(1+u), because the difference is at most 1/n on [0,1].
So we get INT (0 to 1) log(1+u) du.
Using integration by parts, we get 2*log(2)-1.

11226 Let a(1),...,a(n) be real numbers, each greater than 1. If n is at least 2, show there is exactly one solution in the interval (0,1) to
PRODUCT(j=1 to n: (1-xa(j))) = 1-x.

Graphical solution:

Let fn(x):=PRODUCT(j=1 to n: (1-xa(j))), and g(x):=1-x.
We first note that fn(0)=g(0)=1 and fn(1)=g(1)=0.
Notice that for all n we have fn'(0)=fn'(1)=0 (here we use both that n is at least 2 and that a(j) is greater than 1 for all j).

We proceed with induction to prove that the simultaneous picture of the graphs of fn(x) and g(x) is like THIS (bold lines).
For n=2, this is straightforward (study the first and second derivative of f2(x)).
Suppose the picture is correct for n=m, and consider fm+1(x)=fm(x)(1-xa(m+1)).
Since (1-xa(m+1)) decreases monotonously from 1 to 0 on [0,1] (and again fm+1'(0)=fm+1'(1)=0), we get a similar picture for n=m+1 (dotted line).

11227 Call an integer n blocky if n>1 and there is a run of n consecutive integer squares the average of which is a square. (Thus, 25 is blocky because (SUM k: 0 <=k<=24: k2)/25 = 142, and 31 is the next blocky integer.)
(a) Determine the set B of blocky integers.
(b) Given a blocky integer n, give a procedure that determines all integers k that can serve as starting points for required runs of squares.
(c) Give a formula in terms of n for the number of k that can serve as starting points for required runs of squares.

Solution:

Let m be the number the square of which is the average, and m-p a starting point, and m+q an endpoint, so n=p+q+1.
From (m-p)2 + ... + m2 + ... + (m+q)2 = (p+q+1)*m2 we derive
6(p-q)(p+q+1)m = p(p+1)(2p+1) + q(q+1)(2q+1).
Now substitute q=n-p-1. We find that both sides have a factor n. After simplification we get:
(***) 6(2p+1-n)m = 2n2 - n(6p+3) + (6p2+6p+1) = (2p+1-n)(2p+1-2n) + 2p2+2p.
So we find the following answers:

(a) We have: n in B iff there there exists a suitable pair (p,m) for n, i.e. integers p,m with (n div 2 <= p <= n-2) and (p <= m) for which the equality (***) holds.

(b) We notice that m can be at most 4n2/3, so for given n we can systematically find all suitable (p,m). If (p,m) is suitable then m-p is a starting point.

(c) f(n) = (the number of m for which there exists a p with (n div 2 <= p <= n-2) and (p <= m) satisfying (***) )

With the help of a pascal program I found all blocky integers n smaller than 100 with the associated suitable pairs (m,p):

 m-p m n 0 14 25 4 21 31 14 36 41 22 47 47 25 51 49 35 64 55 10 46 65 55 89 65 69 106 71 74 112 73 24 67 79 90 131 79 8 58 89 120 166 89 45 96 95 140 189 95 48 100 97 147 197 97

11228 Prove that in an acute triangle with angles A,B and C
(1-cos(A))(1-cos(B))(1-cos(C))/(cos(A)cos(B)cos(C)) >= 8(tan(A)+tan(B)+tan(C))3/(27(tan(A)+tan(B))(tan(B)+tan(C))(tan(A)+tan(C))).

Partial solution:

First note the inequality becomes an equality if A=B=C=60 degrees.
We can always check this kind of goniometric triangle inequalities with Maple or Pascal.
If we study a printed list of the right hand side rhs next the left hand side lhs for all possible angles X for which, say, 100*X is integer, we cannot be mistaken.
We could use a Pascal program with a fragment like the following:

for m:=6000 to 9000 do for l:=0 to 6000 do
begin C:=m*pi/18000; A:=k*pi/18000; B:=pi-A-C; lhs:=...; rhs:=...; writeln(lhs,rhs) end.

11232 Let f be a continuous mapping from R into R that is bounded below. Show that there exists a real number x0 such that f(x0)-f(x) < abs(x-x0) holds for all x other than x0.

Solution:

We search for x0 such that the graph of g(x):= f(x0) - abs(x-x0) lies entirely below the graph of f(x), except for the common point (x0,f(x0)).

Take an arbitrary real number s and consider V:= {y/ there is a real x with y=f(x) and f(x) <= f(s)-abs(x-s)}. V is not empty because f(s) belongs to it. V is bounded below because f is bounded below. So V has an infimum c.
The horizontal line y=c intersects the graph of f(s)-abs(x-s) in one or two points with x-coordinates a and b (a<=b). The continuous function f has an absolute minimum on [a,b], for x=t (say).

It is straightforward to prove that f(t)=c. When we draw a picture it becomes evident that x0:=t meets our requirements.

11233 Show that for each positive integer n and for x different from zero
(dn/dxn)(xn-1sin(1/x)) = ((-1)n/xn+1)sin(1/x+n*pi/2).

Solution:

We prove with induction that the formula holds both as it is stated and with cos instead of sin.

We first check both versions hold for n=1 and n=2, which is straightforward.

Next suppose they both hold for all n <= m (m>=2, induction hypothesis).

Then (dm+1/dxm+1)(xmsin(1/x)) = (dm/dxm)(d/dx)(xmsin(1/x)) = (dm/dxm)(m*xm-1sin(1/x) - xm-2cos(1/x)) =
= m(dm/dxm)(xm-1sin(1/x)) - (d/dx)(dm-1/dxm-1)(xm-2cos(1/x)) =
{by induction hypothesis}
= m((-1)m/xm+1)sin(1/x+m*pi/2) - (d/dx)((-1)m-1/xm)cos(1/x+(m-1)*pi/2) =
= m((-1)m/xm+1)sin(1/x+m*pi/2) - m((-1)m/xm+1)cos(1/x+(m-1)*pi/2) - ((-1)m-1/xm)sin(1/x+(m-1)*pi/2)(1/x2).
The first two terms in the last line cancel, the third equals ((-1)m+1/xm+2)sin(1/x+(m+1)*pi/2).

Likewise, we can show that (dm+1/dxm+1)(xmcos(1/x)) = ((-1)m+1/xm+2)cos(1/x+(m+1)*pi/2).
This completes the induction step.

11234 Let a1, b1, a2, b2, ... , an-1, bn-1, an be an increasing sequence of real numbers, and let h be an integrable function on R. Show that
INT (x from -inf to +inf) h(x) dx = INT (x from -inf to +inf) h((x-a1)(x-a2)..(x-an)/((x-b1)..(x-bn-1))) dx .

First approach:

For each natural m, we divide [-m,m] in 2m2 intervals with length 1/m. Let xk be the midpoint of the k-th interval, so xk = -m+k/m-1/(2m).
The first integral is lim (m to inf) SUM (k from 1 to 2m2) h(xk)/m = L.
So SUM (k from 1 to 2m2) h(xk) is nearly L*m for large m (that is L*(half the length of [-m,m])).

Now the idea is that u:=((x-a1)(x-a2)..(x-an))/((x-b1)..(x-bn-1)) runs at a steady pace from -inf to +inf when x runs from -inf to a1 and then from an to +inf.
Furthermore, u runs at a fairly steady pace n-1 times from -inf to +inf when x runs from a1 to an.
So it seems probable that
1) SUM (k from 1 to 2m2 and xk outside [a1,an]) h(uk) is near L*(m-(an-a1)/2) for very large m.
2) SUM (k from 1 to 2m2 and xk inside [a1,an]) h(uk) is bounded above (not very much more than L*(an-a1)/2).
Then the second integral would be lim (m to inf) SUM (k from 1 to 2m2) h(uk)/m = L

11235 (alternative version) Find all primes p such that 128p-1 is composite and a divisor of 264p-1.

Solution:

Let m=128p-1. Suppose q1a1q2a2...qsas is a prime decomposition of m. Note that qj is not 2 and not p for j=1,..,s.
Now if m is a divisor of 264p-1 then 64p is a multiple of the order d of 2 in the multiplicative group modulo m, which is a real divisor of fi(m), where fi is Euler's function.
So d is a common divisor greater than 1 of 64p and fi(m)=m*product(j from 1 to s:(1-1/qj) = q1a1-1q2a2-1...qsas-1(q1-1)(q2-1) ...(qs-1).
Since qj is not 2 and not p for j=1,..,s, we deduce that d is a common divisor greater than 1 of 64p and (q1-1)(q2-1)...(qs-1).
We find one easy solution: p=2 and m=255=3*5*17.
Otherwise, if p divides d, then 1+2tp divides m=128p-1 for t at most 6. We easily rule out all possibilities. So d divides 64 and hence m=128p-1 divides 264-1.
So we look for composite factors of 264-1=3*5*17*257*641*65537*6700417 of the form 128p-1. Since the latter four factors have the form 128n+1, there are no other solutions except p=2.

11236 Given a positive integer n and a positive real number x, consider the proposition P(x,n): "If we color each point in the Euclidean plane with one of n colors, then there exist two points of the same color that are either distance 1 or distance x apart."
a) Prove that P(sqrt(2),4), P(sqrt(3),4) and P((1+sqrt(5))/2,4) all hold.
b) Is there any other t>1 such that P(t,4) holds?
c) Is there any t>1 such that P(t,5) holds?

Provisional solution:

a) To prove P(sqrt(2),4), we search for a graph with sides of lenghts 1 or sqrt(2) whose vertices cannot each be colored with one of four given colours in such a way that adjoining vertices always have different colors.
After I discovered that the points (1/2,sqrt(3)/2) and (1+sqrt(3)/2,1/2) happen to be a distance sqrt(2) apart, I designed the appended graph, which is at the moment the simplest one of which I'm sure it fulfils our requirements.
(At the meeting, I learnt how my companions tackled the three cases; for the second, it is important to recognize that, if any two points in the plane at a fixed distance larger than 1 always have the same color, then any two points at distance 1 must also have this same color. For the third we can use the regular pentagon.)

b) I designed the annexed graph with sides of lenghts 1 (blue) and t:=2*sin(5*pi/12) (red). The only way to color each point of the graph with four colors in such a way that adjoining vertices always have different colors is as indicated in the picture. So if we imagine to color in this way all possible graphs in the plane congruent to this one, then any two points in the plane at a distance 2*t=4*sin(5*pi/12) from each other always get the same color. Then any two points at distance 1 must also have the same color. So this can't be imagined. Therefore P(2*sin(5*pi/12),4) holds. (If we set the red sides equal to 1, then the blue sides are equal to csc(pi/12)/2, but the proposer clearly prefers to set the smallest of both side lengths equal to 1.)

c) In the annexed figure, composed out of regular pentagons with side 1, whose vertices are one midpoint and the vertices of four regular 10-gons on circles around the midpoint, there are so many pairs of points at distances (sqrt(5)-1)/2, 1 or (sqrt(5)+1)/2 that the points can't each be colored with one of five colors in such a way that any two points at distance 1 or (sqrt(5)+1)/2 always have distinct colors.
So P((sqrt(5)+1)/2,5) holds.

11237 Prove that the number of 2s occurring in all partitions of n is equal to the number of singletons occurring in all partitions of n-1.

Solution:

The number of partitions of n with k 2s is the coefficient of xn in x2k(1-x2)/n(x), where n(x):=(1-x)(1-x2)(1-x3)(1-x4)...
So the total number of 2s in partitions of n is the coefficient of xn in
t(x):= (x2+2x4+3x6+4x8+...)(1-x2)/n(x).

The number of singletons k in partitions of n-1 is the coefficient of xn-1 in xk(1-xk)/n(x).
So the total number of singletons in partitions of n-1 is the coefficient of xn in
s(x):= x(x(1-x)+x2(1-x2)+x3(1-x3)+...)/n(x).

Now after evaluation the numerators and s(x) and t(x) both turn out to be equal to x2+x4+ x6+x8+....
Since the denominators are equal too, we find s(x)=t(x).

11240 Let a,b and c be the lengths of the sides of a triangle, and let R and r be the circumradius and inradius of that triangle, respectively.
Show that R/(2r) >= exp((a-b)2/(2c2)+(a-c)2/(2b2) +(b-c)2/(2a2)).

Partial solution:

First note he inequality becomes an equality if the triangle is equilateral.
We use the wellknown formulas R=abc/(4D), r=(2D)/(a+b+c), D=(1/2)(abc)2/3(sin(A)sin(B)sin(C))1/3, and finally a/sin(A)=b/sin(B)=c/sin(C)=h.
The inequality reduces to just another geometric inequality that can be checked with Maple or Pascal, using C=pi-A-B:
(sin(A)+sin(B)+sin(C))/(4sin(A)sin(B)sin(C)) >= exp((1/2)(((sin(A)-sin(B))/sin(C))2+ ((sin(A)-sin(C))/sin(B))2+((sin(B)-sin(C))/sin(A))2)).

11243 An m x n matrix of 0s and 1s is a parity pattern if every 0 is adjacent (horizontally or vertically) to an even number of 1s and every 1 is adjacent to an odd number of 1s. It is perfect if no row or column is entirely zero.
(a) Determine the number c(n) of perfect parity patterns that have exactly n columns.
(b) Prove that a perfect parity pattern with eightfold symmetry exists for all n of the form n=3.2k with k at least 1.

Partial solution:

(a) We can construct all parity patterns with n columns and without a row of 0s as follows:
First choose the elements in the first row. Then fill in the elements in the second row so as to meet the demands for the elements in the first row. Then fill in the elements in the third row so as to meet the demands for the elements in the second row, etc. Proceed until you first get a row of 0s. Since such a row has a positive probability, it is bound to appear at some moment. Delete this row, and a parity pattern remains (unless the row of 0s is the first row, then nothing remains). This way we construct 2n-1 parity patterns without a row of 0s.
Now how many of them have no column of 0s, either?
I saw that every column of 0s is a kind of mirror, with on both sides an identical but inversely orientated perfect parity pattern (two columns of 0s next each other don't occur). If we have k-1 colums of 0s (k at least 2) and the mirrored perfect parity pattern has m columns, then clearly k*m + (k-1) = n, so k*(m+1) = n+1, so m+1 is a real divisor of n+1.
So, among our 2n-1 parity patterns, the number of perfect ones is c(n):= 2n-1 - (SUM m: m+1 is a real divisor of n+1: 2n-1 - c(m)).
We find c(1)=1, c(2)=3, c(3)=6, c(4)=15, c(5)=27, etc.

11244 Let f be a differentiable function from the positive reals to the positive reals with the property that f(x) is smaller than x for all x. Suppose that x1 is larger than 0, and for n larger than 1 let xn=f(xn-1).
Suppose further that lim (n to inf) xn = 0 and that there exist positive numbers a and k such that lim (x to 0) (xa-f(x)a)/(xaf(x)a)=1/ka.
(a) Prove that lim (n to inf) n1/axn=k.
(b) Suppose that x1 is between 0 and 1, and specialize to the case where f is given by f(x)=sin(x) if x is smaller than pi/2 and f(x)=1 if x is at least pi/2. Show that lim (n to inf) xn*sqrt(n)=sqrt(3).
(c)Finally, suppose instead that x1 is between 0 and 1 and f(x)=1-exp(-x). Show that, in this case, lim (n to inf) xn*n=2.

Solution:

(a) Suppose xn ~ c/np (c,p positive), so f(xn)=xn+1~c/(n+1)p. (See the justification beneath.)
For large n we find (by substitution and evaluation): (n+1)p*a - np*a ~ (c/k)a. If p*a is larger than 1, the left hand side goes to infinity; if p*a is smaller than 1, the left hand side goes to 0. Hence p=1/a and c=k.

(b) Here lim (x to 0) (x2-sin2(x))/(x2sin2(x))=1/3, since sin(x) ~ x-x3/6. So a=2 and k=sqrt(3).

(c) Here lim (x to 0) (x-1+exp(-x))/(x*(1-exp(-x))=1/2, since 1-exp(-x) ~ x-x2/2. So a=1 and k=2.

Justification:

We can justify the assumption in the solution of (a) by comparing the rate of change of the outcome k/n1/a with the rate of change of xn derived from the data in the problem, as follows:
From the given limit with outcome 1/ka we derive 1-(xn+1/xn)a ~ (xn+1/k)a.
From the same limit, after using l'Hôpital, we derive (xn+1/xn) - (xn+1/xn)af '(xn) ~ (xn+1/k)a((xn+1/xn) + f '(xn)).
Combining these two, we get f '(xn) ~ (xn+1/xn)a+1.
Now is this compatible with xn=k/n1/a?
Substitution in (xn+1/xn)a+1 yields (n/(n+1))1+1/a.
Substitution in f '(xn) ~ (xn+2-xn+1)/(xn+1-xn) yields (n/(n+1))1/a*((1-1/(n+2))1/a-1)/((1-1/(n+1))1/a-1) ~ (n/(n+1))1/a((n+1)/(n+2)).
So both substitutions yield nearly the same.
Notice that the main features of the sequence are completely determined by the recurrence (xn+2-xn+1)/(xn+1-xn) ~ (xn+1/xn)a+1. Express xn+2/xn+1 in xn+1/xn.

11245 Consider an acute triangle with sides of lengths a,b and c, and with an inradius of r and a circumradius of R.
Show that r/R is at most sqrt(2(2a2-(b-c)2)(2b2-(c-a)2)(2c2-(a-b)2)) /((a+b)(b+c)(c+a)).

Practical solution:

Substitute a=h*sin(alpha), b=h*sin(beta), c=h*sin(gamma). The right hand side becomes
sqrt(2(2sin2(alpha)-(sin(beta)-sin(gamma))2)(2sin2(beta)-(sin(gamma)-sin(alpha))2 )(2sin2(gamma)-(sin(alpha)-sin(beta))2)) /((sin(alpha)+sin(beta))(sin(beta)+sin(gamma))(sin(gamma)+sin(alpha))).
Furthermore, r=2D/(a+b+c), R=abc/(4D), with D3=(ab*sin(gamma)/2)(bc*sin(alpha)/2)(ca*sin(beta)/2), so the right hand side becomes
r/R = 8D2/((a+b+c)abc) = 2a1/3b1/3c1/3 sin2/3(alpha)*sin2/3(beta)*sin2/3(gamma)/(a+b+c) = 2sin(alpha)*sin(beta)*sin(gamma)/(sin(alpha)+sin(beta)+sin(gamma)).
Notice that both sides are equal to 1/2 if alpha=beta=gamma=60 degrees.
Now we can study the difference between the right hand side and the left hand side for positive alpha ranging from 0 to 60 degrees, gamma from 60 to 90 degrees, beta from alpha to gamma degrees, and alpha+beta+gamma=180 degrees, using Pascal or Maple. The difference is positive unless alpha=beta=gamma.

Remark:

It is easy to derive new inequalities of this kind from geometric inequalities.
For example, combining
(sin(alpha)*sin(beta)*sin(gamma))1/3 is at most (sin(alpha)+sin(beta)+sin(gamma))/3, and
sin2(alpha)+sin2(beta)+sin2(gamma) is at most 9/4, we get
2(sin(alpha)*sin(beta)*sin(gamma))/(sin(alpha)+sin(beta)+sin(gamma)) is at most (1/6)*(sin(alpha)+sin(beta)+sin(gamma))2/ (sin2(alpha)+sin2(beta)+sin2(gamma)).
Hence we derive: r/R is at most (1/6)*(a+b+c)2/(a2+b2+c2).

11247 Let A,B,C,D be be distinct points in the plane with the property that any three of them can be covered with some strip of width 1. Show that there is a strip of width sqrt(2) covering all four points, and demonstrate that if no strip of width less than sqrt(2) covers all four, then the points are the corners of a square of side sqrt(2). (A strip of width w is the closed set of points bounded by two parallel lines separated by distance w.)

Solution:

To cover three points with a strip of minimal width, one side of the strip has to go through two of these three points, and the other side must pass through the third point. I calculated the minimum of the three strip widths. It occurs when a strip side goes through two points (out of the three) at maximal distance.
Without loss of generality, assume that among the six distances between two points from {A,B,C,D} the distance between D and A is maximal. Then B and C must be at a distance at most 1 from DA.
We want to cover the four points with a strip of minimal width. This minimal strip width is maximal if B and C are at distinct sides of DA, and at distance 1 from DA. So, w.l.o.g. we may assume D=(0,0), C=(c,1), B=(b,-1), A=(a,0) (in order of increasing x-coordinates, except possibly b=c), and that a-c is at least b. Then the strip with one side going through A and C, and the other through B, has minimal strip width among the strips that cover all four points and has width (c(a-b)+a-1)/sqrt(c2+(a-1)2). This width is maximal if b is least possible, so b=c.
Then the only possibility meeting all restrictions and assumptions is a=2 and b=c=1.