Proof related to a subset of a set.

Hi,

I have a problem that I am having trouble starting.


Let S(n) be the set {1,2,3,4,,2n-1,2n}. Let A be any subset of S(n) containing (n+1) elements. Show that there exist elements a and b in A such that a|b. and S(n) for all values of n.


I have to show the result is true for for a and b in A and for all values of n in S(n)...if a and b is in A, then it is also in S(n)...this proof would be through mathematical induction.

S(1) ={1,2}
S(2) ={1,2,3,4}
S(3)={1,2,3,4,5,6,}
S(4)={1,2,3,4,5,6,7,8}
S(5)={1,2,3,4,5,6,7,8,9,10}
and so on...

A start would be much appreciated.

Thanks,

Joe

Do you have the ‘pigeon hole principle’ to work with?

Yes, by induction or pigeon hole principle....but how would the pigeon hole principle relate to these sets?

This may to too advanced a proof for you. However this is a standard pigeon hole problem.
To get some notation: \(\displaystyle S(n) = \left\{ {1,2,3, \cdots ,2n - 1,2n} \right\}\quad \& \quad O = \left\{ {1,3, \cdots ,2n - 1} \right\}.\) Note that the set \(\displaystyle O\) has \(\displaystyle n\) elements in it.

Here is some background information you need to know. Each element \(\displaystyle k \in S\) can be written as \(\displaystyle k = 2^x Q\quad ,\quad Q \in O\), that is a power of 2 times some odd number.

Now define \(\displaystyle f:A \to O\) by \(\displaystyle f(k) = Q\). Now we have \(\displaystyle n + 1\) pigeons and \(\displaystyle n\) pigeons-holes.

Can you finish it?

I am having trouble understanding the proof you are using.

Can you please explain how this proof shows n+1 pigeons and n pigeon holes?

First, what is set O?

From what you stated, k exists within S(n) and Q exists within O. Also, k = 2^X *Q. And Q is a power of an odd number times 2...2(2n-1)?? so would k be equal to a power of some odd number times two, 2(2n-1), which exists within O? isn't 2 times an odd number an even number?

I am also confused with defining f and its purpose.
And also how does this relate to a | b?

Sorry, but the only background I have with this is some set theory and the basic pigeon hole principle.

Thanks for your time,

Joe

There are \(\displaystyle n + 1\) elements in \(\displaystyle A\) each of which is assigned to some element of \(\displaystyle O\). Thus some element of \(\displaystyle O\) has two pre-images in \(\displaystyle A\).
Now if \(\displaystyle k > j\quad \Rightarrow \quad 2^j |2^k\)

If you are needing more help than that, then you are asking for someone to do your work for you. There are at least two people who come by here and give completely worked out, ready to hand in solutions. I am not one of them! One of those is a Jr. College instructor who I doubt understands this problem and the other is a current mathematics major who actually learns something from doing these problems.

My point is, of course, you need to find on your own a solution to this.
I have handed you all the necessary information.
If you cannot do it for yourself, you do not deserve to have it done for you.

Thanks.

Though, I was not looking to get the solution handed to me. Rather, just a teacher.

Thanks for you help!

- greatly appreciated.

JoeSal said:

Thanks.

Though, I was not looking to get the solution handed to me. Rather, just a teacher.

Thanks for you help!

- greatly appreciated.

Click to expand...

Joe, I'll try to explain what pka said in slightly simpler terms. (pka am I that math major? lol)

The function f from the subset A of S(n) to O sends from a set with n+1 elements to a set with n elements... Since every number in A has an image, at least one image is not unique. Also, every element in S(n) can be written as a power of 2 times an odd number from S(n):

If the number (k) from S(n) in question is odd, it is just 2⁰k, which is in O. If it is even: k=2j, and if j is even j=2i, etc until you get to 2 times some odd number, then just add the power of 2's times that odd number. For example: 56 = 2*(2*(2*7))) = 2³*7, where 7 would be in O.

This gives us a working example for the function we needed i.e. for any w in A, w = 2^kq for some q in O. So f(w)=q. By the pigeonhole principle, there must be some number in O that has two preimages from A (i.e. f is not "one-to-one"). So this tells us for some number \(\displaystyle a\) in O there are two numbers \(\displaystyle b\) and \(\displaystyle c\) in A such that \(\displaystyle f(b)=a=f(c)\)

Thats pretty much where pka left off, and it is not hard to skip to the end from here.

thanks for your reply...no, I cannot finish your proof. it is too advanced for me. Can you explain at a lower level? I am a sophomore taking a discrete mathematics class. I am familiar with basic set theory and the pigeon hold principle. I would appreciate any help.

JoeSal said:

thanks for your reply...no, I cannot finish your proof. it is too advanced for me. Can you explain at a lower level? I am a sophomore taking a discrete mathematics class. I am familiar with basic set theory and the pigeon hold principle. I would appreciate any help.

Click to expand...

The biggest part of this proof is that every number \(\displaystyle a\) in A can be written as \(\displaystyle 2^k(b)\) where \(\displaystyle b\) is ODD.

S(n)={1:2n}
O={1,...,2n-1}
A={some set with n+1 umbers from S(n)}

A has n+1 numbers... right? O has n numbers... right?

Since EVERY number in A can be written as 2*2*..*2(b) where b is ODD, and there are n+1 numbers in A, there must be AT LEAST TWO numbers in A that have a DIFFERENT power of 2 times THE SAME odd number.

For example in S(6), O={1,3,5,7,9,11}, A={3,4,5,6,7,11,12} we have: 6=\(\displaystyle 2^1*3\) and 12=\(\displaystyle 2^2*3\). Notice they have different powers of 2 but the same odd multiple.

The proof should follow from this, but if I said anymore I'd be giving you the answer. I hope that was clearer.

Thanks a lot.

Sorry about the last post that you just responded to, I attempted to post that earlier in the day and for some reason it got posted a couple hours later...after your first post. But anyway, you made it clear with both of your posts, that the pigeon hole principle says that there has to be 2 values in S for 1 value in O.


ie

10 = 2^1 * 5.....where 5 is odd and in O.
20 = 2^2 * 5.....where 5 is odd and in O.