Given any six natural numbers, show that there must be two, say m and n, with difference
m − n divisible by 5.
On first look it seems like a pigeonhole principal question, but im not really sure how to structure it if it is, I have trivial part completed > "If all the elements in the set are the same then its trivial, the difference between any combination of numbers is x-x = 0 which is always divisible by 5"
thanks in advance guys
bump
>>8431758
>consider all numbers mod 5
>apply pigeonhole principle
>>8431809
I know that has something to do with it but when it comes to applinyg ph principal i go potato, can you walk me through this
>>8431832
Hmm I think this is a pigeonhole principle question.
Look at all the numbers mod 5. By the PHP, now, at least two will have the same value (6 things, but 5 boxes).
Subtract those two things to get they're 0 mod 5.
>>8431848
>Hmm I think this is a pigeonhole principle question.
yes I do too (stated in op)
>Look at all the numbers mod 5. By the PHP, now, at least two will have the same value (6 things, but 5 boxes).
You just skipped a bunch of stuff, this is what I dont get how do you *know* that when you subtract two things in the set at least one of them will be mod 5
>(6 things, but 5 boxes).
??? I dont get how this is relevant
What im seeing now is
{x1, x2, x3, x4, x5, x6}
but how do I know that subtracting one of the combinations will be mod 5 it makes no sense to me how you could ever deduce that
>>8431857
I'm going to use Z/5Z+j to denote the set (more formally, the equivalence class) of integers congruent to j mod 5, where j=0,1,2,3,4. (Disclaimer: I'm a statsfag so this is probably butchered notation but it should get the point across.)
By definition, if any two numbers m,n are in the same set, then their difference m-n is divisible by 5.
Now you have six natural numbers x1,...,x6 and five equivalence classes. You should be able to take it from here.
>>8431869
>>8431869
Ohh... thanks
do you have any tips on how to think better, I always seem to come across things that are very simple but for some reason I never think of the correct solution? Or is there no way to think better if youre not genetically predisposed for maths?
>>8431877
There's no genetical predisposition for maths because maths are a human invention, anon.
There's no way nature selects for it in any meaningful way.
>>8431758
As other posters have laid out, you can frame this in terms of the integers modulo 5. Here's an alternative that's equivalent, but it doesn't require any of that notation. In fact, in some sense it's literally the same argument, but I think it might be easier to see.
Basically, think about the possible remainders when dividing each number by 5.
In more detail: you have 5 possible remainders (what are they?) but 6 numbers. Now apply the pigeonhole principle to these 6 numbers and the 5 remainders to get 2 numbers, say m and n, with the same remainder. Then m-n will be divisible by 5 (you should explain why this is true).
>>8431857
But I didn't skip a bunch of stuff.
The PHP says if you have n things in m boxes, with n>m, then at least one box will contain at least two items.
So: look at the numbers a,b,c,d,e,f mod 5. If you look at their remainders mod 5, you'll have six numbers between 0 and 4. But there are only 5 unique numbers. This means there is a repeat among them.
Our things: numbers (6 of them)
Our boxes: the unique numbers 0,1,2,3,4 representing the possible remainders when divided by 5.
So: we have more things than boxes, so by the PHP, one box has two things in it: ie there are two numbers whose remainder is the same when divided by 5.
And that's the answer.
Example:
3, 7, 8, 21,45,92.
Look at everything mod 5:
3,2,3,1,0,2
There are only 5 possible unique remainders mod 5:
0,1,2,3,4
But since we have 6 numbers, there's got to be at least one repeat. In our example, we see 2: 2 and 3.
And now you see: 8-3 is divisible by 5, and 92-7 is divisible by 5.
>>8431900
maybe the choice of words wasnt the best, what I meant was why can some people just think of abstract things to solve stuff that others normally wont? Like, the average human may be more inclined to brute force problems where as smart people can simplify the problem set using their intelligence, how do people just think of certain things to solve stuff? Think of proofs for example, theres no laid out bread and butter way to do things but for some reason people have a "gut feeling" of doing stuff while I just sit here wtfing at the arbitrarity of proofs
>>8431908
Yup that is a very intuitive understanding of it I get it now
>>8431915
>1915 ▶
>>>8431857 (You)
yea sorry I get it now but the explaination you said is what i wnated
>>8431900
>Implying that maths are a human invention.
Is this turning to one of those threads again?
array['x'] = ( 1,2,3,4,5,6 );
so if you take one number out, you must get in number that is already divisible by the five, if you you can give it in sequence
x + y*z, but it's not any helpful, because y in case of divisionarity by 5 is just 4 numbers you can choose, but you must do that twice, so the number you are choosing is divisionable by another in array.
>>8431917
There is no simple answer to the first part of what you said.
However, trust me when I say this line of thought is harmful. We don't know any way of quantifying intelligence nor any way of increasing it.
So don't worry about whether or not you're naturally able to think of abstract stuff to solve problems.
Worry more about learning, seeing problems, solving them, and remembering them. Agter this problem, for example, the next PHP problem will be easier. Make sure you really understand the material you're learning.
As far as problem solving goes, there are general principles to follow but nothing specific will allow you to solve problems better. Just do more and understand why it worked... And like Descartes said, every problem he solved became a rule for a later problem.
>>8431927
ok I guess youre right... its hard to not get angry and depressed sometimes when you see others do easily what you cant figure out on your own
>>8431937
Absolutely. But try not to get caught up on individual problems. Now that you know this, you know not only the PHP better but also how to go about actually starting similar problems.