Author |
Topic: combinatorics insane problem (Read 933 times) |
|
grish
Newbie
Gender: 
Posts: 5
|
 |
combinatorics insane problem
« on: Jul 11th, 2006, 6:55am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: combinatorics insane problem
« Reply #1 on: Jul 11th, 2006, 10:21am » |
Quote Modify
|
Whats' the question?
Whether a schedule meeting the conditions is possible?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
grish
Newbie
Gender:
Posts: 5
|
|
Re: combinatorics insane problem
« Reply #2 on: Jul 11th, 2006, 12:59pm » |
Quote Modify
|
yeah, thats (^^) the question, sorry, lol. Any help would be appreciated.
grish
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: combinatorics insane problem
« Reply #3 on: Jul 11th, 2006, 3:43pm » |
Quote Modify
|
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.
|
| « Last Edit: Jul 11th, 2006, 3:44pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: combinatorics insane problem
« Reply #4 on: Jul 12th, 2006, 1:14pm » |
Quote Modify
|
This 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.
|
| « Last Edit: Jul 12th, 2006, 2:09pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: combinatorics insane problem
« Reply #5 on: Jul 12th, 2006, 2:04pm » |
Quote Modify
|
on Jul 11th, 2006, 3:43pm, towr wrote:| Sounds like something best solved by programming.. |
|
Did somebody say "programming"? 
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
|
|
IP Logged |
--SMQ
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: combinatorics insane problem
« Reply #6 on: Jul 12th, 2006, 5:26pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
grish
Newbie
Gender:
Posts: 5
|
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
|
| « Last Edit: Jul 13th, 2006, 7:21am by grish » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: combinatorics insane problem
« Reply #8 on: Jul 13th, 2006, 7:20am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
grish
Newbie
Gender:
Posts: 5
|
|
Re: combinatorics insane problem
« Reply #9 on: Jul 13th, 2006, 7:23am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
Well, here's how it basically works:
First it generates all 2520 unique scheduling permutations (2520 = 8!/24 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
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: combinatorics insane problem
« Reply #11 on: Jul 14th, 2006, 5:29am » |
Quote Modify
|
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.
|
| « Last Edit: Jul 14th, 2006, 5:31am by Grimbal » |
IP Logged |
|
|
|
grish
Newbie
Gender:
Posts: 5
|
|
Re: combinatorics insane problem
« Reply #12 on: Jul 14th, 2006, 6:06am » |
Quote Modify
|
just curious, could i perhaps see the code for that?
thanks, you guys rock, and your help is greatly appreciated
grish
|
| « Last Edit: Jul 14th, 2006, 6:07am by grish » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: combinatorics insane problem  sched.c
« Reply #13 on: Jul 14th, 2006, 6:16am » |
Quote Modify
|
Here. Just as quick and dirty as SMQ's.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print