OliForum Matematico

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!!!

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

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.

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?

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!!!

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.]

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.

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!!! ):

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.

Pare che qui la gente non apprezzi molto i tuoi problemi, Evariste!!! A me piacciono tanto, invece...

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.

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 $)

Essì, stavolta mi sarei potuto proprio risparmiare... 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.

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 $.

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.

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...

EDIT: piccola correzione ispirata nottetempo!

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} $.