Prove that if any 14 integers from 1 to 25 are chosen without repetition, then o

Question

Prove that if any 14 integers from 1 to 25 are chosen without repetition, then one of them is a multiple of the other. Could the number of integers chosen be less than 14?

Explanation / Answer

Proof by contradiction Let us assume given statement is not true => there is case where we can choose 14 numbers from 1 to 25 such that no one is a multiple of no other number => let x be the number of numbers choosen from first 13 numbers (from 1 to 13) let y be the number of numbers choosen from 14 to 25 we know that x+y = 14 =>since there are no multiples of each other y should contain atmost 13-x elements otherwise by pigeon hole principle there is number in range (14 to 25) which is twice of a number in range (1 to 13) so maximum value of x+y is x+13-x =13 but x+y = 14 Hence a contradiction So given statement is true

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.