Conference rusure::math

1253.0. "Two obscure repr's of integers" by CIVAGE::LYNN (Lynn Yarbrough WNP DTN 383-5663) Thu Jun 14 1990 17:40

There are a number of obscure representations of integers that may be 
useful in special contexts. We are familiar with decimal, octal, binary,
etc. (positive) radices; there are also negative radices (e.g. radix -2)
and a variety of others. For combinatorial work, a *factorial* 
representation turns out to be useful; i.e. express n as the sum [from j=1]
of d[j]*j! where d[j] <= j. For an example of how this is useful,
Beckenbach (in *Applied Combinatorial Mathematics*) shows how the factorial
representation can be used to calculate quickly what the 1,000,000th
permutation (in lexicographical order) of 10 digits is. 

MAPLE turns out to be a nice language for describing the algorithm for 
deriving the d[j] from n, especially since it permits a procedure to return 
a table or list as its value. Here it is:

#	fact_rep.maple
# Given an integer n, this procedure computes its factorial representation:
#	n = d[1]*1! + d[2]*2! + ... + d[k]*k!
# The function returns a table, internally known as d, as value.
# ============================================================
fact_rep := proc(nn) local d, n, r;
	n := nn;
	for r from 1 while n > 0 do
	    d[r] := n mod (r+1);
	    n := (n - d[r])/(r+1);
	od;
# At the end of loop, r is too large by 1; d[r] does not yet exist, 
# so return the rest.
	d[i]$i=1..r-1
end;

Another representation is called the *combinatorial representation of nome 
k* of n; 
	         (d[i])
	n = sum  (    ), i.e. the sum of binomial coefficients.
	  i=1..k ( i  )

This one's a bit more obscure, but - who knows? - you may find a use for it 
some day. It's messier to calculate, since you need to find the largest 
binomial coefficient less than each partial remainder, and maybe there's a 
cleaner way to do it. Anyhow, here it is:

#	comb_rep.maple
# Given integers n and k, this routine computes the combinatorial
# representation of n to the nome k, i.e.
#	n = C(d[1],1) + C(d[2],2) + ... + C(d[k],k)
# where C(a,b) is the binomial coefficient.
# Reference: Beckenback, Applied Combinatorial Mathematics, P. 8.
# The function returns a table of length k, internally known as d, as its 
# value.
# ========================================================================
comb_rep := proc(nn, kk) local d, k, n, p, q, r;
	n := nn;
	for k from kk by -1 to 1 do
# find the largest appropriate bin. cooef. < n:
	    p := 1;
	    for r while p <= n do
		q := p;
		p := p*(r+k)/r;
	    od;
	    d[k] := r + k - 2;
# reduce n (and k) and go 'round again...
	    n := n - q;
	od;
	d[i]$i=1..kk
end;

	Lynn's topic reminds me of a game.   We have the usual 2 players
sitting in front of n sticks.   Each player takes it in turn to remove
a certain number of sticks, but no more than twice the number that the
other player removed in his immediately prior turn.   The player who picks
the last stick wins.   For the very first turn of the game, the first player
is free to take any number of sticks he likes, as long as he doesn't take
the whole lot.

	So:

	(1) suppose we start with 1000 sticks.   Who wins, and how does he
do it?

	(2) what's the general strategy?

	(3) how does this tie in with the base note?

Regards,
Andrew.

	Let f_i denote the ith fibonacci (number).   Let f_1 = 1, f_2 = 2,
f_3 = 3, f_4 = 5, ... 

	Say that two distinct fibonacci numbers, f_i & f_j, are adjacent if 
|i-j| = 1.

	Define a Fibset, F, as a finite set of distinct fibonacci numbers
such that no two are adjacent.   Define S(F) to be the sum of elements of
a Fibset, F.

	Lemma: S is a bijection between the set of Fibsets and the natural 
numbers.

	Define F(n) to be the inverse function to S.   F uniquely decomposes
n into a Fibset.

	Now, to return to the game.   We will characterize a position in
the game as (x,y), where x is the number of sticks remaining, and y the
maximum number of sticks the next player, P, is entitled to remove.   For
example, the start position is (n,n-1).   Any position is either a loss or
a win for P.   We say that V(x,y) = 0 or 1 accordingly.

	We will rephrase the rules of the game to make them slightly more
general.   The loser of the game is the first person who cannot legally
play a move.   So the person to remove the last stick is the winner.

	Take x > 0.   The foregoing enables us to say that V(x,0) = 0 (so in 
particular the game with 1 stick is a loss for the first player.)   On the 
other hand V(x,x) = 1.   Regarded as a function of y, V(x,y) is monotonic.   
Let t(x) = min(y| V(x,y) = 1).

	Theorem: t(x) = f(x), where
		f(x) = min(f_i | f_i in F(x)).

	Corollary: the losing initial positions are exactly the fibonaccis.

	Example: n = 1000.   The initial position is: F(1000) = {13,987}.   
t(x) = 13.   So a winning strategy is to take 13 sticks.

	Question: (Easy given the above) what are *all* the winning strategies 
for the position (x,y)?

Regards,
Andrew.