Problema:
Dati 1000 interi qualsiasi,
dimostrare che ne esistono almeno 2 la cui somma o la cui differenza è uguale ad un multiplo di 1997.
Come si risolve col pigeonhole?
Vi ringrazio.
Sticky
aiuto sull'applicazione del pigeonhole
I mille interi sono i piccioni. Consideriamo ora le classi di congruenza modulo 1997. Esse sono 1997, poichè sono pari ai resti della divisione per 1997 e sono tutti gli inter che vanno da 0 a 1996. Accoppiamo ora le classi di congruenza da 1 a 1996 di modo che la somma dei rispettivi resti della divisione per 1997 dia 1997. Uniamo quindi le classi di congrenza 1 e 1996, 2 e 1995, 3 e 1994,...,998 e 999. Abbiamo ottenuto da queste unioni 998 insiemi e, considerando anche la classe di congruenza 0 modulo 17, gli insiemi in cui inserire i mille interi sono in tutto 999. Quindi almeno due devono finire nello stesso insieme...si vede facilmente che o la somma o la differenza è multipla di 1997...credo di essermi incasinato un po'...ma più o meno ci siamo
"È più difficile disintegrare un pregiudizio che un atomo." (A. Einstein)
Cesco ha scritto: considerando anche la classe di congruenza 0 modulo 17
Ma no che porta sfortuna! almeno spara un altro numero
[b]Membro Club Nostalgici[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
Infatti non ci credo
proviamo...quanto fa $ \frac{51}{3} $?
proviamo...quanto fa $ \frac{51}{3} $?
[b]Membro Club Nostalgici[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]