Intereting Posts

Proof of $k {n\choose k} = n {n-1 \choose k-1}$ using direct proof
What is the sum of $\sum\limits_{i=1}^{n}ip^i$?
Prime Appearances in Fibonacci Number Factorizations
Expanding problem solving skill
Locally continuously differentiable implies locally Lipschitz
Where DCT does not hold but Vitali convergence theorem does
How to prove that the converse of Lagrange's theorem is not true?
prove that $\text{rank}(AB)\ge\text{rank}(A)+\text{rank}(B)-n.$
Proof of a Ramanujan Integral
If $\int_A f\,dm = 0$ for all $A$ having some fixed measure $C$, then $f = 0$ almost everywhere
Evaluation of a continued fraction
Prove that $\int_{0}^{\infty}{1\over x^4+x^2+1}dx=\int_{0}^{\infty}{1\over x^8+x^4+1}dx$
Why is there more room in a square room than there is in a rectangular room when the perimeter is the same in both rooms?
Quasi-interactive proof on real numbers
A little more on $\sqrt{\cos\bigl(\tfrac{2\pi}7\bigr)}+\sqrt{\cos\bigl(\tfrac{4\pi}7\bigr)}+\sqrt{\cos\bigl(\tfrac{8\pi}7\bigr)}$

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5.

I tried with positive,negative numbers. Even, odd numbers etc but can’t find the solution. Any thoughts on what should the holes be ?

- How many different subsets of a $10$-element set are there where the subsets have at most $9$ elements?
- Possible ways to walk to school
- What is the purpose of implication in discrete mathematics?
- If two coins are flipped and one gets head, what is the probability that both get head?
- outer automorphisms of $S_6$
- Number of ways to put N indistinct objects into M indistinct boxes

- Relations of a~b iff b = ak^2
- How is Pascal's Triangle Important?
- Combinatorial proof that $\frac{({10!})!}{{10!}^{9!}}$ is an integer
- Prove that $(A-B) \cap (A-C) = A \cap (B \cup C)^c$ for any three sets A, B, C.
- Exponentiation in terms of Summation
- Why these two problems lead to same answers?
- Element of, subset of and empty sets
- Number of binary and constant-weight strings of length m which do not contain k consecutive zeros
- Creating a sequence that does not have an increasing or a decreasing sequence of length 3 from a set with 5 elements
- Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

“Divisible by 5” suggests considering modulo 5. Can you have 5 of them in the same residue class mod 5? If not, will you have at least 1 in each residue class? If so, notice that $0+1+2+3+4 = 10$.

As chubakueno pointed out, this isn’t a tight bound. We can easily cut it down by the following.

We can add 1 to each number and it doesn’t affect whether there are 5 of them with the property, so we can add until residue class 0 is the biggest.

If there are at least 3 “0”s, there cannot be both “1” and “4” or both “2” and “3”, giving at most $4+4+4 = 12$. In the other case there are at most 2 “0”s, and hence at most 2 in each residue class, giving at most 10 numbers in total. This gives an upper bound of 12, which still isn’t tight, and if we want we can push even further.

If there are at least 3 “0”s,

There cannot be:

“1,2,2” or “1,1,1,2”

“1,1,3” or “1,3,3,3”

“2,4,4” or “2,2,2,4”

“3,3,4” or “3,4,4,4”

Therefore in any pair of non-empty non-zero residue classes has at most 3 numbers in total

But as before for every non-zero residue class its complementary class must be empty

So there will be at most 2 non-empty non-zero residue classes

If there are 2 non-empty non-zero residue classes,

They have at most 3 numbers in total

If there is at most 1 non-empty residue class,

There are at most 4 numbers in it

Therefore there are at most $4+4 = 8$ numbers

If there are at most 2 “0”s,

If there is a non-zero residue class with 2 numbers in it,

We could make it such that it is either residue 1 or residue 2

If we have 2 “0”s and 2 “1”s,

There cannot be any “3” and there can be at most 1 “2” and 1 “4”

Therefore there are at most $2+2+1+1 = 6$ numbers

If we have 2 “0”s and 2 “2”s,

There cannot be any “1” and there can be at most 1 “3” and 1 “4”

Therefore there are at most $2+2+1+1 = 6$ numbers

If every non-zero residue class has at most 1 number in it,

There are at most $2+1+1+1+1 = 6$ numbers

Therefore in any case there are at most 6 numbers

Therefore there are at most 8 numbers and it is tight because of $(0,0,0,0,1,1,1,1)$

Since you don’t seem to be familiar with modular arithmetic I won’t use the language of congruences.

Every integer is of one of the following forms, $$ 5k, \ 5k + 1, 5k + 2, 5k + 3, 5k + 4; \; \text{for some integer $k$} $$

Now, if you pick $17$ integers by the pigeonhole principle either you must pick at least $1$ from each class or else you will have $5$ from the same class.

Say you picked at least $1$ from each class then they are of the form, $$5k_1, \ 5k_2 + 1, \ 5k_3 + 2, \ 5k_4 + 3, \ 5k_5 + 4$$ Now their sum is equal to $$5(k_1 + k_2 + k_3 + k_4 + k_5) + 10 \;\; \text{which is clearly divisible by $5$}$$

**OR**

You’ve picked $5$ integers from the same class and they are of the form $$5k_1 + i, \ 5k_2 + i, \ 5k_3 + i, \ 5k_4 + i, \ 5k_5 + i$$ where $i \in \{0,1,2,3,4\}$. It is easily seen that their sum too is divisible by $5$

- Partial vs Total Derivative (Basic)
- All finite abelian groups of order 1024
- Do different methods of calculating fractional derivatives have to be equal?
- Measure on the set of rationals
- Associated Prime Ideals in a Noetherian Ring; Exercise 6.4 in Matsumura
- Proving that $\lim_{h\to 0 } \frac{b^{h}-1}{h} = \ln{b}$
- Why concept of proper cone is important in convex optimization?
- Verification for the solution following differential equation!
- Infinite Series $\sum\limits_{k=1}^{\infty}\frac{k^n}{k!}$
- Is this inequality true? $ (x + y)^{\alpha} < x^{\alpha} + y^{\alpha} $, for positive $x$ & $y$, and for $0 < \alpha < 1$
- Binary operation (english) terminology
- When does the boundary have measure zero?
- Quaternions and spatial translations
- Pairwise Independent Random Variables that aren't Jointly Independent
- Get the equation of a circle when given 3 points