Suppose six numbers are chosen from 1..10. Show that these six numbers must include a pair a, b such that a|b?

Question

where a|b means a is a factor of b

Answer 1

Lots of good proofs. Here is my favorite -- because it can be generalized to much larger cases. Every positive integer can be written in the form: k*2^i, where k is odd, and i is a nonnegative integer.

Note that k*2^i divides k*2^j for any j
Just to help visualize the proof for the case n=5, the sets of k*2^i are:
1,2,4,8
3,6
5,10
7
9
Since there are only five of these sets, any set of six numbers from 1...10, must contain at least two from one set.

For every 1...2n, there is a set of n numbers such that no two divides each other. One such set is n+1, ..., 2n, since each number is larger than one half the size of each of the others.

Answer 2

Use proof by contradiction.

1 can't be included because it divides every number.

If 2 is included no other even number can be included or 2 will divide it. So 2 and all five odd numbers must be included. But if all the odd numbers are included then 3|9. So 2 can't be included.

If 3 is included then 6 and 9 cannot be, because 3|6 and 3|9. 1 and 2 have already been excluded so only six are left. Namely
3 4 5 7 8 10
But 4|8 so 3 can't be included.

If 4 is included then 8 cannot be because 4|8. Since 1 thru 3 are already excluded only six are left.
4 5 6 7 9 10
But 5|10 so 4 can't be included.

That leaves only
5 6 7 8 9 10
and 5|10

So no combination of six numbers of the set 1 thru 10 can be selected without a pair (a,b) where a|b.

Therefore there must exist a pair a, b where a|b.

Answer 3

Suppose that the set didn't contain such a pair. Then what? All numbers must be prime or 1. The set of such integers 1...10 is what? There's your answer.

Answer 4

1. Do you know a Mary Sue? => No, sorry I don't. 2. Your jet crashes in the middle of Antarctica, with you and the antagonist of your favorite book being the only survivors. What do you do? Seek shelter? Find food? What else? => Antagonist? O.O Uhh.. I think he would just play chess with me or something. He's quite boring most of the time... but deadly. *shivers* but then again, really ugly. (he's a demon) 3. You come home one day and to your shock, the entire house has been transformed into a pool! The antagonist is swimming in your flooded living room and you don't dare approach them because they've got two manticores on guard. Now what? => If my family's alright, then we'll just move to another house. Not wasting my own life with a couple of manticores. O.o On second thought... if only I had a gun I would kill those two manticores. YEAH! \m/ and the antagonist and I will go to an agreement. :D That's easy.. in some way.. 4. A question to the comic relief character - Think of the last thing you did. How would you react if you saw a man doing the same thing in a hotel lobby? => An old grown man... skateboarding? HAHA! XD I'd like to see them try. >:) 5. A question to the antagonist - im a realy gud riter, but I cant think of anytihng to rite about. can I hav ur iedeas? => I have no time with your writing games. Better go and ask somebody else to play. 6. Certain stories have quotes at the beginning. What is a quote that could go at the beginning of your story? => I can't think of any! >..< BQ: Could the you of today get along with the eight-year-old you? => Yeah maybe, but not much of a bonding time. I was more lively then, now I'm more like a dried, serious piece of work. I don't know, maybe we'll get along... BQ2: What is a writing-related pet peeve you have? => Specific sounds, like the door to y room keeps creaking and it's disturbing. Also, we have an internet shop just next to my room and they play loud music... again.. annoying... There's a lot and it's frustrating. -_- BQ3: Are you ambidextrous? => Woah! I had to look that one up. XD Okay. So.... no. I like my righty. I also read this, "Practicing or siding with both parties." so... agreement right? If it's agreement on two different things, then I would say depends. :D

Answer 5

My favorite uses the "pigeonhole principle." Break the 10 numbers into the following five sets.

{1, 7} {2, 6} {3, 9} {4, 8} {5, 10}

If the six chosen numbers contain both numbers in any set, they include an a & b with a | b.

The six numbers must contain both numbers of one set, since there are six numbers and only five sets. This is the pigeonhole principle: six pigeons (numbers chosen) going into five pigeoholes (carefully constructed sets) must have at least two pigeons in at least one pigeonhole.

Answer 6

1,2,3,4,5,6,7,8,9,10

I will attempt to disprove the statement
let us assume 1 is a lowest number chosen, but 1 is a factor for all the other 9 numbers.

if 2 is the lowest number in the list
4,6,8,10 are have 2 as a factor, the we only have 3,5,7,9 left, and that gives a total of 5 number when we need 6. (also 3 will disqualify 9)

if 3 is the lowest number in the list,
6,9 are factors, we have to pick 4,5,7,8,10 but 8 is a factor of 4, and 5 is a factor of 10

if 4 is the lowest number in the list, non-factors of 4 are
we have 5,6,7,9,10. but 5 is a factor of 10

if 5 is the lowest, non-factors are 6,7,8,9; we will not have enough numbers remaining.

we don't have to consider 6,7,8,9,10 because the set is too small to fulfill the 6 number requirements

Answer 7

there are 4 prime number from 1 to 10.
if we let the numbers drawn be {2,3,5,7,r,s}
r and s can either be a multiple of the prime number or it can be 1 which is a factor of the numbers 1 to 10.