Deli problem

[franktaw at netscape.net]

I have now submitted the sequence with the table of the number of such 
sequences with limit n and k terms.

This can be calculated as follows: take the Farey sequence of order n 
(excluding 1); that is, all rationals q in [0,1) with denominator <= n. 
 Count how many have floor(q*n) = k-1; this is T(n,k).

-----
By the way, what is happening with the seqfan list?  Yesterday, I 
submitted an email at 12:39.  The first response I saw was from Emeric 
at 6:29, but I didn't see the message back from seqfan until 8:04.  The 
note I'm "replying" to here I sent out at 1:37 today; I still  haven't 
gotten it back at 5:00.

Franklin T. Adams-Watters


-----Original Message-----
From: 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.