181. easy

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Mountains Drew
Messaggi: 59
Iscritto il: 25 mag 2013, 16:41
Località: Bregnano (Provincia di Como)

181. easy

Messaggio da Mountains Drew » 10 giu 2015, 15:06

Problema staffetta (facile)
Dati $p$ interi $a_1, ... , a_p$ con $p$ intero (non per forza primo), dimostrare che esiste un insieme $I \subseteq \{ 1,2, ..., p\}$ non vuoto tale che $ \sum\limits_{i\in I}a_i $ è multiplo di $p$

Bonus (per non lasciarlo troppo semplice)
Dati $n(p-1)+1$ vettori $a_1, ... , a_{n(p-1)+1}$ appartenenti a $\left(\mathbb{Z}/p\mathbb{Z}\right)^n$ con $p$ primo, dimostrare che esiste un insieme $I \subseteq \{1,2, ..., n(p-1)+1\}$ non vuoto tale che $ \sum\limits_{i\in I}a_i $ sia il vettore nullo
Ultima modifica di Mountains Drew il 13 giu 2015, 19:13, modificato 2 volte in totale.

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 181. easy

Messaggio da Drago96 » 10 giu 2015, 15:49

Nel vero problema direi che non è necessario $p$ primo...
E poi il bonus
Testo nascosto:
si fa anche con pigeonhole o serve un po' di artiglieria?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: 181. easy

Messaggio da cip999 » 10 giu 2015, 15:53

Il bonus con un cannone si uccide in fretta... :D
- E cosa c'è di peggio del suicidio?
- La vita.

Mountains Drew
Messaggi: 59
Iscritto il: 25 mag 2013, 16:41
Località: Bregnano (Provincia di Como)

Re: 181. easy

Messaggio da Mountains Drew » 13 giu 2015, 19:12

Avevo provato anche il punto b con pigeonhole e non ero riuscito... poi magari si fa, ma non così agilmente come il punto a.

Mentre col cannone è tutto più facile :D

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 181. easy

Messaggio da Drago96 » 17 lug 2015, 14:53

Suvvia, qualcuno risolva il problema facile!
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 181. easy

Messaggio da jordan » 19 lug 2015, 21:57

O uno è multiplo di $p$, o altrimenti abbiamo $p-1$ possibilità: consideriamo le $p$ somme $x_1+...+x_n$. O una è zero o due di essi sono uguali modulo $p$. Nell'ultimo caso, prendiamo la differenza tra queste due.

Ora, andiamo con quello un po' piu' difficile? [Se non sbaglio, anche quello è già stato sull'oliforum]
The only goal of science is the honor of the human spirit.

rizzo-5
Messaggi: 17
Iscritto il: 29 giu 2015, 13:43
Località: Verona

Re: 181. easy

Messaggio da rizzo-5 » 24 lug 2015, 12:11

Scusate la domanda stupida, ma con $\sum_{i\in I}a_i$ si intende che si possono anche sottrarre due $a_i$?

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: 181. easy

Messaggio da Enigmatico » 28 lug 2015, 01:10

In questo caso no, perché gli $a_{i}$ sono tutti interi positivi... Diciamo che il procedimenti di jordan è un modo per trovare gli $a_{i}$ utili, senza, però sottrarl. Ad un orario più decente se vuoi ti posto la soluzione estesa che mi ha mandato per pm dopo che ho avuto lo stesso tuo dubbio...

Rispondi