The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

   
The Grey Labyrinth Forum Index
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups    RegisterRegister  
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Ten subsets of [0, 1]

 
Reply to topic    The Grey Labyrinth Forum Index -> Visitor Submitted Puzzles
View previous topic :: View next topic  
Author Message
bonanova
Daedalian Member



PostPosted: Fri Jul 17, 2009 8:45 am    Post subject: 1 Reply with quote

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
View user's profile Send private message
ralphmerridew
Daedalian Member



PostPosted: Fri Jul 17, 2009 1:46 pm    Post subject: 2 Reply with quote

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
View user's profile Send private message AIM Address Yahoo Messenger
Zag
Tired of his old title



PostPosted: Fri Jul 17, 2009 2:27 pm    Post subject: 3 Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website Yahoo Messenger
Display posts from previous: by   
Reply to topic    The Grey Labyrinth Forum Index -> Visitor Submitted Puzzles All times are GMT
Page 1 of 1

 
Jump to:  
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
Site Design by Wx3