jump to navigation

Problem of the Day #56: Spring Cleaning May 14, 2011

Posted by Aziz in : potd , trackback

Five people, Sreenath, Mitchell, Alex, Albert and Sam, live in the same house and need to clean up before their parents come visit.

Each person gets his own room. A person will clean only their own room. Each person’s own room has a certain mess level, greater values requiring more cleaning. A cycle consists of everyone cleaning a certain amount of their own room and dumping the rest of their mess into another person’s room. Each person is required to clean between $5$ and $20$ of their mess each cycle. Whatever is left uncleaned is dumped into a randomly chosen other person’s room. Whenever someone dumps their remaining mess, the person receiving it will gain an additional 5 mess units as a cost for dumping.

Mess Factor of:
Sreenath — 150
Mitchell — 80
Alex — 50
Albert — 10
Sam — 70

The goal is to minimize the number of cycles it takes to clean the house.

Determine the expected number of cycles it would take if everyone acted independently and if they came up with and followed an optimal plan before beginning the cleanup.


no comments yet - be the first?