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.

>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

> 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