Conference rusure::math

>>    	In a certain football game a team can score only 3 or 7 points at
>>    	any time.  Is there a largest number that could not be a team score
>>    	in this game?

	Yes.

>>	If so, what is it?

	11.

	Proof one way:

	3+3+3+3=12.
	3+3+7=13.
	7+7=14.

	Integers >= 15 are a multiple of 3 more than one of {12,13,14}.

	Proof the other way (long):

	for m = 0 to oo
	   for n = 0 to oo
	      if 3n + 7m = 11 then { print Wrong! ; exit }

	Dan

>	Proof the other way (long):

>	for m = 0 to oo
>	   for n = 0 to oo
>	      if 3n + 7m = 11 then { print Wrong! ; exit }
    
    I see how this could be genralized to many numbers, example for finding
    if Z could be a score made up of scoring only 3,7,11 say we do

	for m = 0 to oo
	   for n = 0 to oo
             for k= 0 to oo 
	      if 3n + 7m + 11 k = Z then { print Wrong! ; exit }
    
    But I cant see a systematic way of finding Z (first way proof), other
    But doing
      For Z = oo to 0
	for m = 0 to oo
	   for n = 0 to oo
             for k= 0 to oo 
	      if 3n + 7m + 11 k = Z then { print "Found largest=" Z; exit}
    
    But offcourse this dont make sense sense no one know what oo is.
    /naser
    
       

    A generalization to 2 positive integers --

    If the two numbers are not relatively prime to each other than there is
    no largest "inaccesible" number -- Let the two numbers equal a*c and
    b*c.  A score will be of the form (a*c*n + b*c*m) = (a*n + b*m)*c
    for some n and m non-negative integers.  Clearly, numbers which are not
    multiples of c are inaccessible, and there is no largest non-multiple
    of c.

    So assume that the two numbers are relatively prime and call the
    smaller a and the larger b.  Let:

	    X = (a-1)*b - a = ab - (a + b)

    Then X will be the largest inaccesible number.

    Reasoning (not quite a proof):

        First let Y0 = 0*b and let c0 = Y0 rem a.  (Y0 and c0 of course
        equal 0, but that's not important).  Now any value greater than Y0
        which equals c0 mod a will be accessible simply by adding a
        suitable number of a's onto Y0.  Any value less than Y0 which
        equals c0 mod a cannot be reached.

        Now check Y1 = 1*b and c1 = Y1 rem a.  Again any value greater than
        Y1 which equals c1 mod a will be accesible, and any such value less
        than Y1 will be inaccessible.  Note that c1 ~= c0.

        Continue with Y2 = 2*b and c2 = Y2 rem a.  The same properties hold
        and it will not equal any of the smaller c's.

        When we get to Yn and cn where n=(a-1) we will have all the values
        mod a, so any value greater than n*b will be accessible. The value
        X = (Yn - a) is the next smaller value equal to cn mod a, so it is
        inaccesible.  But because a<b, X > Y(n-1) so all the values between
	X and Yn will be accessible, QED (sort of).

					    Topher

    all scores are of the form
    
            score = n*3 + m*7          m >= 0, n >= 0
    
    consider the following table
    
                                  n ->
    
           0   1   2   3   4   5   6   7   .   .   .
         --------------------------------------------------------------
     m  0| 0   3   6   9   12  15  18
     |  1| 7   10  13  16  19  22  25  28
    \ / 2| 14  17  20  23  26  29  32
        3| 21  24  27  30  33  36  39
        4| 28  31  34  37  40  43  46                score
        5| 35
        6|
        .|
        .|
        .|
    
    notice that if you proceed from the upper left to the lower right of
    the table along the diagonals the values of score increase by 10
    
    thus starting with the value 0 at position (0,0) - (m,n) -  and
    proceeding along the diagonal we cover all values 0,10,20,30,...
    
    likewise if we start at position (0,4) with the value 12 and proceed
    diagonally we cover the values 12,22,32,42,...
          
    by inspection one can see that all integers after the integer 11 appear
    in the table.
    

    I was unable to find a closed algebraic description for the case where
    there is more than two possible scores -- and I suspect that there
    isn't one.  The following pseudocode program will find the value.

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

    PROCEDURE max_inaccessible(N: Integer>1,
			       X: Vector[1..N] of Integer>0)
	<<Find common-factor being the greatest common factor of the N
	    X values>>

	if common-factor > 1 then signal("No maximum inaccessible");

	<<Find the smallest element of X and swap it to X[N]>>

	base := X[N];
	NN := N - 1;

	! Optional performance improving step:
	    <<Eliminate all elements of X which are multiples of smaller
		elements, or which are equivalent modulo base to smaller
		elements -- adjust X and NN as necessary so that the
		"active" elements are the first NN elements of X.>>

	covered := new Vector[0..base-1] of Boolean initially FALSE;
	covered[0] := TRUE;
	count := base-1;
	Q := new Priority-Queue;
	for i := 1..NN do add(Q, X[i]);

	WHILE count>0 DO
	    candidate := pop_smallest(Q);

	    if ~covered[candidate MOD base]		! Acceptance test.
	    then
		covered[candidate MOD base] = TRUE;
		count := count - 1;
		for i := 1..NN do add(Q, candidate+X[i]);    ! Inner-loop

	return (candidate - base);

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

    The acceptance test will be passed (base-1) times, and each time the
    inner-loop's body will be called NN times (basically, N-1 times where
    the optional step is not applied or has no effect), so 'add' will be
    called (base-1)*(N-1) times.  A single add operation to a priority
    queue can be done in time O(logM) where M is the number of elements in
    the queue when the add is done.  Obviously, the worst case is less than
    all adds being done with all the (base-1)*(N-1)+(base-1) = (base-1)*N
    elements already in the queue, so the worst case cost will be less than
    or equal to O(base*N*log(base*N)).

				Topher

	
	I realize it's a mute point because you are really more interested 
	in the problem than in football, but another way to score is the
	safety, for two points.  If this is allowed, then all scores greater
	than 1 are possible.

	Avery