|
|
|
|
| View previous topic :: View next topic |
| Author |
Message |
bonanova
Daedalian Member
|
Posted: Fri Jul 17, 2009 8:45 am Post subject: 1 |
|
|
I was playing with the following discrete puzzle and wondering if it has a continuous extension:
n balls numbered 1-n are placed in each of 10 urns.
A certain number m of balls is removed from each urn.
The remaining balls have the following property:
1. if any 5 urns are emptied into a bowl, there will be at least one ball with each of the numbers 1-n
2. if any 4 urns are emptied into a bowl, there will be at least one missing number. The problem asks what is the smallest n that makes this possible, and what is the value of m?
It does not ask which m balls are removed from the urns - a different subset is obviously removed from each urn.
I reasoned that if 10 unique subsets of the set [1, ..., n] can be found with these two conditions for a finite n,
there should be 10 unique subsets of the reals on [0, 1] with the same properties:
the union of any 5 subsets covers the interval, but of any 4 does not.
Maybe it's trivial, but I couldn't find a starting point. Any thoughts?
OK all i had to do is post this and I see the answer.
So let's add the question: what parts of the interval are removed in the ten cases? _________________
Vidi, vici, veni.
|
|
| Back to top |
|
 |
ralphmerridew
Daedalian Member
|
Posted: Fri Jul 17, 2009 1:46 pm Post subject: 2 |
|
|
Minimal n is 10C6 = 210.
If any ball appears in 5 or fewer urns, then choose the other 5 urns and you'll miss that ball. If any ball appears in 7 or more urns, remove that ball and the result will have fewer balls but still have properties 1 and 2. Therefore every ball appears in exactly 6 urns.
Consider any set of six urns. There must be at least one ball that appears in exactly those 6 urns, or choosing the other 4 would get all the balls. There must be at most one, or one of them could be removed without disturbing properties 1 or 2.
Therefore, n = 10C6 in a minimal solution. |
|
| Back to top |
|
 |
Zag
Tired of his old title
|
Posted: Fri Jul 17, 2009 2:27 pm Post subject: 3 |
|
|
| I was going to say 10C4, for exactly the same reason (which is, of course, the same answer). My thinking was that for every group of 4 urns, there is exactly 1 ball missing, which must be in all the remaining urns. |
|
| Back to top |
|
 |
|
|
You cannot post new topics in this forum You can reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|