13
$\begingroup$

I am an undergraduate student studying languages and give private lessons to secondary school students to help them learn English. Recently one of them suddenly asked me during a lesson whether I could help him solve a logical problem given to him by his math teacher as a part of an assignment. I agreed, but only managed to come up with a half-intuitive answer. Seeing my confusion, the boy told me to get on with the English lesson. I'm very curious whether I told him the right answer, and I'm curious how to solve the problem.

The problem is this: There's a pet shop, and there are 100 pets inside it. Those pets are hamsters, ferrets, chinchillas, and guinea pigs. That is, four mutually exclusive kinds of pets. You don't know how many pets of each kind are there in the shop, but, as stated above, you know that the total number is 100. And you also know one more thing: if you select any 85 pets in this shop, then there will invariably be at least one hamster, at least one ferret, at least one chinchilla, and at least one guinea pig among the selected pets. And here is the question: given this information, how many pets must you select at random in this shop to ensure that the selected pets are of at least three different kinds?

The half-intuitive answer I gave the boy is 69, but I'm highly unsure whether I'm not missing anything, because there are a multitude of possibilities within the restrictions specified in the problem. The logic needed to solve the problem seems very convoluted, and I am lost in my chaotic thoughts.

Can you come up with a logically clear solution and tell me what the right answer is?

Improve this question
$\endgroup$
1
  • $\begingroup$ Your answer looks correct to me. The easiest way of thinking about it would I think be reversing and inverting. For example, the opposite of "at least one of each" would be "none of at least one". "none of" in your selection can be reversed to "all" in what you left out. Etc. $\endgroup$
    – Paul Panzer
    Oct 26, 2020 at 22:06

2 Answers 2

Reset to default
16
$\begingroup$

if you select any 85 pets in this shop, then there will invariably be at least one hamster, at least one ferret, at least one chinchilla, and at least one guinea pig

This means there are at least 16 of each type. Otherwise, you could pick 85 and avoid the type that has only 15 or fewer.

So when you've picked all but 32 (twice the minimum for one type, 2*16), you might still have only two types, but once you've picked one more, you must have three types. So you're right: 69 is how many you need (the total number minus the minimum for two types plus one, 100-32+1).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Since OP is asking for clarity: I think would be good to mention that 16 is a tight bound, i.e. not only necessary but also sufficient. Because if you only know you can prove 16 or more but do not know whether perhaps some clever proof exists for 17 or more you cannot know whether 69 is the best you can do. $\endgroup$
    – Paul Panzer
    Oct 27, 2020 at 14:03
  • $\begingroup$ @PaulPanzer It would be good to mention the word "ensure", maybe. Because with the description given you can show an example where you pick 68 pets that are only two types, and the 69th pet picked is a third type, so it's not possible to ensure three types with fewer than 69. $\endgroup$
    – user3067860
    Oct 27, 2020 at 15:04
  • $\begingroup$ @user3067860 Same thing, only "ensure" is the general concept, 16 being tight or not is the concrete thing that needs consideration. $\endgroup$
    – Paul Panzer
    Oct 27, 2020 at 15:36
  • $\begingroup$ @PaulPanzer No, I'm still not following you. It's possible to show an example with only 16 of one type of pet that meets all of the criteria in the question. There really is no possibility for a more-clever proof showing a better number given the criteria in the question. $\endgroup$
    – user3067860
    Oct 27, 2020 at 15:51
  • $\begingroup$ @user3067860 Yes, I know it's possible. All I'm saying is that for a complete argument you need to explicitly state so. Clarity means being aware of the "mechanics" of the argument. $\endgroup$
    – Paul Panzer
    Oct 27, 2020 at 16:04
0
$\begingroup$
  1. 100 animals of 4 types
  2. If you select 85 there are guaranteed to be all 4 types

This means you can exclude any 15 animals and you will not be excluding all of any one type of animal, so there must be at least 16 of each animal type. If 3/4 animal types have the minimum of 16, that is 48 so the other animal could have a population of 52.

  1. How many do you need to select to be guaranteed at least 3 different kinds?

My first thought was to start with the extreme where one type has 52 and the other types have the minimum. That means you would need 52 + 16 + 1 or 69 animals if you happened to select all of the most populous type and all of another type.

Working the other way, if you omit all of one of the smallest type (16) and all but one of another of the smallest types (15), that is 31 you are leaving out to ensure you have at least 1 of three types. 100-31 is 69 so that agrees with the other way.

So I say 69 is the answer.

It's worth noting that the problem as stated doesn't say you have to select 85 to be guaranteed to have one of each type, just that if you do select 85 you are guaranteed to have at least one of each type.

If could be that each type has exactly 25 members. In that case you would be guaranteed to get one of each type if you select any 76 pets, but that also means you would be guaranteed to have onE of each if you select 85, or any other number above 75.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.