Pigeonhole e discesa infinita

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

Messaggio da mates » 25 mar 2005, 08:43

HiTLeuLeR ha scritto: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 $).

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

mates sul problema #1

Messaggio da HiTLeuLeR » 25 mar 2005, 10:10

Ok, mates, soluzione perfetta!!!

Hammond
Messaggi: 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da Hammond » 27 mar 2005, 18:08

mates ha scritto: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.

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

Re: arrivano i rimpiazzi...

Messaggio da Boll » 27 mar 2005, 18:26

HiTLeuLeR ha scritto: 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:D

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 07 ott 2005, 18:16

Questo l'ho notato solamente ora..
Marco ha scritto: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!! :oops: :oops: :oops:

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..
Ultima modifica di enomis_costa88 il 27 ott 2007, 21:15, modificato 2 volte in totale.

Avatar utente
evans
Messaggi: 115
Iscritto il: 21 nov 2005, 20:52

Messaggio da evans » 26 ago 2006, 13:24

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

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

Messaggio da EvaristeG » 26 ago 2006, 13:44

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

Avatar utente
evans
Messaggi: 115
Iscritto il: 21 nov 2005, 20:52

Messaggio da evans » 28 set 2006, 10:14

:?: @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?

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 28 set 2006, 13:42

:shock:

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

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

Messaggio da EvaristeG » 28 set 2006, 15:07

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

Avatar utente
evans
Messaggi: 115
Iscritto il: 21 nov 2005, 20:52

Messaggio da evans » 29 set 2006, 21:02

edriv ha scritto::shock:

$ 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 $ :shock: :shock: è 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 :D

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

Messaggio da EvaristeG » 29 set 2006, 22:44

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

Avatar utente
evans
Messaggi: 115
Iscritto il: 21 nov 2005, 20:52

Messaggio da evans » 30 set 2006, 15:26

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?

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 30 set 2006, 16:31

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)
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph

Rispondi