15 numbers from 100

[did.gid]

Hello,
i don`t know how it`s possible, u can elect only 15 numbers from random gived full 100, the difference between two is dies 15 numbers and can be divided to 7? I post the german version also, its the origin. I must solve this task until tomorrow. Thanks

[FONT=&quot]German version: Kann man aus 100 beliebig gegebenen ganzen Zahlen stets 15 Zahlen so auswahlen,• da die Di erenz zweier beliebiger dieser 15 Zahlen durch 7 teilbar ist? (Beweis[/FONT]

 

[Ishuda]

Hello,
i don`t know how it`s possible, u can elect only 15 numbers from random gived full 100, the difference between two is dies 15 numbers and can be divided to 7? I post the german version also, its the origin. I must solve this task until tomorrow. Thanks

German version: Kann man aus 100 beliebig gegebenen ganzen Zahlen stets 15 Zahlen so auswahlen,• da die Di erenz zweier beliebiger dieser 15 Zahlen durch 7 teilbar ist? (Beweis

I'm not sure I understand the question, so I will restate to see if I am stating it correctly:
(1) You have a set of 100 integers [from 1 to 100?]
(2) you want to choose 15 integers, {a₁, a₂, a₃, ...., a₁₅} from the set of 100 numbers so that
___(i) for some j and k, a_j - a_k = 15, and for some m and n, a_j=7n and a_k =7m.

Is that a correct restatement of the problem?

 

[did.gid]

I'm not sure I understand the question, so I will restate to see if I am stating it correctly:
(1) You have a set of 100 integers [from 1 to 100?]
(2) you want to choose 15 integers, {a₁, a₂, a₃, ...., a₁₅} from the set of 100 numbers so that
___(i) for some j and k, a_j - a_k = 15, and for some m and n, a_j=7n and a_k =7m.

Is that a correct restatement of the problem?

No these numbers are random, it`s not said. And u elect these 15 neumbers and the difference between these 15 number can be divided to 7. For instance, 1 and 8, 8 and 22.
I think too, that we must prove that with some kind of example such yours.
Thanks
I have not understend too ,firstly, the task and that`s why it`s hard for comprehending for others

 

[did.gid]

I'm not sure I understand the question, so I will restate to see if I am stating it correctly:
(1) You have a set of 100 integers [from 1 to 100?]
(2) you want to choose 15 integers, {a₁, a₂, a₃, ...., a₁₅} from the set of 100 numbers so that
___(i) for some j and k, a_j - a_k = 15, and for some m and n, a_j=7n and a_k =7m.

Is that a correct restatement of the problem?

Maybe the u second solution is true but iam not certain.

 

[RalphD]

I can read German a little bit, but silly me got stuck on Di erenz which should have read Differenz. Anyways, I am quite sure the problem statement reads like this:

---

Given 100 random whole numbers, either prove that it is or is not possible to always select 15 of these numbers so that the difference between at least two of them is divisible by 7.

---

Note that "Differenz zweier beliebiger dieser 15 Zahlen" does not translate to "a difference of 15 of two of these numbers"; 15 belongs with "Zahlen", or "numbers". So instead, we have "the difference between two of these 15 numbers". Just thought I should point that out.

The problem is quite interesting. It is actually an optimization problem in disguise! The problem simply asks us to find a worst-case scenario (the maximum amount of whole numbers we can select so that none of them have a difference divisible by 7) and then asked to compare the given amount of 15 to the resulting amount. So let's get to it; first we select any number \(\displaystyle a_1\) to begin with. Then we select another number \(\displaystyle a_2\) with the constraint that \(\displaystyle a_1 - a_2 \not\equiv 0 \pmod{7}\). WLOG, assume that in fact, \(\displaystyle a_1 - a_2 \equiv 1 \pmod{7}\). Then we pick another number, \(\displaystyle a_3\). Now it is required that \(\displaystyle a_1 - a_3 \not\equiv 0 \pmod{7}\) and also that \(\displaystyle a_2 - a_3 \not\equiv 0 \pmod{7}\). Since we assumed \(\displaystyle a_2 - a_1 \equiv 1 \pmod{7}\), that means \(\displaystyle a_1 - a_3 \not\equiv 1 \pmod{7}\). Again, WLOG we can choose \(\displaystyle a_1 - a_3 \equiv 2 \pmod{7}\). When will we run out of options? Clearly, after we hit \(\displaystyle a_1 - a_7 \equiv 6 \pmod{7}\) in our current selection algorithm, we have no more options. The next step would be \(\displaystyle a_1 - a_8 \equiv 7 \pmod{7}\), but that simplifies to \(\displaystyle a_1 - a_8 \equiv 0 \pmod{7}\) which contradicts our constraint. Therefore, if we select 8 or more of such dice, we know that at least one of the numbers must be congruent to another one modulo 7. Since we have a whopping 15 numbers instead of just 8, we now know that not only must one number be congruent to another mod 7, but even that there is at least one triplet such that all of the three are congruent to one another. Hence we've concluded our proof: when we select 15 numbers out of 100 whole numbers randomly, we will always select them so that at least one pair has a difference divisible by 7.

 

[HallsofIvy]

select 15 of these numbers so that the difference between at least two of them is divisible by 7.

What is the point of the "15" here? The real question is whether, given a collection of 100 numbers, there always exist two whose difference is a multiple of 7. If that is true, then you could take any other 13 numbers to fill out the 15.

 

[RalphD]

What is the point of the "15" here? The real question is whether, given a collection of 100 numbers, there always exist two whose difference is a multiple of 7. If that is true, then you could take any other 13 numbers to fill out the 15.

Oops, that is indeed correct. I guess I read "two of the 15 random numbers" as "two of the 15 randomly chosen numbers" rather than "two of the 15 numbers that are themselves random". The preceding statement does in fact rule out the former interpretation.

Luckily the resulting problem is largely the same (although the general case is very slightly different), as now we simply compare 100 to 7 and conclude that it is also greater and therefore we can always pick our 15 numbers to satisfy the given conditions.