|
New site? Maybe some day.
|
Suppose k+1 different numbers are chosen from the set (1,2...2k). Prove that there are two chosen numbers x and y which have the property that x is a multiple of y.
Prove that at any gathering of K people, there must be two people who shake the same number of hands(assume that two people don't shake hands more than once)
yup |
|
those are the easy problems...the hard ones will be posted if anyone even has an inkling of an idea as to what the fuck to do |
|
I'm going to take a crack at this... number 1:
Let's say k=2, that means 3 numbers must be chosen from the set (1,2,3,4).
Before we choose them, the following values of y would have x as a multiple:
if y=1 then x=2 OR x=3 OR x=4.
if y=2 then x=4.
So no matter if the three numbers we choose are 1,2,3 or 1,2,4 or 1,3,4 or 2,3,4, you can always find at least one pair in those three numbers where one can be x and one can be y according to the equations in the above two sentences.
Let's say k=3, that means 4 numbers must be chosen from the set (1,2,3,4,5,6):
if y=1 then x=2 OR x=3 OR x=4 OR x=5 OR x=6.
if y=2 then x=4 OR x=6.
if y=3 then x=6.
So no matter if the four numbers picked are 1,2,3,4 or 1,2,3,5 or 1,2,3,6, or 1,2,4,5 or 1,2,4,6 or 1,2,5,6 or 1,3,4,5 or 1,3,4,6 or 1,4,5,6, or 2,3,4,5 or 2,3,4,6 or 2,3,5,6 or 3,4,5,6 you can always find at least one pair in those four numbers where one can be x and one can be y according to the equations in the above three sentences.
As we can see, going over the lower numbers like 1 and 2 each time that we increase k is a bit redundant, since those scenarios have already been proven. Clearly, the only questionable area to be solved are the new numbers that appear at the top of the list everytime k is increased by one.
With that in mind: If you take k+1 numbers out of a list of consecutive integers from 1 to 2k, and try to take the highest numbers possible, you end up taking the top half of the list as well as the next lowest integer, which HAS to be k. Since k is always going to be half of 2k, there is always a scenario where x is a multiple of the y.
In otherwords, the sets we were looking at earlier could also be looked at as (1,k,3,2k), (1,2,k,4,5,2k), etc. No matter what k is, the fact that the list ends with 2k guarantees that one will always be a multiple of the other.
I don't know if I'm wording this as a "proof" by the standards her math professor may set, but this is the logic behind solving the problem. Hope it helps... |
|
I said fuck college and day jobs at the age of 20, whatever I do for a living will have to do with playing my guitar, and at 27, I've kept that vow. So I can afford a morning of being a nerd who solves other people's math problems. |
|
ok thats not cool. i cant even count to 5 and here is Shadow figuring out the key to the universe. |
|
Whoa - That is totally unfair. How am I supposed to concentrate on that math problem when you put up a picture of that adonis. He is the Cadillac of men. I'm all hot and bothered and distracted. Curse You! |
|
my sister says that when you get to larger sets that neither k or 1 could be picked, so that doesn't necessarily prove it all the time(your answer makes sense to me though, but she seems to think that there will be instances where it can't be proved that way every time) |
|
SacreligionNLI said: my sister says that when you get to larger sets that neither k or 1 could be picked |
Neither k nor 1 have to be picked for this to work, that's the whole point. In the second example above where k=3, I neglected to mention (2,4,5,6) as a possible chosen set; that right there is a set of numbers without k or 1, but in which you can find at least one pair where one can be x and one can be y. Even if you have neither k or 1, you can't avoid picking two numbers where one is the multiple of the other - and that's the heart of the proof being requested. Numbers increase at a constant rate, so no matter how big the set gets, these relationships never change; it's all relative.
|
|
Let me correct my wording in that third sentence: even if you have neither k or 1, there always exists at least one pair where one is the multiple of the other. The problem only calls for us to "prove that there are two chosen numbers" where one is the multiple of the other. |
|
haha and like i said...it makes sense to me
she had class last night and the guy didn't have the answers and said he'd post them later online...she's convinced that he doesn't know them and is waiting to see what the class comes up with |
|
he's just going to google and find this page.
I did this stuff in both descrete math and advanced computer algorithms. it succked. |
|
yeah the class is called "discrete math"
she's pissed because on her degree it won't say "combinatorics" it will say "discrete math" and that doesn't sound nearly as impressive
hooray for being a math teacher, or computer programmer |
|
Many professors are incompetent. That's why college is for suckers |
|
i just set hat picture as my background....fuckin hilarious
|
|
Shadow is actually The Midget that stole God's map of the universe.
Smart guy.
I'd like to think of myself as a fairly intelligent guy, but math.......ummmm......no. |
|
Fuck math, All you need to be a high school level viking is geography and metal shop |
|
Dankill said: Shadow is actually The Midget that stole God's map of the universe.
|
All five members?
|
|
SacreligionNLI said: yeah the class is called "discrete math"
she's pissed because on her degree it won't say "combinatorics" it will say "discrete math" and that doesn't sound nearly as impressive
|
It's only called that to prevent all the girls from flashing their tits.
|
|
"This is DISCRETE math, young lady!" |
|
...he said I was smart, not funny.
Seriously though, I actually don't get the midget reference from earlier, Dankill, somehow I don't think you were really talking about the local band... fill me in if you can.
|
|
I found an answer (its not mine, I take no credit):
"With there only being 2k numbers to select from and you have to select half of the numbers plus one, the smaller the k the easier to prove. if you have k = 4, annd you are selecting 5 numbers, start with 5,6,7,8 and that leaves 1 number left to select, with the remaining numbers being 1,2,3,4 which all of these numbers are multiples of one or more of the first numbers. if taking all odd numbers, you have 1 as one of your numbers which make it a multiple of all numbers already chosen. if you take all evens then you would have 2 which is a multiple of all numbers chosen. Its the +1 that makes you have at least two numbers, x and y that are multiples of each other. "
"Your assumption that two people don't shake hands more than once is your proof. Two people in any group K will have shook the same number of hands because two people have only shook hands once." |
|
what the fuck is wrong with these people? what use does combinamatrix have in life? |
|
Problem solving... Mostly people that use statistics and engineering use this kind of math. Your brother will be taking it soon. |
|
he'll probably ace it too. bastard. |
|
Not if I beat the crap out of him... He'll learn not to smarterur then we's! |
|
The midget reference is to the movie Time Bandits. (oddly enough, my friend was watching it just yesterday) |
[default homepage]
|
[print][ | 7:16:18am Apr 24,2024 load time 0.01634 secs/15 queries] | [search] | [refresh page] |
|