Question

URGENTLY NEEDS HELP!
prove that any set of seven distinct integers has integers x and y whose sum or difference is divisible by 10

Answer 1

@zepdrix @thomaster

Answer 2

for holes you may consider the remainders modulo 10

Answer 3

```
0
1,9
2,8
3,7
4,6
5
```

Answer 4

Notice that \((10k+r_1) - (10l+r_2)\) is divisible by \(10\) when \(r_1 = r_2\), and \((10k+r_1) + (10l+r_2)\) is divisible by \(10\) when \(r_1 + r_2 = 10\)

Answer 5

6 holes and 7 pigeons

By pigeonhole principle, one hole must contain at least two pigeons.

Answer 6

another question, "If we are to take three distinct integers, then we have x and y such that y(x^3)-x(y^3) is divisible by 10" how to prove it?

Answer 7

''Pigeonhole principle'' ALWAYS cracks me up xD

Answer 8

please help..

Answer 9

maybe start by factoring the given expression and consider the product in modulo 10

Answer 10

i considered the factor already and i don't know what to do next.. TT_TT

Answer 11

same here i feel a bit stuck..

Answer 12

To conclude, we want to have a situation in which we get "2 holes and 3 pigeons"

Answer 13

consider Z sub 5... if one of the elements chosen is congruent to 0 mod 5 then, were done. supposing not, then we can partition {1,2,3,4} in such a way that the sum of the elemnts that are in the same subset is congruent to 0 mod 5...

Answer 14

is that okay?

Answer 15

I think that's okay, but you might have to demonstrate that you can always sum the subsets to be congruent to 0 mod 5

Answer 16

I mean, case-by-case, unless you have some theorems or earlier results to work with

Answer 17

that looks like a good try but we want to show that there always exist two integers among 3 distinct integers such that the given expression is congruent to 0 mod 10 right

Answer 18

Yes, that might work well. I think the motivation to use 5 is because it's prime so you have some special properties to work with

Answer 19

if the sum doesn't work, (continuing the proof i presented above), then it mean the element taken from the same subset is equal. thus making (x-y) congruent to 0 mod 5. since we always have y(x^3)- x(y^3) even (it is equal to xy(x+y)(x-y) s.t. either x, y, or x+y is even)..

Answer 20

sorry, i'm still hoping i could finish the proof (somehow ._.)

Answer 21

I see your proof works perfectly! just show that you're actually using pigeonhole principle by explicitly stating number of pigeonholes and pigeons

Answer 22

\[y(x^3)-x(y^3) = xy(x+y)(x-y)\]It is easy to see that \(2|xy(x+y)\) for all integers \(x\) and \(y\).


We're done if either \(x\) or \(y\) is divisible by \(5\). If not, we show that \(5|(x-y)\) by partitioning the remainders into two bins :
```
1,4
2,3
```
2 holes and 3 pigeons
one hole must contain at least 2 pigeons.