Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Lunch Bunch arrangement problem

by tall_man (Parson)
on May 16, 2003 at 16:06 UTC ( [id://258696]=perlquestion: print w/replies, xml ) Need Help??

tall_man has asked for the wisdom of the Perl Monks concerning the following question:

A couple of years ago I worked on an arrangement problem, a "lunch bunch." The basic idea is that 64 people want to go out to lunch together in eight groups of eight at a time, with the groups rearranging each month so that everyone gets to have lunch with each of the others and no two people have lunch together twice.

With 49 people, or other prime squares, we can arrange a square and make the sets as follows:

1 2 3 4 5 6 7 <- shift by 0 8 9 10 11 12 13 14 <- shift by 1 15 16 17 18 19 20 21 <- shift by 2 22 23 24 25 26 27 28 <- shift by 3 29 30 31 32 33 34 35 <- shift by 4 36 37 38 39 40 41 42 <- shift by 5 43 44 45 46 47 48 49 <- shift by 6

The first set is the rows as-is, the second set is the columns as-is, and the subsequent sets are generated by shifting the rows as indicated and then reading down the columns. This gives eight total groupings, which covers all the members with no duplication.

When I went to expand the solution to 8x8, the simple shifting idea wouldn't work, because shifts by 2, 4, and 6 caused duplicated positions. What I ending up doing was finding a Galois field of order 8 and using that for shifting instead.

# The multiplication and addition tables are derived from # a Galois field order(2^3), from (0, 1, a, a^2, ... a^6) # where a^3 = a + 1. # # multiply # 0 1 a a^2 a^3 a^4 a^5 a^6 # ------------------------------------------------------ # 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | # |------------------------------------------------ # 1 | 0 | 1 | a | a^2 | a^3 | a^4 | a^5 | a^6 | # |------------------------------------------------ # a | 0 | a | a^2 | a^3 | a^4 | a^5 | a^6 | 1 | # |------------------------------------------------ # a^2| 0 | a^2 | a^3 | a^4 | a^5 | a^6 | 1 | a | # |------------------------------------------------ # a^3| 0 | a^3 | a^4 | a^5 | a^6 | 1 | a | a^2 | # |------------------------------------------------ # a^4| 0 | a^4 | a^5 | a^6 | 1 | a | a^2 | a^3 | # |------------------------------------------------ # a^5| 0 | a^5 | a^6 | 1 | a | a^2 | a^3 | a^4 | # |------------------------------------------------ # a^6| 0 | a^6 | 1 | a | a^2 | a^3 | a^4 | a^5 | # |------------------------------------------------ # # add # # 0 1 a a^2 a^3 a^4 a^5 a^6 # ------------------------------------------------------ # 0 | 0 | 1 | a | a^2 | a^3 | a^4 | a^5 | a^6 | # |------------------------------------------------ # 1 | 1 | 0 | a^3 | a^6 | a | a^5 | a^4 | a^2 | # |------------------------------------------------ # a | a | a^3 | 0 | a^4 | 1 | a^2 | a^6 | a^5 | # |------------------------------------------------ # a^2| a^2 | a^6 | a^4 | 0 | a^5 | a | a^3 | 1 | # |------------------------------------------------ # a^3| a^3 | a | 1 | a^5 | 0 | a^6 | a^2 | a^4 | # |------------------------------------------------ # a^4| a^4 | a^5 | a^2 | a | a^6 | 0 | 1 | a^3 | # |------------------------------------------------ # a^5| a^5 | a^4 | a^6 | a^3 | a^2 | 1 | 0 | a | # |------------------------------------------------ # a^6| a^6 | a^2 | a^5 | 1 | a^4 | a^3 | a | 0 | # |------------------------------------------------ BEGIN { @Field8::mtable = ( [0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7], [0, 2, 3, 4, 5, 6, 7, 1], [0, 3, 4, 5, 6, 7, 1, 2], [0, 4, 5, 6, 7, 1, 2, 3], [0, 5, 6, 7, 1, 2, 3, 4], [0, 6, 7, 1, 2, 3, 4, 5], [0, 7, 1, 2, 3, 4, 5, 6] ); @Field8::atable = ( [0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 4, 7, 2, 6, 5, 3], [2, 4, 0, 5, 1, 3, 7, 6], [3, 7, 5, 0, 6, 2, 4, 1], [4, 2, 1, 6, 0, 7, 3, 5], [5, 6, 3, 2, 7, 0, 1, 4], [6, 5, 7, 4, 3, 1, 0, 2], [7, 3, 6, 1, 5, 4, 2, 0] ); }

I would like to generalize this solution to other cases. I think it's impossible for composite orders like 6 or 10, but all orders that are powers of primes should work.

I see a math package on cpan called Math::Pari and that is has functions for Galois fields, but I am not sure how to use it to generate tables like the ones above. Has anyone worked with Math::Pari or other packages that might help? Thanks.

Replies are listed 'Best First'.
Re: Lunch Bunch arrangement problem
by abell (Chaplain) on May 17, 2003 at 10:25 UTC

    Try using the following gp script:

    multable( p, P, g ) = { P = Mod(1,p) * P; g = Mod( Mod(1,p) * g, P ); d = poldegree( P ); n = p^d; /* This version makes B[2] = Mod( 1, P ) which is wrong B = concat( [0], vector( n-1, i, g^(i-1) ) ); The following line corrects the mistake */ B = concat( [0], vector( n-1, i, Mod( Mod(1,p), P ) * g^(i-1) ) ); R = vector( n ); for( i = 1, n, R[ 1 + subst( lift(lift( B[i] )), x, p )] = i-1; ); for( a = 1, p^d, ae = B[a]; for ( b = 1, p^d, be = B[b]; re = ae * be; print1( R[ 1 + subst( lift(lift( re )), x, p )], "\t" ); ); print; ); }
    Save it in a file (say "ff.gp") and then invoke gp (it's an interactive environment for pari). A sample session might be
    $ gp -q
    ? read ("/tmp/ff.gp")
    ? multable(2, x^3+x+1, x)
    0       0       0       0       0       0       0       0
    0       1       2       3       4       5       6       7
    0       2       3       4       5       6       7       1
    0       3       4       5       6       7       1       2
    0       4       5       6       7       1       2       3
    0       5       6       7       1       2       3       4
    0       6       7       1       2       3       4       5
    0       7       1       2       3       4       5       6
    ? 
    
    The arguments to multable are the characteristic, the polynomial generating the field and a generator of the multiplicative group. To generate the addition table, substitute with re = ae + be on the due line.

    Cheers

    Antonio

    The stupider the astronaut, the easier it is to win the trip to Vega - A. Tucket

    Update: The mistake for g^0 + g^0 should be corrected now
      Thanks, Antonio. It looks very close to what I need, but I am getting some errors. For example, when I try for the addition table:
      ? addtable(2, x^3+x+1, x) 0 1 2 3 4 5 6 7 1 2 4 7 2 6 5 3 2 4 0 5 1 3 7 6 3 7 5 0 6 2 4 1 4 2 1 6 0 7 3 5 5 6 3 2 7 0 1 4 6 5 7 4 3 1 0 2 7 3 6 1 5 4 2 0
      The second entry on the second line is supposed to be 0, not 2. I also tried for 3^2, like this:
      ? multable(3,x^2+x+1,x) 0 0 0 0 0 0 0 0 0 + 0 7 8 6 7 8 6 7 8 + 0 8 6 7 8 6 7 8 6 + 0 6 7 8 6 7 8 6 7 + 0 7 8 6 7 8 6 7 8 + 0 8 6 7 8 6 7 8 6 + 0 6 7 8 6 7 8 6 7 + 0 7 8 6 7 8 6 7 8 + 0 8 6 7 8 6 7 8 6
      This table doesn't look right at all. What could be going wrong?

      Update:For the 3^2 case, I see that I didn't use a correct primitive polynomial for GF(3). I tried "x^2+2*x+2" and it looks a lot better. Now I just need to find a way to get other primitive polynomials...

      Update2: I found a program than can compute a primitive polynomial of any order for GF(n), here.

Re: Lunch Bunch arrangement problem
by shemp (Deacon) on May 16, 2003 at 18:48 UTC
    I ran across similar problems in my undergrad math, and its been quite a while, but i swear there was a way to generate these "schedules" with modular equations, although that approach is probably isomorphic to using Galois fields.

    Is it possible to use a field defined by generators whose orders are the prime factors of the desired composite order? For instance for 6 people, could you do something with generating the list (somehow) with galois fields of orders 2 and 3.

    Sorry if this is rambling, its been quite a while, but i swear something along those lines works.
    When you say that you think its impossible for composite orders, do you mean impossible to generalize, or that there are no solutions? I assume that you mean the former.
      I believe the 6x6 case has no solutions. The proof is the 36 Officer Problem.

      How can a delegation of six regiments, each of which sends a colonel, a lieutenant-colonel, a major, a captain, a lieutenant, and a sub-lieutenant be arranged in a regular 6x6 array such that no row or column duplicates a rank or a regiment? The answer is that no such arrangement is possible.

      Suppose they were trying to form lunch bunches: the first arrangement is all the same rank, the second is all the same regiments. Then we know there is no third arrangement and the schedule fails.

        Sorry, I was misreading the original post. I was thinking more along the lines of pairwise scheduling, like for certain sports, where every team in the league plays each week, and plays each team exactly once.

        This is a much different problem. It sounds like something Erdos would have worked on.
        I know this wont help you, but could you point me at some info regarding the problem?

        party on,
        shemp
Re: Lunch Bunch arrangement problem
by shemp (Deacon) on May 21, 2003 at 15:53 UTC
    Did you run across a proof that there are no lunch bunch arrangements for orders that arent powers of one prime? Basically this would be a generalization of the 36 officer problem. It seems pretty likely that your statement is correct

    I think it's impossible for composite orders like 6 or 10, but all orders that are powers of primes should work.

    Seeing as those are the only orders of Galois fields.
    I'm asking because if you're not aware of a generalized proof, I'd probably be willing to take a shot at it. I havent done much algebra in a number of years, but it would be a good refresher. :)
      I don't know of a general proof. I know Euler had a conjecture that two orthogonal Euler squares of order 10 could not be found. That conjecture was disproved when a 10x10 pair was found (but a pair is not enough to create lunch bunches). Here is the reference.

      Update: A lunch bunch arrangement is a resolvable block design of the form (n^2, n, 1), which is also known as an affine plane. An affine plane of order n exists if and only if a projective plane of order n exists. In the projective plane article it states:

      A finite projective plane exists when the order n is a power of a prime...It is conjectured that these are the only possible projective planes, but proving this remains one of the most important unsolved problems in combinatorics.

      So if one could prove the above conjecture, it would prove that the only lunch bunches are of the order of powers of a prime.

        Well, with that knowledge, this is probably beyond the scope of my time and / or ability. But we'll see...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://258696]
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (5)
As of 2024-03-28 16:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found