wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> selecting the increment set
        
(Message started by: inexorable on Oct 10^th, 2006, 4:03am)

Title: selecting the increment set
Post by inexorable on Oct 10^th, 2006, 4:03am

Say you have an integer key number 14, and a set of increments (3, 5),
where each increment is an integer greater than 1 and less than or equal
to half the key number. You want to sum the increments up from 0 in order
(3+5+3+5+3+5 etc), modulo the key number, so that you get all available
values, with no repeats until you get back to 0. So for the above example:

0, 3, 8, 11, 16%14= 2, 5, 10, 13, 18%14= 4, 7, 12, 15%14= 1, 6, 9, 0

That sequence comes full circle back to 0, covering every number from 0 to 13
with no repeats.

So the question is, once you've selected a key number, how can you select
values for the increment set (as well as the number of members to include
in the set) without just brute-forcing every possibility?

Title: Re: selecting the increment set
Post by towr on Oct 10^th, 2006, 4:35am

Pick any singleton set with a number that is coprime to and smaller than the key-number.
I think that should work.

If you want a larger set, I'd hazard to guess they have to be coprime, and also coprime to any (consecutive) sum,w hich also has to be coprime to the key number.
Hence why I'd stick with as singleton set.

I suppose, you could take a subset of the factorization of key+1, as you've seem to have done for 14. (It's straightforward that they have to be coprime to the key. The other property have to be additionally enforced though.)

Title: Re: selecting the increment set
Post by jollytall on Oct 10^th, 2006, 4:51am

Some quick thoughts:

How many elements shall be in the set? Can they be equal? Is the first element of the sequence 0?

For n<5 there is no solution.
For n=5, the only available set is {2} and that works. This also tells me, that there can be only one element in the set, or the set elements can be equal {2, 2}
For n=6, both 2 and 3 are dividers of 6, so the set has to have 2 different elements. Set {2, 3} does not work if the first element 0 (because the sequence 0,2,5,1,4,0 gets back 0 i.e. there is a repeat). If the first element is not necessarily 0, then it works (2,5,7=1,10=4,12=0,15=3). Otherwise the set must be {3,2}.

For n>6 there is always a relative prime, that can be the single element of the set. Based on n=5 restrictions it is always a solution.

If we want to find all the solutions, it is much more complex, not only because we have to find the elements of the set, but also because the n=6 example shows that the same elements might or might not give a solution depending on their sequence (if the sequence starts with 0).

Title: Re: selecting the increment set
Post by towr on Oct 10^th, 2006, 5:30am

on 10/10/06 at 04:51:07, jollytall wrote:

For n=6, both 2 and 3 are dividers of 6, so the set has to have 2 different elements. Set {2, 3} does not work if the first element 0 (because the sequence 0,2,5,1,4,0 gets back 0 i.e. there is a repeat). If the first element is not necessarily 0, then it works (2,5,7=1,10=4,12=0,15=3). Otherwise the set must be {3,2}.

{3,2} has a problem too, you repeat the 3 before returning to 0
0,3,5,2,4,1,3,0

Guess it's more complicated than I thought, at least for non-singleton sets.

Title: Re: selecting the increment set
Post by jollytall on Oct 10^th, 2006, 7:01am

You are right. I focused on having n different numbers in the first n position of the sequence, while the original question asked to get back to 0 in the n+1 position.

Even without trying, from the fact that {2, 3} is not a solution for n different numbers in the first n positions, it can be proven that {3, 2} cannot be a solution for the n+1 long 0.. ..0 sequence.
Proof: If the n+1 element (0) would be the same as the first element (also 0), then we had exactly n increments in between. Since n(=6) is even, both 2 and 3 are used the same number of times, i.e. the sequence starting from the n+1 position would be the same as from the first position. With other words it would mean a sequence of repeated patterns of n length, where all the n elements are different. But if it would be so, then {2, 3} would not repeat any number in any n long pattern either, and would be a solution too.

In more general, the statement would sound: If a certain set has e elements and e is a divider of n and {e} set is a solution to the original problem then every rotated version of the set is also a solution. (Rotated means that we put the first number of the sequence to the last position as many times as we wish).
I am not sure for other permutations (mixing up the sequence of the numbers in the set), neither what happens when e is not a divider of n.

I am also concerned on your coprime set logic. If n=7, then the only set with e>1 is {2, 3}, where both 2 and 3 and their sum (5) are coprimes to each other and n(=7), still it is not a solution.

Title: Re: selecting the increment set
Post by towr on Oct 10^th, 2006, 1:45pm

on 10/10/06 at 07:01:49, jollytall wrote:

I am also concerned on your coprime set logic. If n=7, then the only set with e>1 is {2, 3}, where both 2 and 3 and their sum (5) are coprimes to each other and n(=7), still it is not a solution.

Yeah, basicly the last part of it is just plain wrong.
For n=7 {2} works and {3} works, but not {2,3}
And of course, in the original example we have for n=14 {3,5}; 3+5=8 which isn't coprime to 14. So the idea that it ought to be is rather bust from the outset.

Title: Re: selecting the increment set
Post by Barukh on Oct 10^th, 2006, 10:44pm

Case by case study?..

[hideb]If the key number K is even, then the set {n, m} works, if:

1. n is odd.
2. n+m = K-2.

[/hideb]

Does this make sense?

Title: Re: selecting the increment set
Post by towr on Oct 11^th, 2006, 1:02am

on 10/10/06 at 22:44:54, Barukh wrote:

Does this make sense?

Take K = 4x, then at the maximum n and m can be 2x-1 and 2x-3, and so can't sum to K-2
So in that case your conditions can't be satisfied, unless n and m are the same. In which case you have a problem if K and n aren't coprime.

For K = 4x+2 you'd have 2x+1 and 2x-1, and that seems fine..

Title: Re: selecting the increment set
Post by jollytall on Oct 11^th, 2006, 1:24am

For K=4x+2, using n=2x-1 and m=2x+1 works for all x.

The elements are:
0, 2x-1, 4x, 6x-1=2x-3, 4x-2, ...

Even position elements are always even, odd position elements aer always odd. So only two odd, or two even position elements can be the same. Even position elements are in the form of 2x-1-2i. They can only be equal modulo K, if 2i = 0 (mod K), i.e. the peridicity is exactly K. Similarly it is tru for the even elements.

Title: Re: selecting the increment set
Post by SMQ on Oct 11^th, 2006, 7:19am

Looking at exhaustive solutions for S = {n, m} (n and m distinct) and K < 100, I'm seeing:
- odd K has no solutions in {n, m}
- both n and m are always odd
- it appears to me that {n, m} generates all integers < K if and only if (n + m)/2 is coprime to K/2 (i.e. there are no other further restrictions on {n, m}

[edit] (removed silly hide tags)

Expanding the above, the following appear to be necessary (but not sufficient) conditions, for a set S = {a₁, a₂, ..., a_n} to generate all integers < k:
- n must be a factor of k (otherwise the series can't have period k).
- sum(a₁, a₂, ..., a_n) is a multiple of n (so that r*sum(a₁, a₂, ..., a_n) is a multiple of k where r*n = k).
- GCF(k, a₁, a₂, ..., a_n) = 1
- sum(a₁, a₂, ..., a_n)/n is coprime to k/n

These conditions appear to also be sufficient for n = 2 (verified for 4 < k < 720).
[/edit]

--SMQ

Title: Re: selecting the increment set
Post by jollytall on Oct 11^th, 2006, 12:48pm

I had two similar results with proofs.

I also thought of your first thought re multi element sets, i.e. that the number of elements must be a factor of K. It is true that otherwise the period cannot be K, but based on the original question it could still work otherwise. Imagine e.g. 2 elements for an odd K. It is clear that when the K+1 element is 0 again, it cannot continue like it started (since #2 = n, while #K+2 = m). But it does not mean, that 0 cannot be repeated with a period of K, having K-1 different elements in between (but in different order).
The proof for this in case of two element sets is:
In this case the period is maximum 2K.
In the first K long segments if the first increment is n, then the last is also n. So the second 0 follows an n increment. The third 0 is following an m increment. I.e. regardless the last increment before a certain 0, K elements later it will again be 0. It must also be true then for any other number, i.e. the period shall be K, not 2K. But the 2nd element is N, while the K+2 is m, i.e. contradiction.
I guess it can be done for higher numbers too.

For the 2 element sets, I also got that if K even (based on the above a 2 element set can never be a solution for an odd K, or the other way said, for odd K-s there is no solution with 2 elements) then (n+m)/2 must be coprime to K/2.
The proof is that if you take the even position elements of the series, the difference between two of them is always in the form of i*(n+m). If this is 0 (mod K), then the same value is repeated, i.e. i*(n+m) = j*K. If (n+m) and K has any common divider (other than 2) then there is an i less than K/2 giving a solution, but it means that there are two identical elements of the sequence closer than 2i (<K), i.e. the first K elements are not all different.
When (n+m) and K have 2 as the only common divider, then i=K/2 is the first solution, what exactly means that the period is K, i.e. that is allowed.

Title: Re: selecting the increment set
Post by Barukh on Oct 18^th, 2006, 5:48am

on 10/11/06 at 01:02:11, towr wrote:

Oops… I missed the restriction of set elements be no greater than the half of the key…

Ok, here’s a sufficient condition for the set of n elements to exist for arbitrary n, K.

First, define s_i = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_j<=i a_j.

Now, the condition:

1) Taken modulo n, the numbers s₁, …, s_n are all different, and
2) gcd(s_n, K) = n.^*

For which combinations n, K the 1) above can be satisfied? It is easy to see that if a_i = 1 modulo n for every i = 1, …, n, then it is satisfied. That means the solution always exists for K >= 2n(n-1) + 2. But that’s probably not the only case.

I believe that there is much similarity between this result and that of SMQ and jollytal.

^*I think SMQ uses GCF instead of my gcd.

Title: Re: selecting the increment set
Post by SMQ on Oct 18^th, 2006, 6:53am

on 10/18/06 at 05:48:45, Barukh wrote:

I think SMQ uses GCF instead of my gcd.

"Greatest Common Factor" vs. "Greatest Common Divisor" Based on a quick survey of Mathworld, PlanetMath and Wikipedia, GCD seems to be more widely accepted -- I'll attempt to remember to use it in the future. ;)

--SMQ

Title: Re: selecting the increment set
Post by inexorable on Oct 20^th, 2006, 4:14am

Thanks to all for their insights.

What happens if you remove the requirement of summing the increments in order(i.e there can be any number of increments of each element in set and in any order)? Presumably this would increase the number of increment sets that would work with a given key number, but how would you choose which increment to add at which time?

Title: Re: selecting the increment set
Post by towr on Oct 20^th, 2006, 9:46am

Actually, it just means that instead of a tuple (for instance) (2,2,2,3,2,3) you'd be done with a set {2,3}
So using proper sets which you can pick from at will, you'd have less solutions (or at least, not more) because a lot of order-dependant tuples would fall together.