Conference rusure::math

> Question 4
> ----------
> A city has a system of bus routes laid out such that
>
>   (i) there are exactly 11 bus stops on each route;
>  (ii) it is possible to travel between any two bus stops without changing
>								routes; and
> (iii) any two bus routes have exactly one bus stop in common.
>
> What is the number of bus routes in the city?

    Doesn't "1 route" [also] satisfy all the above?

re .1
    
>                              -< Is Q4 correct? >-
    
    I didn't make any typos in it.

>    Doesn't "1 route" [also] satisfy all the above?
    
    My guess is that there is a solution with the number of routes greater
    than one. It is specified that there is a "system of bus routes" which
    to me implies that "1 route" is not an acceptable answer.

  > A function f satisfies the following conditions:
  >   (i) For each rational number x, f(x) is a real number;
  >  (ii) f(1988) <> f(1987); and
  > (iii) f(x+y) = f(x)f(y) - f(xy) + 1 holds for all rational numbers x and y.
  > Show that f(-1987/1988) = 1/1988

Let a = f(1)-1; then:
  f(1) = a+1
  f(2) = f(1+1) = f�(1)-f(1)+1 = f(1)(f(1)-1)+1 = (a+1)a+1 = a�+a+1
  f(3) = f(2+1) = f(2)f(1)-f(2)+1 = f(2)(f(1)-1)+1 = (a�+a+1)a+1 = a�+a�+a+1
and similarly (proved by induction), for each positive integer n:
  f(n) = a**n + a**(n-1) + ... + a + 1
But, for f(4) we also get:
  f(4) = f(2+2) = f�(2)-f(4)+1 ==> f(4) = �(f�(2)+1) = �((a�+a+1)�+1) ==>
  a**4 +a�+a�+a+1 = �((a�+a+1)�+1) ==> ... ==> a**4 -a� = 0 ==> a�(a�-1) = 0
Thus, "a" must be one of {-1,0,1}

If a = -1 then f(1) = 0 and f(2) = 1 and for *any* rational number x:
  f(x+1) = f(x)f(1)-f(x)+1 = -f(x)+1
  similarly: f(x+2) = ... = -f(x+1)+1 = f(x)
  but also: f(x+2) = f(x)f(2)-f(2x)+1 = f(x)-f(2x)+1 = f(x+2)-f(2x)+1
which means f(2x) = 1 (for *any* rational x), which contradicts (ii).

If a = 0 then f(1) = 1 and for *any* rational number x:
  f(x+1) = f(x)f(1)-f(x)+1 = f(x)-f(x)+1 = 1
which again contradicts (ii).

So, we are left with a = 1 and for each positive integer n: f(n) = n+1, and for
*any* rational number x: f(x+1) = f(x)f(1)-f(x)+1 = 2f(x)-f(x)+1 = f(x)+1.
By simple induction we get: f(x+n) = f(x)+n, but then:
  f(1/n)+n = f(1/n+n) = f(1/n)f(n)-f(1)+1 = f(1/n)(n+1)-2+1 = f(1/n)(n+1)-1 ==>
  f(1/n) = 1/n+1

And finally:
  f(-1987/1988) = f(1/1988-1) = f(1/1988)-1 = 1/1988+1-1 = 1/1988

Q4 The Bus Routes

	Pick one stop, s1.   Look at the the k routes which pass through s1.
Each visits 10 other stops.   None of the k routes visit the same stop (apart
from s1 itself).   Each stop appears in one of the k routes.   So the stops
apart from s1 are partitioned into k sets of 10 members each.   So there are
10k+1 stops in total.   So k is independent of the choice of s1.

	Let S be the number of stops, R the number of routes.   We have:
		S= 10k+1
	Also since each pair of stops have a route linking them:
		55R = �S(S-1)
	And each pair of routes share exactly one stop, with k routes at each
stop:
		�R(R-1) = �k(k-1)S

	These simplify to R = 1 or 111.   Since we know there's more than 1
route, 111 is the answer.   k = 11, and S = 111.   Hence we're looking at a
finite projective plane on 111 points/edges.   Is this the one whose existence
was proved a couple of years back, using a massive amount of Cray power?

c.f.: 973,1063

Andrew

re .3
    
    Nice work!
    
    One minor nit.
    
>  f(2) = f(1+1) = f�(1)-f(1)+1 = f(1)(f(1)-1)+1 = (a+1)a+1 = a�+a+1
    
    f�(x) is often used to mean f(f(x))
    
    Here you mean (f(x))� which confused me a bit. Your usage is consistent
    with the trig functions though. Someone better enter a QAR against
    mathematics. (-:

>Question 3

	The number of times you can divide n! by a prime p is given by:
		sum(j=1...infy) floor(n/p^j)
Given this, the result drops out.

>Question 5

	Here's an algorithm:

	When a single judge arrives, the Court Servant places him in the lowest
numbered chair which is vacant, using the following numbering from the left:
	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 16 18 19 20 21 22 23
	(Note the order of 17 & 16.)
	When a pair of judges arrive, the Court Servant places them as far to
the right as possible.
	How does this work out when we never have more than 16 judges present
simultaneously?   Could the Court Servant have a problem?   He can never have
a problem placing a single judge.   Imagine that he has a problem placing a
pair of judges.   What chairs are occupied?   With 16 judges, the rightmost 6 
chairs could never have been occupied by a single judge.   So 3 pairs of 
judges occupy chairs 18-23.   We have 16-2-6 = 8 judges to block chairs 1-17.
The only way that these 8 judges can prevent a two adjacent seats out of the
17 from being available is by occupying seats 2 4 6 8 10 13 14 & 17.   But 
a single judge could never have occupied seat 17.   And if a paired judge
occupied 17, 16 would still be occupied as well.   So 16 judges can always be
accommodated.

>Question 6

	S[i] + T[i] = K, say
	sum(i) S[i] = pK

	m(a,b) = 0 unless a + b == K mod 4.   So the result is obviously true
unless K == 0 mod 4.   Assume that K == 0 mod 4 now.
	sum(a=0..3) a*m(a,4-a) == pK mod 4
=>	m(1,3) - m(3,1) == 2*m(2,2) mod 4.

> Question 1

	The proof given in .3 is neat.   So in fact f(x)=x+1.

Andrew.

Indeed the next step is to prove that f(m/n) = m/n+1. It's really easy
now (2 more lines). However, "f" was only defined for *rational* numbers.

Suppose (iii) hold for any *real* number. Given that "f" is continuous,
it's also easy now [I think] to show that f(x) = x+1. Can we show that
even without knowing in advance the continuity of "f"? Is it true at all?

/Nitsan

>Suppose (iii) hold for any *real* number. Given that "f" is continuous,
>it's also easy now [I think] to show that f(x) = x+1. 

	Yes.

>Can we show that even without knowing in advance the continuity of "f"? 
>Is it true at all?

	I don't know, but if we restrict ourselves to a subset of the reals,
then there can be other solutions to the equation than the one we found.
Explicitly, if G:Q is a Galois extension of the rationals Q, and � is a member
of the corresponding Galois group, then f(x) = �(x)+1 satisfies the 
constraints.   This is grandiose language for what is actually a very obvious
idea.

	For example, if we define for all elements of the form a_/2 + b, where
a & b are rationals, and _/2 denotes sqrt(2), then f(a_/2+b) = -a_/2 + b + 1
is a perfectly consistent model.

	A similar idea says that if Q(t):Q is a simple transcendental
extension, and u is another transcendental number, then we can define a
field automorphism fixing Q from Q(t) -> Q(u), that maps t -> u.   Call it �.
Then f(x) = �(x)+1 will do the job.

	Why should these things be so?

	Let g(x) = f(x)-1.   Then the key constraint rewrites to:
	g(x+y)-g(x)-g(y) = g(x)g(y) - g(xy).   So if g is a field automorphism,
then both sides of this equation will vanish, and hence be the same.   However,
other animals apart from a field AM can satisfy this equation.   For instance,
g(x)=0.

	Does R:Q have any non-trivial field AMs?   I ought to be able to answer
this right off the bat, but I'm a little confused.

	Like question 4, question 1 seems to hover on the brink of some quite
advanced mathematics.

> Does R:Q have any non-trivial field AMs?   

	The answer's no:

There are no non-trivial automorphisms on the reals, R, that fix the rationals,
Q.

Proof:

	Suppose � is an AM on R fixing Q.

	If � is not order-preserving, then there exist x,y in R such that:

		x > y
		�(x) < �(y)

=>		x-y > 0
		�(x-y) < 0

	Since x-y > 0, there exists z in R such that z^2 = x-y.   Therefore:

		�(z)^2 < 0

which is not possible in R.   Contradiction

	By reductio ad absurdum, � is order-preserving.

	If � is not trivial, then there exists w in R such that

	w <> �(w).   Wlog, w < �(w).

	Let a in Q lie in the interval (w,�(w)).

	Then w < a = �(a) < �(w).   But this contradicts the fact that � is
order-preserving.   So by reductio ad absurdum again, � is trivial.

--------------------------------------------------------------------------------

	What does this mean?   Well, I think it means that *probably* the
only f over the reals which satisfies all the original constraints is

		f(x) = x+1.

Andrew.

> g(x+y) - g(x) - g(y) = g(x)g(y) - g(xy)

Try with y+1 instead of y:

  	g(x+y+1) - g(x) - g(y+1) = g(x)g(y+1) - g(xy+x)
=>	g(x+y) - g(x) - g(y) = g(x) + g(x)g(y) - g(xy+x)

Subtracting:

	g(x) = g(xy+x) - g(xy)

Relabelling, and checking for divide-by-zero problems:

		g(x+y) = g(x) + g(y)

		g(xy) = g(x)g(y)

I should now point out that ker(g) is an ideal, and a field has no non-trivial
ideals.   So g is either an automorphism, or the zero map.   We saw in a
previous reply that there is only 1 automorphism on the reals fixing Q, and
that is the identity.

	Therefore f(x) = x+1 is the *only* function on R which satisfies the 
constraints of the problem.

--------------------------------------------------------------------------------

	If A is the field which is the intersection of the algebraic numbers
with the reals, then the previous paragraph is true with A replacing R.

	On the other hand, we know that if K is a finite extension of Q, then
there are other functions on K which satisfy the constraints of the problem.

	Are there any "maximal" fields offering multiple solutions?   Or
minimal fields offering the unique solution, f(x)=x+1?

Andrew.

re .6
    
>>Question 3

>Given this, the result drops out.
    
    Indeed. As a consequence, 2 divides n! exactly n-r times where r is the
    number of 1 bits in the binary representation for n. I can't see that
    this is a staggeringly useful result but it could be used for some
    impressive mental feats.

>>Question 5

>The only way that these 8 judges can prevent a two adjacent seats out of the
>17 from being available is by occupying seats 2 4 6 8 10 13 14 & 17.   But 
    
    Typo?                                                 ^^ 12
    
    Is it necesssarily the case that because 16 judges can always be seated,
    15 judges can always be seated or more generally is there some number j
    in 0..23 such that j or fewer judges can always be seated and attempts
    to seat more than j judges can always be defeated? If so, what is j for
    23 seats? and what is j(n) where n is the number of seats?

>>17 from being available is by occupying seats 2 4 6 8 10 13 14 & 17.   But 
>    
>    Typo?                                                 ^^ 12

	Yes.

>    Is it necesssarily the case that because 16 judges can always be seated,
>    15 judges can always be seated. 

	Sure.	

	17 judges can't be accommodated.   If you have 6l-1 seats, then you
can accommodate 4l judges, but not 4l+1.

--------------------------------------------------------------------------------

	Sketch of proof, if you are interested:   Suppose they all arrive singly
and are accommodated.   Then 8 of them go away, and return as 4 pairs.   However
we arranged the original 17, there's a way to pick the 8 who will leave, such
that the 4 pairs cannot all be accommodated.

	To see this, look at each possible way of arranging 17 judges in 23
seats.   We are asked to remove 8 judges and prevent the appearance of 4 pairs.
Call this problem P(17,23,8,4).   We can simplify by splicing out any 
subsequence of even length, where each seat is empty.   For instance, if 2
adjacent empty seats are spliced out, we are facing the problem P(17,21,8,6).
We can also splice out any subsequence of even length, where each seat is full.
For instance, if we continue from P(17,21,8,6) by splicing out 4 adjacent full
seats, we are left with P(13,17,6,6).

	THE KEY IDEA: give the Servant the free gift that the 23 seats are
arranged in a *cycle*.   This can only make it easier for him, but it makes the
*proof* that he can't manage 17 easier for us.   Because, after removing all
the subsequences of even length, we can *only* terminate at P(1,1,0,1).   
However 1 judge is arranged in 1 seat, we can remove 0 judges and prevent the 
appearance of 1 pair!   So P(1,1,0,1) can be solved, and hence P(17,23,8,4) 
can be solved.

	Generalizing, P(2k+1,2k+2l-1,k,l) can be solved.   If k=2l, then
P(4l+1,6l-1,2l,l) can be solved.   That's saying that if you've got 6l-1 seats,
then you can't accommodate 4l+1 judges.   But you *can* accommodate 4l judges,
by the standard trick.

Andrew