wu :: forums - Print Page


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

        riddles >> hard >> combinatorics insane problem
        
(Message started by: grish on Jul 11^th, 2006, 6:55am)

Title: combinatorics insane problem
Post by grish on Jul 11^th, 2006, 6:55am

Situation
Your school club is sponsoring a 2 day festival. You have 4 booths you need to staff with two students each on one hour shifts. Just for your convenience call the Students Tracy, Cara, Matt, Shumoni, Danika, Margaret, Craig and Katie

Condition
1. Each student works each booth on the first day and again works each booth on the second day.
2. Over the 2 day period, (8 shifts) each student works with each of the other 7 students, repeating with another student only once.
(From the original problem, the 4booths are red booth, blue booth, green booth, and yellow booth. Time shift is 10-11, 11-12,12-1,1-2)

Definately need some help with this one, either a proof for either positive or negative, or a solution, thanks

Title: Re: combinatorics insane problem
Post by towr on Jul 11^th, 2006, 10:21am

Whats' the question?
Whether a schedule meeting the conditions is possible?

Title: Re: combinatorics insane problem
Post by grish on Jul 11^th, 2006, 12:59pm

yeah, thats (^^) the question, sorry, lol. Any help would be appreciated.
grish

Title: Re: combinatorics insane problem
Post by towr on Jul 11^th, 2006, 3:43pm

Sounds like something best solved by programming..

8 shifts, 4 table that's 32 pairs
you have 8*7/2=28 unique pairs. So given the conditions, exactly 4 pairs are used twice, and the rest is used once.

You can fill the first shift any way you want, so you really only need to puzzle over the last 7.

Title: Re: combinatorics insane problem
Post by THUDandBLUNDER on Jul 12^th, 2006, 1:14pm

This (http://www.jdawiseman.com/papers/tournaments/all-play-all/apa_08.html) is the best I can find, with the last pairings being
8 G:E F:H C:A B:D
although I have just noticed that 1) is not satisfied as it is.
Permuting the 8 sets of pairings might give a solution.

Title: Re: combinatorics insane problem
Post by SMQ on Jul 12^th, 2006, 2:04pm

on 07/11/06 at 15:43:18, towr wrote:

Sounds like something best solved by programming..

Did somebody say "programming"? ;D

My computerized search did not find any solutions.

However, in order to get the run time down under an hour the program has become complex enough that I'm not 100% convinced of its accuracy any more... I'm currently working on verifying the result.

--SMQ

Title: Re: combinatorics insane problem
Post by SWF on Jul 12^th, 2006, 5:26pm

After trying this manually, it looks like there is a good chance this is impossible. The pairings that are duplicated seem to cause the the biggest problems with completing the remainder of schedule.

I was able to fill the morning sessions without using any duplications. If the names are changed to 1,2,3...8, the columns are the 4 booths, and the rows are time slots, a morning session that works without repeating any pairings is:

12 34 56 78
67 58 13 24
38 26 47 15
45 17 28 36

Title: Re: combinatorics insane problem
Post by grish on Jul 13^th, 2006, 7:02am

yeah, that is what i was thinking. the first day schedule was the easiest. After that, it gets more difficult. I was able to get 6 shifts done, but the problem came that of the eligible pairs, one person in the pair had worked two of the booths, and the other person had worked the other 2 booths that day. that file is the farthest i have gotten, i believe.
It's on sheet 2, sheet 1 is a bunch of random work.
grish

Title: Re: combinatorics insane problem
Post by SMQ on Jul 13^th, 2006, 7:20am

OK, I now trust my computer results: it is possible to schedule seven shifts, but not all eight. One possible schedule for seven shifts (in SWF's notation) is:

12 34 56 78
34 56 78 12
57 18 23 46
68 27 14 35

13 24 58 67
25 16 37 48
47 38 26 15

--SMQ

Title: Re: combinatorics insane problem
Post by grish on Jul 13^th, 2006, 7:23am

thanks man. However, can anyone prove that without programming? or if not, could i perhaps see your program, if you would be so kind as to e-mail it to me or something along those lines?

thanks,
grish

Title: Re: combinatorics insane problem
Post by SMQ on Jul 13^th, 2006, 7:56am

Well, here's how it basically works:

First it generates all 2520 unique scheduling permutations (2520 = 8!/2⁴ since the ordering of the two students assigned to each booth is irrelevent).

Then it arbitrarily assigns the first shift as 12 34 56 78.

Then it performs a depth-first search for a solution by assigning the second shift as null, setting the current shift to 2, and looping the following:
If the current shift is 8 and the current assignment is not null, print a solution
Find the next allowed permutation for the current shift
If the next allowed permutation is not null, increment the current shift and assign the new current shift as null, otherwise decrement the current shift
Repeat while the first assignment of the second shift is either 34 or 35 (all others will be equivalent to one of these)

The full (quickly-written, nasty) C++ code is attached.

--SMQ

Title: Re: combinatorics insane problem
Post by Grimbal on Jul 14^th, 2006, 5:29am

I tried another method:
- make a list of all 4! permutations of 4 numbers.
This represents where a student can be in the morning or in the afternoon.
- Assign permutation 1234 for the morning and the afternoon of the first student.
- do a depth-first search for the remaining 7 students, adding one student at a time. At each level choose 2 permutations, one for the morning, one for the afternoon. Check that the new student meets all previous students and that no booth is occupied more than twice.
- when 8 students could be added, print the solution.

The program did not print any solution.

Title: Re: combinatorics insane problem
Post by grish on Jul 14^th, 2006, 6:06am

just curious, could i perhaps see the code for that?

thanks, you guys rock, and your help is greatly appreciated
grish

Title: Re: combinatorics insane problem
Post by Grimbal on Jul 14^th, 2006, 6:16am

Here. Just as quick and dirty as SMQ's.