Pigeonhole e discesa infinita

[mates]

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

Dall'insieme $ \{1, 2, \ldots, 2n\} $ creiamo $ n $ cassetti in questo modo :
$ \{1,2\}, \{3,4\}, \ldots , \{2n-1, 2n\} $
Dovendo sistemare $ n+1 $ elementi in $ n $ cassetti, esisterà almeno un cassetto che contiene 2 elementi. Ma questi 2 elementi sono consecutivi e quindi primi tra loro.

Altro problema
Ad un party sono invitate $ n \geq 2 $ persone. Dimostrare che ci sono due invitati che hanno lo stesso numero di amici al party. (Supporre che la relazione "è amico di .. " sia simmetrica, ossia, se $ a $ è amico di $ b $ allora $ b $ è amico di $ a $).

[HiTLeuLeR]

Ok, mates, soluzione perfetta!!!

[Hammond]

Altro problema
Ad un party sono invitate $ n \geq 2 $ persone. Dimostrare che ci sono due invitati che hanno lo stesso numero di amici al party. (Supporre che la relazione "è amico di .. " sia simmetrica, ossia, se $ a $ è amico di $ b $ allora $ b $ è amico di $ a $).

Ogni persona ha un numero di amici variabile da $ 0 $ a $ n-1 $, ma questi due valori estremi non possono essere presenti contemporaneamente in quanto si escludono a vicenda. Restano allora $ n-1 $ cassetti per $ n $ persone, e ciò conclude la dimostrazione.

[Boll]

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

Problema appartenente alla categoria degli evergreen, quei problemi che ognuno ha fatto almeno $ 5 $ volte nella sua vita... E che ogni tanto reincotra, più o meno modificati :D

[enomis_costa88]

Questo l'ho notato solamente ora..

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.

Io me ne ricordo!!

Comunque si faceva vedendo che se c'è una soluzione puoi dilatarla e traslarla come ti pare e che gli elementi di una soluzione hanno la stessa parità.

Se hai un controesempio minimale (il cui sacchetto con più palline sia minimo) lo puoi dividere per due dopo avere visto che il sacchetto con meno palline ha 0 palline.
assurdo..

PS: grazie eva..

[evans]

avete qualche altro esempio sia di combinatoria che di algebra in cui applicare la discesa infinita?

[EvaristeG]

Evans, di solito la discesa infinita si usa in teoria dei numeri : ad esempio trovare le soluzioni intere di
$ x^2+y^2+z^2=2xyz $
o le soluzioni intere di
$ x^2+y^2=3(z^2+w^2) $
o le soluzioni intere di
$ x^4+y^4=z^2 $ (che copre il Teorema di Fermat nel caso n=4).

[evans]

@EvaristeG

Ma a cosa serve usare il principio della discesa infinita per la dimostrazione dell'irrazionalità di $ \sqrt{2} $. Non basta dire che si tratta di un assurdo poichè i numeri $ p,q $ da noi scelti non sono più primi tra loro come per ipotesi.

come si dimostra che invece $ \sqrt{4} $ è razionale usando la Discesa Infinita?

[edriv]

$ 2^2=4 $, come ti salta in mente di tirare in ballo la discesa infinita?

[EvaristeG]

@ evans : ma a cosa ti serve usare la coprimalità quando hai la discesa infinita?

Non ti sembra un po' sciocca come domanda? Ogni dimostrazione si può fare in molti modi diversi. La discesa infinita nei problemi di teoria dei numeri si applica sempre contando un certo tipo di fattori delle variabili coinvolte (ad es i fattori 2) ... ovvio che si può riscrivere supponendo che il numero in questione sia della forma 2^k * d con d dispari e poi dimostrare che d è anche pari, ma è semplicemente una diversità di tecnica.

[evans]

$ 2^2=4 $, come ti salta in mente di tirare in ballo la discesa infinita?

Sinceramente non ho capito la tua domanda.Poi cosa vuoi dire con$ 2^2=4 $ è questa la tua dimostrazione?non ci avevo pensato scusa..comunque io volevo sapere come si dimostra eseguendo lo stesso procedimento sull'irrazionalità di $ \sqrt{2} $ la razionalità di $ \sqrt{4} $ . In poche parole uso la Discesa infinita e dimostro che $ \sqrt{2} $ è irrazionale poi facendo lo stesso con $ \sqrt{4} $ dovrei riuscire a concludere che è razionale?
Beh potete farmelo vedere

@EvaristeG
Scusa hai ragione non avevo visto bene le ipotesi, grazie 1000

[EvaristeG]

La discesa infinita è una dimostrazione per assurdo : assumi la tesi e trovi una contraddizione, che è per l'appunto espressa dal fatto che un certo algoritmo che dovrebbe terminare (in quanto ad ogni passo possiamo associare un numero naturale sempre più piccolo e quindi prima o poi ci fermiamo a 0) non termina.
Un tale procedimento non può essere usato (a meno di grandi contorcimenti logico-masochistici) per arrivare ad una risposta affermativa... non è detto che ogni dimostrazione si possa fare in ogni modo (in un cesenatico riuscivi facilmente a dimostrare che due lati di un triangolo erano uguali, calcolandone le lunghezze, mentre se ti ostinavi a usare gli angoli e basta, non riuscivi a dimostrare che i corrispondenti angoli erano uguali ... non so se non sia possibile farlo, però di certo è moooolto difficile).
Nel caso della radice di 4 vorresti negare che essa sia irrazionale ... solo che non hai un modo intuitivo di ricollegare il problema ad una discesa infinita come invece ce l'avevi per negare che radice di due fosse razionale. Potresti dire : se l'algoritmo che per radice di 2 non terminava mai, per radice di 4 termina; ma questo è falso. Quindi non vedo proprio perchè sei convinto che debba esserci una dimostrazione di queso genere (inoltre, la radice quadrata di un numero naturale è razionale se e solo se il numero è quadrato di un altro naturale...).

[evans]

La cosa che non mi è chaira è questa: perchè non funziona così, dov'è l'errore

dimostriamo che $ \sqrt{4} $ non è un numero razionale.

dim : supponiamo PER ASSURDO che $ \sqrt{4}=p/q $ con p,q numeri naturali. Eleviamo al quadrato entrambi i membri ottenendo :
$ 4= p^2/q^2 $ ovvero $ 4q^2=p^2 $
quindi 4|p, ovvero 16|p², quindi possiamo dividere per 4 l'espressione ottenendo
$ q^2=4p_1^2 $
dove $ p_1=p/4 $ è ancora intero; da questo si ricava che 4|q e dunque che 16|q², quindi $ q_1=q/4 $ è un intero e possiamo scrivere
$ 4q_1^2=p_1^2 $
ovvero $ 4=p_1^2/q_1^2 $

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}/4 \quad q_n=q_{n-1}/4 $ 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 4 è irrazionale.

Lo so sembra stupido ma dove ho sbagliato?

[Sisifo]

Il problema é che 4 non é un numero primo, per cui, se $ 4|p^2 $ non é detto che $ 4 | p $... Infatti non é vero (come puoi verificare con p=2, q=1)