11449 Find the maximum and minimum values of f=(a³+b³+c³)²/((a²+b²)(a²+c²)(b²+c²)) given that a,b,c are positive and a+b≥c and a+c≥b and b+c≥a.

Solution:

The domain of f is the part of the open first octant of a,b,c-space that is inside the infinite tetrahedron with faces a+b=c, a+c=b, b+c=a.
Now f is constant on each open straight half line that starts from (0,0,0) and stays in the domain.
So we only have to consider values in a+b+c=1 with a∈(0,1/2], b∈(0,1/2], a+b∈[1/2,1).
I did this with Maple and found the global minimum 9/8 for a=b=c and the global maximum 2 for a=b=c/2 or a=c=b/2 or b=c=a/2.
First I had the range [9/8,2) in mind, considering (a,b,c)=(t,t,t) and (a,b,c)=(0,t,t) etcetera. Here (0,t,t) is not in the domain.
But then, much to my surprise, I discovered the value 2 for a=b=c/2 (etcetera).
(I suppose the proposer of the problem doesn't ask for nonglobal extreme values.)

11455 Determine the triangles T of maximal area in the Cartesian plane with the property that for all nonzero integer pairs (m,n) the interiors of T and T+(m,n) are disjoint.

Partial solution:

I think I found a triangle T with a large area among the ones that meet the conditions, although I don't know whether T is optimal.
It's the equilateral triangle with vertices (0,0) and (ρ,ρ) with sides going through (1,0) and (ρ,ρ-1).
Then ρ=tan(75)/(1+tan(75)), where tan(75)=√((1/2+(1/4)*√3)/(1/2-(1/4)*√3)).
So the area of T is (1/4)*√3*2*(tan(75)/(1+tan(75)))².
This is about 0.538675..

Solution:

I first ran a simulation program:

program frog;
var t,k,m,n:integer; a:array[0..30000,0..30000] of integer;
begin
  while true do begin
  writeln('n?'); readln(n);
  for t:=0 to 30000 do for k:=0 to n do a[t,k]:=0;
  for m:=1 to 30000 do
  begin
    k:=0; a[0,0]:=a[0,0]+1;
    for t:=1 to 30000 do
    begin
      if not random≥1-k/n then k:=k-1 else k:=k+1;
      a[t,k]:=a[t,k]+1
    end
  end;
  for k:=0 to n do
  writeln('limprobodd[',k:3,'] = ', (a[29999,k]/30000):13:10, ' limprobeven[',k:3,'] = ',(a[30000,k]/30000):13:10);
  writeln; readln; writeln end
end.

I studied the output and noticed:

1) After an even number of hops, the frog is in a box with an even number, and after an odd number of hops in a box with an odd number, so
lim p_2t(k) = 0 iff k is odd and lim p_2t+1(k) = 0 iff k is even.

2) For each n the table of limits (p_2t+1(k),p_2t(k)) is symmetric, because the probability of a hop to the right at the left side is equal to the probability of a hop to the left at the right side.
For instance, for n=3 we have (0,1/4),(3/4,0),(0,3/4),(1/4,0) and for n=4 (0,1/8),(1/2,0),(0,3/4),(1/2,0),(0,1/8)

Then I found an exacter way to approximate the numerical values of the nonzero limits:

program frog2;
var k,n,t:integer; p:array[0..100,0..30000] of real;
begin
  while true do begin
  writeln('n?'); readln(n);
  for k:=0 to 100 do p[k,0]:=0;
  p[0,0]:=1;
  for t:=1 to 30000 do
    begin
      for k:=1 to n-1 do p[k,t]:=(1-(k-1)/n)*p[k-1,t-1]+((k+1)/n)*p[k+1,t-1]
    end;
  for k:=0 to n do writeln(p[k,29999]:13:10,'*',p[k,30000]:13:10);
  writeln; end
end.

Now I thought I had to sum over all possible paths to box k to find the exact values.
But, thinking it over, I found I only had to solve a system of linear equations (for k=0,1,...,n):

(For odd k let p_k:=lim p_2t+1(k) and for even k let p_k:=lim p_2t(k).)
(For convenience, let p_-1 = p_n+1 := 0.)

p_k = p_n-k,
p_k = (1-(k-1)/n)*p_k-1 + ((k+1)/n)*p_k+1
SUM(k even: p_k) = 1 = SUM(k odd: p_k)

I noticed that we can solve this system of linear equations for any fixed n.
For instance, I found for n=4 for the eventime limits (1/8,0,3/4,0,1/8) and for the oddtime limits (0,1/2,0,1/2,0), as I did earlier above.
For n=5 I found for the eventime limits (1/16,0,5/8,0,5/16,0) and for the oddtime limits (0,5/16,0,5/8,0,1/16).

Now I still had to find the solution for the general case.
Working from k=1 to greater k, I soon discovered p_k = (n over k)*p₀.
Then, using SUM(k even: p_k) = 1 = SUM(k odd: p_k), I finally found p_k = (n over k)*2^1-n.

11500 We have n balls, labeled 1 through n, and n urns, also labeled 1 through n. Ball 1 is put into a randomly chosen urn. Thereafter, as j increments from 2 to n, ball j is put into urn j if that urn is empty, otherwise, it is put into a randomly chosen empty urn. Let the random variable X be the number of balls that end up in the urn bearing their own number. Show that the expected value of X is n - H_n-1.

Solution:

First I ran the following program:

program urns;
var j,n,keuze,aantal:0..10; som,t,x:real; klaar:boolean; urn:array[1..10] of 0..10;
begin
  som:=0; t:=0; writeln; writeln('n?'); readln(n);
   while true do
    begin
      t:=t+1;
      for j:=1 to n do urn[j]:=0;
      keuze:=random(n)+1;
      urn[keuze]:=1;
      for j:=2 to n do
        if urn[j]=0 then urn[j]:=j
                    else
                        begin
                        klaar:=false;
                        repeat
                        keuze:=random(n)+1;
                            if urn[keuze]=0 then begin urn[keuze]:=j; klaar:=true end
                        until klaar=true
                        end;
      aantal:=0;
      for j:=1 to n do if urn[j]=j then aantal:=aantal+1;
      som:=som+aantal;
      x:=som/t;
      writeln(x:13:10)
    end
end.

Looking at the output, I discovered H_n must denote 1+1/2+1/3+...+1/n.

Now how do we calculate the expected value?

E(X) = SUM(j:=1 to n; P(ball j in urn j)) = ...

P(ball 1 in urn 1) = 1/n.
P(ball 2 in urn 2) = 1 - 1/n
P(ball 3 in urn 3) = 1 - P(ball 1 in urn 3) - P(ball 2 in urn 3) = 1 - 1/n - 1/(n(n-1)) = 1 - 1/(n-1)
P(ball 4 in urn 4) = 1 - P(ball 1 in urn 4) - P(ball 2 in urn 4) - P(ball 3 in urn 4) = 1 - 1/n - 1/(n(n-1)) - 1/((n-1)(n-2)) = 1 - 1/(n-2)
P(ball 5 in urn 5) = 1 - P(ball 1 in urn 5) - P(ball 2 in urn 5) - P(ball 3 in urn 5) - P(ball 4 in urn 5) = 1 - 1/n - 1/(n(n-1)) - 1/((n-1)(n-2)) - 1/((n-2)(n-3)) = 1 - 1/(n-3)
... etc.
P(ball j in urn j) = 1 - 1/(n-(j-2))
P(ball n in urn n) = 1 - 1/2

So E(X) = n-1 - (1/2 + 1/3 + .. + 1/(n-1)) = n - H_n-1.

11565 Let U1,U2,... be independent random variables, each uniformly distributed on [0,1].
a) For x in (0,1], let Nx be the least n such that SUM(k from 1 to n:√Uk) is greater than x. Find the expected value of Nx.
b) For x in (0,1], let Mx be the least n such that PRODUCT(k from 1 to n:Uk) is less than x. Find the expected value of Mx.

Solution:

a) (From the output of a Pascal program, I guess E(Nx) must be something like 1+x², but for larger x a bit more.)

E(Nx) = SUM(n from 1 to ∞: n*P(Nx=n) = P(√u1 > x) + 2*P((√u1 ≤ x) and (√u1+√u2 > x)) + 3*P((√u1+√u2 ≤ x) and (√u1+√u2+√u3 > x)) + 4*P((√u1+√u2+√u3 ≤x) and (√u1+√u2+√u3+√u4 > x)) + ...

= 1-x² + 2(x² - INT(u1 from 0 to x²: (x-√u1)²)) + 3(INT(u1 from 0 to x²: (x-√u1)²) - INT(u1 from 0 to x² and u2 from 0 to (x-√u1)²: (x-√u1-√u2)²)) + 4(INT(u1 from 0 to x² and u2 from 0 to (x-√u1)²: (x-√u1-√u2)²)) - INT(u1 from 0 to x² and u2 from 0 to (x-√u1)² and u3 from 0 to (x-√u1-√u2)²): (x-√u1-√u2-√u3)²)) + ...

= 1 + x² + INT(u1 from 0 to x²: (x-√u1)²) + INT(u1 from 0 to x² and u2 from 0 to (x-√u1)²: (x-√u1-√u2)²) + INT(u1 from 0 to x² and u2 from 0 to (x-√u1)² and u3 from 0 to (x-√u1-√u2)²): (x-√u1-√u2-√u3)²) + ...

We can calculate these integrals from the inside through the outside by substituting √uk = vk and integrating by parts, and get

1 + x² + (2/(3*4))x⁴ + ((2*2)/(3*4*5*6))x⁶ + ((2*2*2)/(3*4*5*6*7*8))x⁸ + ... = SUM( n from 0 to ∞: (x√2)²ⁿ/(2n)!) = cosh(x√2).

b) E(Mx) = SUM(n from 1 to ∞: n*P(Mx=n)) = P(u1 < x) + 2*P((u1 ≥ x) and (u1*u2 < x)) + 3*P((u1*u2 ≥ x) and (u1*u2*u3 < x)) + 4*P((u1*u2*u3 ≥ x) and (u1*u2*u3*u4 < x)) + ...

= x + 2*INT(u1 from x to 1: x/u1) + 3*INT(u1 from x to 1 and u2 from x/u1 to 1: x/(u1*u2)) + 4*INT(u1 from x to 1 and u2 from x/u1 to 1 and u3 from x/(u1*u2) to 1: x/(u1*u2*u3)) + ...

= x - 2*x*ln(x) +(3/2)*x*ln²(x) - (4/(2*3))*x*ln³(x) + (5/(2*3*4))*x*ln⁴(x) + ...

= x*SUM(n from 0 to ∞: ((n+1)/(n!))*(-ln(x))ⁿ) = ... = 1 - ln(x).

(This agrees with the output of the Pascal program for x=1/e, which seems to fluctuate around 2.)

11570 Alice and Bob play a number game. Starting with a positive number n, they take turns changing the number; Alice goes first.
Each player in turn may change the current number k to either k-1 or roundupward(k/2). The person who changes 1 to 0 wins. For which initial n does Alice have a winning strategy?

Solution:

We find the good n up to N by the following procedure:

good[1]:=true;
for n:=2 to 2*N-2 do good[n]:=false;
for n:=2 to N-1 do if not good[n] then begin good[n+1]:=true; good[2*n-1]:=true; good[2*n]:=true end;
for n:=1 to N do if good[n] then writeln(n,' is good') else writeln(n,' is not good')

11572 Given a circle C and two points A and B outside C, give an Euclidean construction to find a point P on C such that if Q and S are the second intersections with C of AP and BP respectively, then QS is perpendicular to AB. (Special configurations, including the case that A and B and the center of C are collinear, are excluded.)

Partial solution:

(Using Cabri, we can see that such a P does probably exist in most of the cases.)

Let A(a,c), B(b,c), P(cos(t),sin(t)), Q(cos(u),sin(u)), S(cos(u),-sin(u)) (, so AB is perpendicular to QS.)
We must have
1) A,P,Q collinear, which amounts to (cos(t)-a)(sin(u)-c) = (cos(u)-a)(sin(t)-c),
2) B,P,S collinear, which amounts to (cos(t)-b)(-sin(u)-c) = (cos(u)-b)(sin(t)-c).
We can eliminate u from 1) and 2) and find a polynomial p(x) of degree 6 with coefficients expressed in a,b,c such that p(sin(t))=0.
So we have to construct, with compass and straightedge only, the roots of p(x).
But p(x) looks awkward.

11573 A Sudoku Permutation Matrix (SPM) of order n² is a permutation matrix of order n² with exactly one 1 in each of the n² submatrices obtained by partitioning the original matrix into an n-by-n array of submatrices. Thus, for n=2, the permutation 1324 yields an SPM, but the identity permutation 1234 does not. Find the number of SPMs of order n².

Solution:

First we count the number of SPMs of order n² with n=2. The outcome is 16.
Next we look at SPMs of order n² with n=3. Then, generalizing, we see:

The permutation π yields an SPM iff for all k∈{1,2,..n} the sequence π((k-1)n+1), π((k-1)n+2), ..., π(kn), contains exactly one element from each of the n sets {(k-1)n+1, (k-1)n+2, ..., kn} with k∈{1,2,..n}.
Counting the number of possibilities for π(1), π(2), π(3), ... π(n²), respectively, we find in the end that the number of possible permutations (and hence the number of possible SPMs) is:
Π(i,j∈{1,2,..,n} : n²-(i+j-2)n+(i-1)(j-1))) = Π(i,j∈{1,2,..n}:(n-(i-1))(n-(j-1))) = (n!)²ⁿ. (So this outcome must be less than (n²)!.)

Earlier solutions 1: click here .
Earlier solutions 2: click here .
Earlier solutions 3: click here .
Earlier solutions 4: click here .
Earlier solutions 5: click here .

HOME