The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

Question along with attempt at answer

Hello there can someone help me with this problem please?

Let a1 (subscript for the number), a2, a3,a4,and a5 be any distinct positive integers. Show that there exists at least one subset of three of these integers whose sum is divisible by 3.(Use the fact that every integer can be written in one of the forms 3k, 3k+1, 3k+2, where k is an integer)

Attempted solution:

(3k+3k+1+3k+2)=9k+3 taking out common factor gives 3(3k+1)

Done! hmm!seems to easy what have I missed then?
Reply 1
Avatar for nuodai
nuodai
17
Original post by saizperez
Hello there can someone help me with this problem please?

Let a1 (subscript for the number), a2, a3,a4,and a5 be any distinct positive integers. Show that there exists at least one subset of three of these integers whose sum is divisible by 3.(Use the fact that every integer can be written in one of the forms 3k, 3k+1, 3k+2, where k is an integer)

Attempted solution:

(3k+3k+1+3k+2)=9k+3 taking out common factor gives 3(3k+1)

Done! hmm!seems to easy what have I missed then?

If the numbers were, say, 2, 5, 8, 11, 14, then none of them are of the form 3k3k or 3k+13k+1. You have to account for the possibility that maybe only one or two of the possibilities occur.

The idea is that you know that either all possibilities occur, in which case you can do that; or one possibility doesn't occur, in which case one of the other two appears 3 times (and you can show that therefore the sum of these 3 is divisible by 3).
Original post by saizperez
Hello there can someone help me with this problem please?

Let a1 (subscript for the number), a2, a3,a4,and a5 be any distinct positive integers. Show that there exists at least one subset of three of these integers whose sum is divisible by 3.(Use the fact that every integer can be written in one of the forms 3k, 3k+1, 3k+2, where k is an integer)

Attempted solution:

(3k+3k+1+3k+2)=9k+3 taking out common factor gives 3(3k+1)

Done! hmm!seems to easy what have I missed then?


You need a little more justification than that. There are two cases:

1. at least three of the integers can be written as [3k] OR [3k+1] OR [3k+2]
2. no three integers can be written as [3k] OR [3k+1] OR [3k+2] (which is the case you dealt with)

Edit: damn, beaten to it!
(edited 11 years ago)
Reply 3
Avatar for saizperez
saizperez
OP
6
Hi Nuodai

I'm assuming that I am restricted to using 3k, 3k+1 and 3k+2

By possibility I'm assuming there exists the option of using one of these 3 expression to designate an integer

If there is only one possibility I don't believe it works

However if there is 2 possibilities say 1,3 and 5 with k=1 therefore I would have 1+3k+3k+2=6k+3 works

Is this rigorous enough
Reply 4
Avatar for saizperez
saizperez
OP
6
Original post by nuodai
If the numbers were, say, 2, 5, 8, 11, 14, then none of them are of the form 3k3k or 3k+13k+1. You have to account for the possibility that maybe only one or two of the possibilities occur.

The idea is that you know that either all possibilities occur, in which case you can do that; or one possibility doesn't occur, in which case one of the other two appears 3 times (and you can show that therefore the sum of these 3 is divisible by 3).


what do you mean by the word possibility
Original post by saizperez
what do you mean by the word possibility


That it is possible for all five numbers to be of only one or two of the following forms: 3k, 3k+1, 3k+2. Your initial working does not consider this, it assumes that there are necessarily three integers amongst the five which can be written 3k, 3k+1, 3k+2.
Reply 6
Avatar for saizperez
saizperez
OP
6
Bon ben voyons si j`arrive a piger ce truc!

Scénario 1 il y`a --des 5 cinq chiffres--- au moins 3 integers (cependant n`oublions pas le fait que ---the three forms are represented in such circumstances) de la même forme soit 3k, soit 3k+1, soit 3k+2 alors (je sais, je sais ca depend des combinaisons qu`on fait bof...)

comme exemple 3k+3k+3k+3k+1+3k+2=15k+3 facteur commun de 3



Scénario 2 il y`a --dans l`ensemble des cinq chiffres---seulement 2 forms represented une desquelles sera répété another 3 fois.

comme exemple 3k+2 et 3k soit 3(3k+2)+2(3k)=9k+6+6k=15k+6 facteur en commun de 3
ou bien 3k et 3k+1

I believe this is the heart of the matter. Qu` est-ce que vous en pensez Merci:smile:
Original post by saizperez
Bon ben voyons si j`arrive a piger ce truc!

Scénario 1 il y`a --des 5 cinq chiffres--- au moins 3 integers (cependant n`oublions pas le fait que ---the three forms are represented in such circumstances) de la même forme soit 3k, soit 3k+1, soit 3k+2 alors (je sais, je sais ca depend des combinaisons qu`on fait bof...)

comme exemple 3k+3k+3k+3k+1+3k+2=15k+3 facteur commun de 3



Scénario 2 il y`a --dans l`ensemble des cinq chiffres---seulement 2 forms represented une desquelles sera répété another 3 fois.

comme exemple 3k+2 et 3k soit 3(3k+2)+2(3k)=9k+6+6k=15k+6 facteur en commun de 3
ou bien 3k et 3k+1

I believe this is the heart of the matter. Qu` est-ce que vous en pensez Merci:smile:


Why are some of your sentences multi-lingual? :curious:

To answer your post:

Non, tes deux scénarios sont équivalents. Qu'il y ait 3 nombres, 4 nombres, ou 5 nombres de la même forme, ça revient au même: car trois nombres de la même forme suffisent pour que leur somme soit un multiple de 3. Tant que tu en as 3, peu importe ce que sont les autres nombres. Donc:

Scénario 1: au moins 3 nombres de la même forme.

- s'ils sont de la forme 3k3k leur somme donne: 3k+3k′+3k′′=3(k+k′+k′′)3k+3k'+3k''=3(k+k'+k'')
- s'ils sont de la forme 3k+13k+1 leur somme donne: 3k+1+3k′+1+3k′′+1=3(k+k′+k′′+1)3k+1+3k'+1+3k''+1=3(k+k'+k''+1)
- s'ils sont de la forme 3k+23k+2 leur somme donne: 3k+2+3k′+2+3k′′+2=3(k+k′+k′′+2)3k+2+3k'+2+3k''+2=3(k+k'+k''+2)

Scénario 2: il n'existe pas 3 nombres de la même forme. Ceci implique forcément qu'il y en a 2 d'une forme, 2 d'une autre, et 1 de la dernière. En prenant un nombre de chaque forme tu as:

3k+3k′+1+3k′′+2=3(k+k′+k′′+1)3k+3k'+1+3k''+2=3(k+k'+k''+1)

Et là, et seulement là, as tu épuisé tous les cas possibles et le résultat est donc prouvé.

Translation:

Spoiler

(edited 11 years ago)
Reply 8
Avatar for nuodai
nuodai
17
Je voudrais vous rappeler qu'il y a un règlement qui dit que tous les messages doivent être écrits en anglais ou avec une traduction en anglais! Pour le moment ça va mais la prochaine fois je serai obligé de vous... punir, ou quelque chose comme ça.

I should remind you guys that there's a rule that says posts must be in English (or with a translation provided if not)! It's fine for now but next time I'll be obliged to give you points.
(edited 11 years ago)
Original post by nuodai
Je voudrais vous rappeler qu'il y a un règlement qui dit que tous les messages doivent être écrits en anglais ou avec une traduction en anglais! Pour le moment ça va mais la prochaine fois je serai obligé de vous... punir, ou quelque chose comme ça.

I should remind you guys that there's a rule that says posts must be in English (or with a translation provided if not)! It's fine for now but next time I'll be obliged to give you points.


Sorry about that, I wasn't aware. The OP gave the impression he was more comfortable with French so I went with it to help him out! :smile:

Edit: translated! :wink: (into not-so-good English)
(edited 11 years ago)
How come everyone can speak French! :biggrin:
Original post by Brit_Miller
How come everyone can speak French! :biggrin:


Because it's... the language of reason! :cool: :tongue:
Original post by Lord of the Flies
Because it's... the language of reason! :cool: :tongue:


Well that's one description of it. :biggrin:
Reply 13
Avatar for nuodai
nuodai
17
Original post by Brit_Miller
How come everyone can speak French! :biggrin:

Well there's this group of people, you might know them as "the French", who are born in a country called "France", and curiously this strange country speaks a language distinct from our own: it's called "French"! And occasionally, when two people who are both members of this group "the French" meet, they will communicate in this bizarre language as a means of communication. Of course, it's not a real language, but a means of skewing the truth and making it intractable to us speakers of the Common Tongue.

(As for me, I just learnt lots of French in school and uni, and worked in France once, and stuff.)
Original post by nuodai
Of course, it's not a real language, but a means of skewing the truth and making it intractable to us speakers of the Common Tongue.


How dare you spew such venom?!
Reply 15
Avatar for nuodai
nuodai
17
Original post by Lord of the Flies
How dare you spew such venom?!


Car cela donne l'impression que la langue français est une methode sophistiquée de duper la foule, et donc on va penser que c'est très impressionant.

Because that gives the impression that it's better to focus your attention on learning maths than French.
Original post by nuodai
Well there's this group of people, you might know them as "the French", who are born in a country called "France", and curiously this strange country speaks a language distinct from our own: it's called "French"! And occasionally, when two people who are both members of this group "the French" meet, they will communicate in this bizarre language as a means of communication. Of course, it's not a real language, but a means of skewing the truth and making it intractable to us speakers of the Common Tongue.

(As for me, I just learnt lots of French in school and uni, and worked in France once, and stuff.)


Thanks for the explanation, I just thought it was a myth.
Reply 17
Avatar for saizperez
saizperez
OP
6
Um, cough, cough, passively being facetious...

I'm Canadian EH and I'm sorry for going back and forth between languages during my attempts to understand Ontario Grade 12 Math. I guess it was the asperger's talking. You know when the guv'nor was reprimanding the honourable LOF over language, it was like I was in Montreal again being reprimanded for speaking English. Felt just like home.

RE LOF last explanation, holy mackinaw I'm not too bright am i?
Reply 18
Avatar for saizperez
saizperez
OP
6
Thanks :smile: LOF

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you