All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Candy Box (Posted on 2004-10-08) Difficulty: 3 of 5
A box of candies can be equally divided by weight without cutting pieces between three, four or seven people.
Each piece is an integral number of ounces.
What is the least number of pieces of candy the box could contain? The candies may be of different weights.

See The Solution Submitted by Brian Smith    
Rating: 3.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution | Comment 7 of 18 |
The minimum is 11, achievable by the following weights:  {1,2,4,5,7,8,10,11,12,12,12}.  The partitions are {12}, {12}, {12}, {1,11}, {2,10}, {4,8}, {5,7} for seven people, {4,5,12}, {1,8,12}, {2,7,12}, {10,11} for four people, and {4,12,12}, {7,10,11}, {1,2,5,8,12} for three people. 

To see that 10 is impossible, assume for sake of contradiction that a1,a2,...,a10 are weights summing to 84N for some integer N (see Charlie's post to see why the sum must be of this form).  When dividing this among seven people, it must be the case that at least four people each receive one piece of candy, so we can set a1=a2=a3=a4=12N. 

Now, when dividing among four people, each person must receive 21N, so that each person receives exactly one 12N piece (otherwise some person gets more than one 12N piece).  The remaining 6 candies get distributed among these four, 9N per person.  So at least two of the people receive one more candy each.  We can thus set a5=a6=9N. 

Now let us go back to divding among seven people.  Since we can't have any more 12N pieces, we have that two of the candies among a7,a8,a9,a10 add up to 12N and the other two complement the 9N pieces to make two-candy sets adding to 12N.  In other words, we necessarily have a7=a8=3N. 

Back to four people, we have that two people receive {12N,9N} candy sets, and that the other two receive candy from the set {12N,12N,3N,3N,a9,a10}.  We see that either (a9,a10)=(6N,6N) or (3N,9N).  In either case, all candies are multiples of 3N, so that it becomes impossible to allot 28N per person for the three-person division. 

It follows that ten people is impossible.  Eleven is thus the optimal solution.

  Posted by David Shin on 2004-10-08 14:01:26
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information