Author |
Topic: Impatient Patients (Read 1601 times) |
|
Frost
Newbie
Posts: 14
|
 |
Impatient Patients
« on: Jul 30th, 2002, 9:16am » |
 Quote  Modify
|
Impatient Patients
All patients at the d'Oralian National Hospital require constant care. At least one nurse must be beside a patient's bed at any time and a nurse can only care for one patient simultaniously.
The nurses won't work more that eight hours within any 24 hour period, but don't care when their shift starts. Their shifts look like this: work five hours, one hour break, work another three hours.
How many nurses do you need for one patient?
How many nurses do you need for n patients?
|
| « Last Edit: Oct 23rd, 2003, 7:57pm by Icarus » |
 IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Re: NEW puzzle: Impatient Patients
« Reply #1 on: Jul 30th, 2002, 6:23pm » |
Quote Modify
|
Maybe my question is stupid, but do the nurses have to be there each day in contiguous 9 hour blocks? Or can I break up their work distribution?
For instance, for one patient, nurse A works for the first 5 hours, then takes a break. Then nurse B takes over for one hour during the break.
Then nurse A resumes for another 3 hours. But during these 3 hours, what is nurse B doing? Does she have to be considered "working" since the labor blocks are contiguous and her block has already started? Or can nurse B just be considered idle, so that when nurse A is finished, we'll still have 7 hours of labor + 1 hour of rest on reserve in nurse B?
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW puzzle: Impatient Patients
« Reply #2 on: Aug 1st, 2002, 9:06pm » |
Quote Modify
|
Sorry Will, I believe once she has started she must continue on as planned -- it's like a tiling problem.
Frost: Nice problem! Without giving away the particulars of the solution, here is what I've come up with so far as far as numbers:
n f(n) = required nurses
-- -------------------------
0 0
1 4
2 8
3 10
4 14
5 18
6 20
7 24
>8 24*(n div 8) + f(n mod 8)
I'm a little leary of 7 -- I'm guessing it should be 22 but I couldn't find the soln and am a bit tired for now.
How'm I doing?
Thanks,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
snags697
Newbie
Mad Physicist
Gender:
Posts: 14
|
|
Re: NEW puzzle: Impatient Patients
« Reply #3 on: Aug 8th, 2002, 8:50am » |
Quote Modify
|
I managed to find a solution for 2 patients with only 7 nurses. Start the nurses' shifts at 0:00, 1:00, 3:00, 10:00, 12:00, 15:00, and 20:00. It covers both patients at all hours. It's a little counter-intuitive, because 2 hours are covered by 4 nurses, but it works.
As far as explaining my method, I just used a spreadsheet with a column for each nurse and a row for each hour. I moved blocks of 1's and 0's around to represent each shift, and watched the total hours for each row until I managed to get them all >= 2. I'm sure there's a better method.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW puzzle: Impatient Patients
« Reply #4 on: Aug 8th, 2002, 1:08pm » |
Quote Modify
|
Ye, sorry, I made a mistake -- too lazy. 
Basically I concentrated on the two problems of 1) solving for 1 and 2) finding the first perfect, which I believe occurs at 8. The intermediate values were just kinda plodding about looking for decent fits.
So Will, should I take your downgrading of this problem to medium to mean that you know the full soln? I agree that certainly the CS soln is not too hard, but a good mathematical soln hasnt yet crossed my mind.
Also, is this really an original problem? I thought that I had read it before, or at least similar tiling problems.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
rugga
Newbie
Gender:
Posts: 21
|
|
Re: NEW puzzle: Impatient Patients
« Reply #5 on: Sep 9th, 2002, 3:46am » |
Quote Modify
|
Eric, is there a way to prove your formula for n>=8:
f(n) = 24*(n div 8) + f(n mod 8)
What I mean is, I see that 8 patients can be done with 24 nurses, and I see that less than 8 patients require some wastage. But might it be possible that for larger numbers of patients I could be especially clever and be even more efficient? For example maybe I can do 17 patients with exactly 51 nurses by throwing out the 8-patient "tiling" and doing something ad hoc.
Can it be proven that the optimal solution is always to copy the 8-patient solution as much as possible and then "mop up" what remains? Is this just obvious? Is there some deeper principle here I'm missing?
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW puzzle: Impatient Patients
« Reply #6 on: Sep 9th, 2002, 5:46am » |
Quote Modify
|
Rugga,
Nope: Every nurse works 8 hrs, and each patient needs 24 nurse-hours of care, so the min is always 3n nurses. In other words, the 8 patient tiling is already "perfect", so no improvement can be made.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
rugga
Newbie
Gender:
Posts: 21
|
|
Re: NEW puzzle: Impatient Patients
« Reply #7 on: Sep 10th, 2002, 11:56pm » |
Quote Modify
|
I understand that 3n is a lower bound. My question is: when the number of patients isn't a multiple of 8, can one do better than
24 (n div 8) + f(n mod 8)?
Given that 1 patient requires 4 nurses. Can you prove that 8n+1 patients always requires 24n + 4 nurses instead of 24n + 3? Just because the tiling solution perfectly solves 8n patients doesn't imply that the optimal solution for 8n+1 (for any n) patients necessarily includes that 8n solution as a subsolution, does it?
Sorry if my question seems dense, but it seems nonobvious to me. Thanks for your response.
-Mark
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW puzzle: Impatient Patients
« Reply #8 on: Sep 11th, 2002, 6:50am » |
Quote Modify
|
No, you're right -- I obviously didn't spend enough time thinking about this one. Apologies for misunderstanding your previous msg.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
MAT
Guest
|
|
Re: NEW puzzle: Impatient Patients
« Reply #9 on: Jun 4th, 2003, 6:40am » |
Quote Modify
 Remove
|
Since all scheduled hours of 24 nurses are used by 8 patients there are no spare hours left to reduce the number of nurses used by additional patients. This means that the number of required nurses will always be equal to:
3n (if n mod 8 = 0)
or
3n + 1 (if n mod 8 > 0)
ps. Here is the fixed table for f(n):
number of patients n/needed nurses f(n)/spare hours/starting hour every nurse
1/4/8/0;3;12;15
2/7/8/0;1;3;10;12;15;20
3/10/8/0;1;3;4;10;12;13;15;20;21
4/13/8/0;1;2;4;7;9;11;12;14;15;17;20;22
5/16/8/0;1;2;3;5;6;8;9;11;12;14;16;17;19;20;21
6/19/8/0;1;2;3;4;5;7;8;10;11;12;13;14;16;17;19;20;21;22
7/22/8/0;1;2;3;4;5;6;7;8;9;10;11;12;13;15;16;17;18;19;20;21;22
8/24/8/0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20;21;22;23
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW puzzle: Impatient Patients
« Reply #10 on: Jun 4th, 2003, 7:34am » |
Quote Modify
|
MAT,
I agree that every 8n+x most likely requires n of the perfect tilings, but we have not given a rigorous proof. There's no obvious reason that, for example, 87 = 10*8+7 patients might not be tiled with one less than 10*24+22 nurses -- through the use of some clever tilings not utilizing the perfect 24's all the way through.
(BTW, I think you forgot to update the wasted hours column.)
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print