Pigeonhole e discesa infinita

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Avatar utente
Franchifis
Messaggi: 149
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Pigeonhole e discesa infinita

Messaggio da Franchifis » 16 mar 2005, 21:55

Che cosa sono il pigeonhole e la discesa infinita? In che tipo di problemi e' opportuno utilizzarli? Se ne puo' fare a meno o sono indispensabili per certi problemi? Grazie!!!

EvaristeG
Site Admin
Messaggi: 4789
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 17 mar 2005, 04:33

Dunque ...
non sarò granchè formale, ma spero almeno di essere chiaro :

1) il pigeonhole (o principio dei cassetti) dice sostanzialmente questo : se hai $ k $ cassetti e $ k+1 $ oggetti da disporre all'interno dei detti cassetti, vi sarà almeno un cassetto che contiene 2 oggetti.

Vi sono varianti infinite di questo principio, ad esempio si possono considerare $ nk+1 $ oggetti e dire che ve ne saranno $ n+1 $ in almeno un cassetto.

Di solito, questo principio si usa dove bisogna "contare" qualcosa o studiare le possibili configurazioni di un qualche sistema. Ad esempio :

*) scelti 7 numeri distinti nell'insieme {1,2, ... ,11} ve ne sono sempre due tra essi la cui somma fa 12.

sol : in questo caso gli oggetti sono i 7 numeri tra gli 11; costruiamo i cassetti :
{1,11} {2,10} {3,9} {4,8} {5,7} {6}. Siccome sono 6 cassetti e 7 oggetti, ve ne sarà uno che conterrà 2 oggetti e dunque vi sarà uno dei primi 5 insiemi (quelli con 2 elementi), perciò tra i 7 vi saranno due numeri che sommano a 12.

*) scelti comunque 5 punti in un quadrato di lato 1, ve ne sono due che distano meno di $ \sqrt{2}/2 $.

sol : gli oggetti sono i 5 punti, i cassetti ce li creiamo dividendo il quadrato in 4 quadrati di lato 1/2; due dei 5 punti saranno nello stesso quadratino e quindi disteranno meno della diagonale che è appunto $ \sqrt{2}/2 $.

2) la discesa infinita è uno strumento molto usato nelle dimostrazioni per assurdo che si può enunciare così : non esiste una successione infinita strettamente decrescente di numeri naturali.

ad esempio : dimostriamo che $ \sqrt{2} $ non è un numero razionale.

dim : supponiamo PER ASSURDO che $ \sqrt{2}=p/q $ con p,q numeri naturali. Eleviamo al quadrato entrambi i membri ottenendo :
$ 2= p^2/q^2 $ ovvero $ 2q^2=p^2 $
quindi 2|p, ovvero 4|p², quindi possiamo dividere per 2 l'espressione ottenendo
$ q^2=2p_1^2 $
dove $ p_1=p/2 $ è ancora intero; da questo si ricava che 2|q e dunque che 4|q², quindi $ q_1=q/2 $ è un intero e possiamo scrivere
$ 2q_1^2=p_1^2 $
ovvero $ 2=p_1^2/q_1^2 $
(di solito ci si ferma e si dice : ASSURDO! ma vediamo perchè ...)
Iterando il procedimento possiamo costruire una successione :
$ (p,q) \to (p_1,q_1) \to (p_2,q_2) \to \ldots \to (p_n, q_n) \to \ldots $
dove $ p_n=p_{n-1}/2 \quad q_n=q_{n-1}/2 $ e dunque $ p_n<p_{n-1}\quad q_n<q_{n-1} $ e tutti i numeri coinvolti sono naturali.
Ma questa è una discesa infinita e quindi è un assurdo. Dunque, la radice quadrata di 2 è irrazionale.

Un altro esempio di applicazione può essere il dimostrare che $ x^3+y^3=z^3 $ non ha soluzioni tra i numeri naturali a parte le terne banali (contento, Hit?), ma questo è più difficile...

Spero di esserti stato utile
Ultima modifica di EvaristeG il 17 mar 2005, 19:18, modificato 2 volte in totale.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 17 mar 2005, 08:37

A proposito della discesa infinita...

Non so quanti di voi si ricordano la lista di Combinatoria e Algebra che Evariste ci propose qualche tempo fa (e di cui io, molto truffaldinamente, mi sono appropriato, seminando brutti voti a destra e a manca). C'era un problema che suonava più o meno così: ci sono tanti sacchi con tante biglie dentro; eliminandone uno si possono dividere i sacchi in modo da avere lo stesso numero di biglie...

QUEL problema, ad esempio, si può risolvere con la discesa infinita.

Un saluto.

M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 17 mar 2005, 10:29

EvaristeG ha scritto: Un altro esempio di applicazione può essere il dimostrare che $ x^3+y^3=z^3 $ non ha soluzioni tra i numeri naturali a parte la terna nulla, ma questo è più difficile...
Ehmmm... Le triple (1,0,1) e (0,1,1) dov'è che te le sei dimenticate? :roll: :wink: :mrgreen:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

No, per niente...

Messaggio da HiTLeuLeR » 17 mar 2005, 11:50

EvaristeG ha scritto:Un altro esempio di applicazione può essere il dimostrare che $ x^3+y^3=z^3 $ non ha soluzioni tra i numeri naturali a parte le quattro terne banali (contento, Hit?), ma questo è più difficile...
Coff coff... E mo' come te lo dico? Uhmmm... No, mi spiace, non sono affatto contento!!! :(

Avatar utente
Franchifis
Messaggi: 149
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da Franchifis » 17 mar 2005, 18:18

Wow, non pensavo che con il pigeonhole si potesse effettivamente dimostrare qualcosa. Dovete ammettere che quando lo si enuncia sembra un po'... banale, come una presa in giro. E invece quel problema sul quadrato l'avevo visto tempo fa e non fui in grado di risolverlo...

[Cancellato il messaggio doppio. M.]

EvaristeG
Site Admin
Messaggi: 4789
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 17 mar 2005, 19:29

Non è il caso di dirlo due volte ... ;)

Cmq, ecco :

Scelti comunque n+1 interi tra 1 e 2n ve ne sono due tali che uno divide l'altro.

Marco si allena nella corsa per 44 giorni almeno una volta al giorno, per un totale di 70 volte. Dimostrare che esiste un periodo di giorni consecutivi durante i quali si allena esattamente 17 volte.

In una griglia infinita i nodi sono colorati di due colori; dimostrare che esistono due linee verticali e due linee orizzontali tali che i 4 nodi in cui si intersecano sono tutti dello stesso colore.

Vi sono 51 punti nel quadrato di lato 1; dimostrare che ne esistono 3 che possono essere ricoperti da un cerchio di raggio 1/7.

Dimostrare che comunque presi 52 interi positivi, ve ne sono due, m e n, tali che m+n oppure m-n \`e multiplo di 100.
Bonus question : Rimane vero per 51 interi positivi?

Comunque presi 8 numeri interi ve ne sono due tali che la loro differenza \'e un multiplo di 7.

(da qui in poi difficili!!!)

Presi 5 punti su una sfera dimostrare che 4 di essi stanno in una semisfera chiusa (ovvero compreso l'equatore associato).

Poniamo dei numeri interi in una griglia 10x10, di modo che due numeri vicini (in caselle con un lato comune) non differiscano per pi\`u di di 5. Dimostrare che nella griglia vi sono due interi uguali

I numeri 1, 2, ... , 9 sono divisi in due gruppi. Dimostrare che il prodotto dei numeri che stanno in uno dei due gruppi supera 71.

Questi sono esercizi (più o meno standard) sul pigeonhole.
Per la discesa infinita, proverò a cercare qlcs, ma non me ne vengono in mente di facili, quindi non so se riuscirò.

Buona soluzione.

PS : non garantisco pronta correzione, ma ci sono molti altri validissimi che possono dire se una soluzione sia esatta o meno.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Oh, oh...

Messaggio da HiTLeuLeR » 17 mar 2005, 22:13

EvaristeG ha scritto:Un altro esempio di applicazione può essere il dimostrare che $ x^3+y^3=z^3 $ non ha soluzioni tra i numeri naturali a parte le terne banali (contento, Hit?), ma questo è più difficile...
Adesso sì, grazie! E per dimostrartelo, risolvo uno dei tuoi problemi: non preoccuparti, non intendo rubare il mestiere ai giovani problem solvers. E per provarti la mia buona fede, mi butto a capofitto sul "difficile" (ipsum dixisse!!! :shock:):
Evariste ha scritto:I numeri 1, 2, ... , 9 sono divisi in due gruppi. Dimostrare che il prodotto dei numeri che stanno in uno dei due gruppi supera 71.
Posto $ \mathcal{S} := \{1, 2, \ldots, 9\} $, siano $ G_1, G_2\subseteq \mathcal{S} $ tali che: $ G_1 \cap G_2 = \emptyset $ e $ G_1 \cup G_2 = \mathcal{S} $. E allora: $ |G_1| + |G_2| = |\mathcal{S}| = 9 $, sicché uno almeno fra $ G_1 $ e $ G_2 $ contiene necessariamente un numero di elementi distinti $ \geq 5 $, e detto $ P $ il prodotto di questi stessi elementi, banalmente risulta che: $ P \geq 5! > 71 $. Di qui l'asserto, q.e.d.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Perché snobbate i problemi di Evariste?

Messaggio da HiTLeuLeR » 23 mar 2005, 19:14

Pare che qui la gente non apprezzi molto i tuoi problemi, Evariste!!! :shock: A me piacciono tanto, invece... :mrgreen:
EvaristeG ha scritto:Comunque presi 8 numeri interi ve ne sono due tali che la loro differenza è un multiplo di 7.
Fissato $ n\in\mathbb{N}_0 $, siano $ a_1, a_2, \ldots, a_{n+1}\in\mathbb{Z} $. Intendiamo provare che esistono allora $ i, j\in\{1,2,\ldots, n+1\} $, con $ i \neq j $, tali che: $ a_i \equiv a_j \bmod n $. Ragionando per assurdo, neghiamo la tesi e ammettiamo viceversa che siano determinati $ n+1 $ interi $ a_1, a_2, \ldots, a_{n+1}\in\mathbb{Z} $ tali che: $ a_i \not\equiv a_j \bmod n $, per ogni $ i, j\in\{1,2,\ldots, n+1\} $, con $ i \neq j $.

E allora, comunque scelto $ i = 1, 2, ..., n $: $ a_{n+1} \not\equiv a_i \mod n $, ovvero $ a_{n+1} - a_i \not\equiv 0 \mod n $. E siccome le classi residue non nulle $ \bmod\;\! n $ sono in numero pari ad $ n-1 $ e le differenze di tipo $ a_{n+1} - a_i $ in numero pari ad $ n $, segue dal principio dei cassetti ch'esistono $ i, j = 1, 2, \ldots, n $, con $ i \neq j $, tali che: $ a_{n+1} - a_i \equiv a_{n+1} - a_j \mod n $, sicché: $ a_i \equiv a_j \bmod n $, contro le ipotesi. Assurdo!!! Se ne deduce l'asserto, e quindi (prontamente) la soluzione al problema di Evaristo.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 24 mar 2005, 09:08

Come al solito iperlogorroico Hitl...

I resti possibili modulo $ 7 $ sono, appunto $ 7 $, quindi, fra $ 8 $ numeri, per i cassetti (o Pigeonhole) due hanno lo stesso resto. La differenza fra i due numeri con egual resto risolve il problema. (Se vogliamo fare gli sboroni si legga $ n $ al posto di $ 7 $ e $ n+1 $ al posto di $ 8 $)

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

me sciagurato!!!

Messaggio da HiTLeuLeR » 24 mar 2005, 14:09

Essì, stavolta mi sarei potuto proprio risparmiare... :oops: Bon, tento di rifarmi con quest'altro:
EvaristeG ha scritto:Scelti comunque n+1 interi tra 1 e 2n ve ne sono due tali che uno divide l'altro.
Fissato $ n\in\mathbb{N}_0 $, siano $ a_1, a_2, \ldots, a_{n+1} $ interi arbitrari nell'insieme $ \{1, 2, \ldots, 2n\} $. Orbene, per il teorema fondamentale dell'Aritmetica, per ogni $ i = 1, 2, \ldots, n+1 $, risultano univocamente determinati $ \alpha_i, \beta_i\in\mathbb{N} $ tali che: $ a_i = 2^{\alpha_i}\beta_i $, con $ \beta_i \equiv 1 \bmod 2 $. E poiché $ \beta_1, \beta_2, \ldots, \beta_{n+1} $ sono $ n+1 $ interi dell'$ n $-insieme $ \{1, 3, \ldots, 2n-1\} $, stante il principio dei cassetti, nondimeno esistono necessariamente $ i, j = 1, 2, \ldots, n+1 $, con $ i\neq j $, tali che: $ \beta_i = \beta_j $. E allora $ a_i \mid a_j $, se $ \alpha_i \leq \alpha_j $; o viceversa $ a_j \mid a_i $, se $ \alpha_i > \alpha_j $. Ne fa seguito l'asserto, q.e.d.

Avatar utente
mates
Messaggi: 65
Iscritto il: 01 gen 1970, 01:00

Messaggio da mates » 24 mar 2005, 15:20

EvaristeG ha scritto: Marco si allena nella corsa per 44 giorni almeno una volta al giorno, per un totale di 70 volte. Dimostrare che esiste un periodo di giorni consecutivi durante i quali si allena esattamente 17 volte.
Indichiamo con $ a_{k} $ il numero di allenamenti fino al k-esimo giorno incluso.
Visto che Marco si allena almeno una volta al giorno avremo :
$ 1 \leq a_{1} < {a_{2} < \ldots < a_{44} = 70 $
Aggiungiamo a tutti i termini 17 :
$ 18 \leq a_{1} + 17 < a_{2} +17 < \ldots < a_{44} + 17 = 87 $
Consideriamo ora gli 88 numeri $ a_{1}, a_{2}, \ldots, a_{44}, a_{1}+17, a_{2} + 17, \ldots, a_{44} + 17 $. Visto che il più grande ($ a_{44} + 17 $) vale 87 e noi abbiamo 88 numeri, per il principio dei cassetti devono esserci 2 numeri uguali.
Inoltre abbiamo che $ a_{p} \neq a_{q} $ per $ p \neq q $ quindi esistono $ i, j \in \{1, \ldots, 44\} $ tali che $ a_{i} = a_{j} + 17 $.
Di conseguenza Marco si è allenato esattamente 17 volte nei giorni $ j, j+1, \ldots, i $.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

sarò pure iperlogorroico, ma esiste modo e modo...

Messaggio da HiTLeuLeR » 25 mar 2005, 01:34

EvaristeG ha scritto: Dimostrare che comunque presi 52 interi positivi, ve ne sono due, m e n, tali che m+n oppure m-n \`e multiplo di 100.
Bonus question : Rimane vero per 51 interi positivi?
Essendo $ n $ un numero naturale $ \geq 2 $, siano $ a_1, a_2, \ldots, a_{n+2}\in\mathbb{Z} $. Si tratta di dimostrare ch'esistono allora $ i, j = 1, 2, \ldots, n+2 $, con $ i \neq j $, t.c.: $ a_i + a_j \equiv 0 \bmod 2n $ oppure $ a_i - a_j \equiv 0 \bmod 2n $. Iniziamo con l'osservare che, qualunque sia $ t \in \mathbb{Z} $: $ t \equiv 0 \bmod 2n $ sse $ r_t \equiv 0 \bmod 2n $, ove $ r_t $ denota il resto della divisione intera di $ t $ per $ 2n $. Wlog, si può pertanto ammettere per il seguito che $ a_1, a_2, \ldots, a_{n+2} $ siano appartenenti all'insieme $ \{0, 1, \ldots, 2n-1\} $. Si può inoltre assumere $ a_i \neq a_j $, per ogni $ i, j = 1, 2, \ldots, n+2 $ tali che sia $ i \neq j $, ché altrimenti la tesi sarebbe banalmente verificata.

Stanti queste assunzioni, procediamo per assurdo, e supponiamo che, comunque scelti $ i, j = 1, 2, \ldots, n+2 $, con $ i \neq j $: $ a_i \pm a_j \not\equiv 0 \bmod 2n $. E allora, per ogni $ i, j = 2, 3, \ldots, n+2 $, essendo $ i \neq j $: $ a_1 \pm a_i \not\equiv a_1 \pm a_j \bmod 2n $, ché $ 0 < |a_i - a_j | < 2n $. Ne discende ch'entrambi gli insiemi $ \mathcal{A}^+ := \{a_1 + a_2, a_1 + a_3, \ldots, a_1 + a_{n+2}\} $ ed $ \mathcal{A}^- := \{a_1 - a_2, a_1 - a_3, \ldots, a_1 - a_{n+2}\} $ possiedono cardinalità pari ad $ n+1 $.

Osservando inoltre che, per qualsiasi $ i, j = 2, 3, \ldots, n+2 $, con $ i \neq j $: $ a_1 + a_i \equiv a_1 - a_j \bmod 2n $ sse $ a_i + a_j \equiv 0 \bmod 2n $, e che quest'ultima condizione (viste le ipotesi) può eventualmente sussistere solo se $ i = j $, e quindi $ a_i \equiv 0 \bmod n $, ovvero $ a_i = 0 $ vel $ a_i = n $, risulta d'altro canto che $ \mathcal{A}^+ \cap \mathcal{A}^- $ ha cardinalità finita $ \leq 2 $. Ergo, per il principio di inclusione-esclusione: $ |\mathcal{A}^+ \cup \mathcal{A}^-| = |\mathcal{A}^+| + |\mathcal{A}^-| - |\mathcal{A}^+ \cap \mathcal{A}^-| \geq (n+1) + (n+1) - 2 = 2n $.

E poiché le classi residue modulo $ 2n $ sono in numero pari esattamente a $ 2n $, ne viene (per il principio dei cassetti) che almeno uno degli elementi dell'insieme $ \mathcal{A}^+ \cup \mathcal{A}^- $ è divisibile per $ 2n $; oppure che esistono $ i, j = 1,2, \ldots, n+2 $, con $ i \neq j $, t.c.: $ a_1 - a_i \equiv a_1 + a_j \bmod 2n $, sicché: $ a_i + a_j \equiv 0 \bmod 2n $. Ambedue le conclusioni portano ad un assurdo, e di lì alla tesi.
Ultima modifica di HiTLeuLeR il 25 mar 2005, 10:07, modificato 1 volta in totale.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

la bonus question!

Messaggio da HiTLeuLeR » 25 mar 2005, 01:59

In quanto alla bonus question abbinata al problema precedente, osserviamo che, fissato un intero $ n \geq 2 $, gli $ n+1 $ interi positivi $ a_1 := 2n, a_2 := 2n+1, \ldots, a_{n+1} := 3n $ sono tali che, comunque scelti $ i, j = 1, 2, \ldots, n+1 $, con $ i \neq j $: $ 0 < |a_i - a_j| < 2n $ e $ 4n < |a_i + a_j| < 6n $, perciocché $ 2n \nmid (a_i \pm a_j) $. La risposta al quesito supplementare posto dal sommo Evaristo è pertanto seccamente negativa, sigh... :cry: :cry:

EDIT: piccola correzione ispirata nottetempo! :oops: :roll: :mrgreen:
Ultima modifica di HiTLeuLeR il 25 mar 2005, 10:00, modificato 2 volte in totale.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

arrivano i rimpiazzi...

Messaggio da HiTLeuLeR » 25 mar 2005, 02:35

Naturalmente, la soluzione al problema originale di Evariste si ottiene assumendo $ n = 50 $. Bon, siccome siamo in tema, ne approfitto per proporre un altro paio di problemi (piuttosto classici) in cui (volendo) si può far uso del principio dei cassetti, anche per rimpiazzare quelli già risolti:

Problema #1: essendo $ n\in\mathbb{N}_0 $, dimostrare che, comunque scelti $ n+1 $ elementi distinti nell'insieme $ \{1, 2, \ldots, 2n\} $, ne esistono almeno due primi fra loro (i.e., dotati di massimo comun divisore unitario).

Problema #2: provare che, per ogni $ m\in\mathbb{N}_0 $, esiste $ n\in\mathbb{N}_0 $ tale che: $ m \mid f_n $, ove $ \{f_n\}_{n\in\mathbb{N}} $ è la successione dei numeri di Fibonacci, definita ricorsivamente assumendo $ f_0 := 0, f_1 := 1 $ ed $ f_{n+2}:= f_{n+1} + f_n $, per ogni $ n\in\mathbb{N} $.

Rispondi