Deli problem

[franktaw at netscape.net]

Nice problem.

These sequences are well-known, although I've never seen anybody raise 
this particular question before.  They're called Beatty sequences; see, 
for example, http://mathworld.wolfram.com/BeattySequence.html.  For 
some reason, that article doesn't mention the basic constructive 
property for Beatty sequences:

After taking a(1) arbitrary (and as Joshua notes, we want it greater 
than zero for this problem), for each subsequent a(n), look at all sums 
a(k) + a(n-k), for 0 < k < n.  These will either have all the same 
value, or two consecutive values.  In the latter case, a(n) must be the 
larger of the two; in the former case, it can be the given value or 1 
larger.  Taking David's first example below, for a(4), we have sums 
3+11 = 7+7 = 14, so a(4) can be 14 or 15.  In the event, it's 15.  For 
a(9), we have 3+30 = 33, 7+27 = 11+23 = 15+19 = 34, so we must have 
a(9) = 34.

All this is closely related to Farey fractions.  At the first step, 
a(1) = 3, we know that our x is between 3/1 and 4/1.  The next division 
is at (3+4)/(1+1) = 7/2, which is determined by whether a(2) is 7; 
since it is, x is between 7/2 and 4/1.  Continuing in this way, a(7) 
=27, but a(8) < 31, so x is between 27/7 and 31/8.  The next key point 
is then a(15), which determines/shows whether x >= 58/15.

For counting sequences, the process stops when the numerator is greater 
than or equal to N (which David is taking to be 100).

So how many choices, total do we have at step N?  One for each rational 
N/k, where gcd(k,N) = 1.  In other words, phi(N).  So the total number 
of sequences at step N is A002088(N): 1,2,4,6,10,12,18,....  For N=7, 
the 18 sequences are:

0,1,2,3,4,5,6; 0,1,2,3,4,5; 0,1,2,3,4,6; 0,1,2,3,5,6; 0,1,2,4,5,6; 
0,1,2,4,5; 0,1,3,4,6; 0,1,3,5,6; 0,1,3,5; 0,2,4,6; 0,2,4; 0,2,5; 0,3,6; 
0,3; 0,4; 0,5; 0,6; 0.

The table of the distribution by length of sequence starts:

1; 1,1; 1,2,1; 1,2,2,1; 1,3,2,3,1; 1,3,2,2,3,1; 1,4,3,2,3,4,1; ...

This is not in the OEIS.

I am submitting a comment on A002088 about this problem.  I'm going to 
hold off on submitting the table to see if somebody (possibly me) can 
compute more terms.  I don't think it's particularly hard to compute.

Franklin T. Adams-Watters


-----Original Message-----
From: davidwwilson at comcast.net

I work at a deli now, but I'm always thinking math, so here goes.
 
The scales at my deli rounds down weights to the nearest one hundredth 
of a pound (yeah, it's an odd mix of U.S. and metric, but I guess it's 
standard for U.S. delis). So 0.778 pounds of meat or cheese would weigh 
out as 77 hundredths of a pound.
 
Suppose I am slicing a block of cheese that happens to yield perfectly 
uniform slices weighing precisely 0.03871 pounds each. I start with an 
empty scale, and add slices one at a time, staying less than a pound. 
The successive readings on the scale are:
 
0 3 7 11 15 19 23 27 30 34 38 42 46 50 54 58 61 65 69 73 77 81 85 89 92 
96

The next reading would be 100, which is a pound or over, so I stop 
there. Similarly, if the slices weighed 0.04137 pounds each, I would 
get the readings
 
0 4 8 12 16 20 24 28 33 37 41 45 49 53 57 62 66 70 74 78 82 86 91 95 99

of if the slices were a very heavy 0.29337 pounds, I would get the 
readings
 
0 29 58 88
 
My questions are:
 
Given slices of perfectly uniform positive weight, how many different 
reading sequences are possible? How are they distributed by number of 
readings?




 
 
 
 
 


________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.