Pick up minimum number to inequality

Probability Level 5

Find the minimum value of $x$ such that for any $x$ numbers chosen from $\{1,2,3,\ldots,138\}$ , there exists two of them $p$ and $q$ such that $\dfrac 23 \leq \dfrac pq \leq \dfrac32$ .

The answer is 11.

1 solution

Choi Chakfung
Apr 21, 2016

we can group the number group by group first:
group 1 (1)
group 2 (2-3)
group 3 (4-6)
group 4 (7-10)
group 5 (11-16)
group 6 (17-25)
group 7 (26-39)
group 8 (40-60)
group 9 (61-91)
group 10 (92-138)

If we draw one from each group , we can make sure our next draw can contain two number such that $\dfrac 23 \leq \dfrac pq \leq \dfrac32$ . Therefore , the answer is 10 +1 =11

Moderator note:

The better way to phrase the final paragraph is to apply the pigeonhole principle . If we chose 11 numbers, then at least $\lceil \frac{11}{1} \rceil =2$ of them must fall in the same group. We can then verify that these 2 numbers will satisfy the condition, hence we are done.

The better way to phrase the final step is to apply the pigeonhole principle . If we chose 11 numbers, then at least 2 of them must fall in the same group, and hence we will obtain the required condition.

Calvin Lin Staff - 5 years, 1 month ago

Yes I also made a worst possible group of 10 elements namely {1,2,4,7,11,17,26,40,61,92}. Now if we choose these numbers and any other number of the set it can form a p and q pair of required conditions with 92 because no number less than or equal to 138 is there which doesn't follow the required condition with 92.

Kushagra Sahni - 5 years, 1 month ago

Kushagra, your solution while believable, is not rigorous. This is because it is unclear what "worst possible group" actually means. You need to justify the claim that is indeed the "worst", especially since there are other sets of 10 numbers which satisfy the condition.

Calvin Lin Staff - 5 years, 1 month ago

It is the worst possible because the question asks us to find at least two numbers satisfying the condition in every possible value of x. If we prove that if x=11 even the worst case is true so other cases will obviously be true even in lower values of x. I took the 1st element to be 1 and as this is the most disobedient set I wanted p/q to be greater than 1.5 so we can choose next element to be 2. Then for 2 numbers greater than 3 should be there and so I included 4. This way I mutiplied each element by 1.5 and checked which numbers can enter the set. This brought me to that set.

Kushagra Sahni - 5 years, 1 month ago

@Kushagra Sahni – I understand what you are thinking and wanting to say. I'm just pointing out that your solution isn't rigorous, even though you think it is. Your solution never shows why 11 is not ever possible in all cases, but only that "we can't get to 11 from this worst case scenario of 10". It is
1. Not clear why that's a worst case scenario
2. Not clear why there are no other equivalent worst case scenarios that could lead to a result of 11.
3. Not clear why there are no other scenarios that could lead to a result of 11.

Note: I've been in the same position before. The difficulty that you're facing is in expressing your ideas in a clear manner that someone else can immediately understand without disputing your claims.

Calvin Lin Staff - 5 years, 1 month ago

@Calvin Lin – All right I got your point. I think that's quite difficult to prove that there are no 11 elements of this set which disobey the conditions. Maybe you can give me a hint.

Kushagra Sahni - 5 years, 1 month ago

@Kushagra Sahni – See the Challenge Master note.

Calvin Lin Staff - 5 years, 1 month ago

Pick up minimum number to inequality

The answer is 11.

1 solution

Moderator note:

0 pending reports