1. PATTERN

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

dieciottantunesimi
Messaggi: 218
Iscritto il: 01 gen 1970, 01:00
Località: (0;1/5)

Messaggio da dieciottantunesimi »

Proporrò un\'esercizio alla volta numerandoli. Per la soluzione (ce ne sono sempre più di una, trovatele tutte! ) scrivete sempre: SOL. n (numero dell\'esercizio). Partiamo dal facile (i più esperti abbiano pazienza) e pian piano passaimo al difficile. Mi raccomando, dimostrazioni in carattere BIANCO.
<BR>
<BR>Normalmente il solutore cerca di farsi un\'idea del problema e \"prova\" a convincersi della plausibilità del risultato. Questo lo si può fare al meglio esaminando i casi speciali più immediati; se fate questa esplorazione in maniera sistematica \"potrebbero\" emergere patterns che vi suggeriranno la via da prendere.
<BR>
<BR>
<BR>Vi mando subito il 1°.
<img src="http://www.ocf.berkeley.edu/~wwu/YaBBImages/avatars/run_in_box.gif">
dieciottantunesimi
Messaggi: 218
Iscritto il: 01 gen 1970, 01:00
Località: (0;1/5)

Messaggio da dieciottantunesimi »

<font color=red>PROBLEMA 1.</font>
<BR>
<BR><font color=blue>Dimostrate che un insieme di n differenti elementi ha esattamente 2^n sottoinsiemi differenti.</font>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: dieciottantunesimi il 12-01-2004 21:26 ]<BR><BR>[ Questo Messaggio è stato Modificato da: dieciottantunesimi il 12-01-2004 21:27 ]
<img src="http://www.ocf.berkeley.edu/~wwu/YaBBImages/avatars/run_in_box.gif">
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

Come si fa a mettere il carattere bianco?
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-01-12 20:52, dieciottantunesimi wrote:
<BR>scrivete sempre: SOL. n (numero dell\'esercizio). Partiamo dal facile (i più esperti abbiano pazienza) e pian piano passaimo al difficile. Mi raccomando, dimostrazioni in carattere BIANCO.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Capito kaio?
AleX_ZeTa
Messaggi: 625
Iscritto il: 01 gen 1970, 01:00
Località: Milano
Contatta:

Messaggio da AleX_ZeTa »

(font color=white)messaggio(/font)
<BR>
<BR>sostituendo () con minore/maggiore
"E se si sono rotti i freni?"
"Se si sono rotti i freni non ci resta che l'autostop e il viaggio si complica. Faremo il giro del mondo a piedi."
AleX_ZeTa
Messaggi: 625
Iscritto il: 01 gen 1970, 01:00
Località: Milano
Contatta:

Messaggio da AleX_ZeTa »

SOL 1.
<BR>
<BR><font color=white>
<BR>considerando anche l\'insieme vuoto come sottoinsieme degli n elementi si ottiene facilmente che i sottoinsiemi di k elementi (con 0 <= k <= n) sono dati da C(n,k).
<BR>
<BR>quindi il numero totale di sottoinsiemi è: sumC(n,i)=sum(n,i)
<BR>
<BR>ma i vari (n,i) altro non sono che i coefficienti binomiali del polinomio P=(x+y)<sup>n</sup>. E la loro somma si ottiene ponendo x=y=1.
<BR>
<BR>Quindi sum(n,i)=(1+1)<sup>n</sup>=2<sup>n</sup>
<BR></font>
<BR>
<BR>EDIT: errori di battitura -.-<BR><BR>[ Questo Messaggio è stato Modificato da: AleX_ZeTa il 12-01-2004 21:46 ]
"E se si sono rotti i freni?"
"Se si sono rotti i freni non ci resta che l'autostop e il viaggio si complica. Faremo il giro del mondo a piedi."
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

SOL 1.
<BR>
<BR><font color=white>
<BR>Tutti i possibili sottoinsiemi del nostro insieme di partenza possono essere considerati una n-upla di a_i=1 o 0 a seconda se l\'elemento iesimo appartiene o no al sottoinsieme considerato.
<BR>è evidente che le disposizioni con ripetizione di 2 oggetti (0 o 1) di classe n sono 2^n, e questo è pertanto il numero di tutti i possibili sottoinsiemi
<BR></font>
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

SOL. 1
<BR>
<BR>Io preferisco farlo induttivamente e molto + semplicemente...
<BR><font color=white>
<BR>L\'insieme con 1 elemento ha 2 sottoinsiemi: l\'elemento stesso e Ø. Aggiungiamo un elemento; tutti i sottoinsiemi del nuovo insieme saranno tutti gli stessi dell\'insieme precedente con o senza l\'elemento nuovo quindi saranno il doppio. Quindi se con 1 elemento abbiamo 2 sottoinsiemi con 2 elementi ne abbiamo 2*2 con 3 ne abbiamo 2*2*2.
<BR>Con n elementi abbiamo 2<sup>n</sup> elementi
<BR></font>
<BR>
<BR>Fatto... <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>P.S. mi sono dimenticato l\'insieme con 0 elementi che cmq ha 2<sup>0</sup> =1 sottoinsiemi cioè solo Ø<BR><BR>[ Questo Messaggio è stato Modificato da: Simo_the_wolf il 12-01-2004 21:57 ]
dieciottantunesimi
Messaggi: 218
Iscritto il: 01 gen 1970, 01:00
Località: (0;1/5)

Messaggio da dieciottantunesimi »

<font color=red>PROBLEMA 2:</font>
<BR><font color=blue>Siano x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub> ... una sequenza di numeri reali che soddisfano
<BR>x<sub>n</sub> = ( x<sub>n-2</sub> x <sub>n-1</sub> ) / ( 2x<sub>n-2</sub> - x<sub>n-1</sub> ), n = 3, 4, 5, ...
<BR>
<BR>Stabilire le condizioni necessarie e sufficienti per x<sub>1</sub> e x<sub>2</sub> affinchè x<sub>n</sub> sia un intero per infiniti valori di n.
<BR></font>
<img src="http://www.ocf.berkeley.edu/~wwu/YaBBImages/avatars/run_in_box.gif">
lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

Messaggio da lordgauss »

Uhm... ripeto, lodevole come iniziativa, fai benissimo... magari mr. Larson avrebbe qualcosa da ridire sul copyright...
<BR>Seriamente, concordo sulla traccia da seguire (i 12 comandamenti sono un ottimo primo approccio al problem solving), magari si potrebbe aggiornare un po\' il problem-chest...
<BR>In secondo luogo, non ci starebbe male una soluzione \"ufficiale\" che impieghi la tecnica euristica in oggetto...
<BR>
<BR>Ex. PATTERN = experimentations alla ricerca di regolarità.
<BR>Per il problema dei sottoinsieme l\'approccio patternoso è semplicemente una tabella...
<BR>Certo che il modo cui 10/81 ha proposto il problema ne inificia il valore pedagogico... la domanda doveva essere: \"Quanti sottoinsiemi differenti un insieme di n differenti elementi?\" NON \"Dimostrate che un insieme di n differenti elementi ha esattamente 2^n sottoinsiemi differenti\"
<BR>
<BR>Ok, comunque continuate e perdonate gli oziosi commenti, l\'opera è meritoria
dieciottantunesimi
Messaggi: 218
Iscritto il: 01 gen 1970, 01:00
Località: (0;1/5)

Messaggio da dieciottantunesimi »

Commenti giustissimi, Lordgauss. Terrò conto del tuo consiglio e modificherò in modalità pedagogica gli esercizi tratti rigorosamente dal Larson (che sto leggendo in questi giorni). Anche esercizi diversi (\"tratti da altri libri\") sono ben accetti, basta metterli nelle sezioni giuste man mano che le metterò, anche questo può essere pedagogico.
<img src="http://www.ocf.berkeley.edu/~wwu/YaBBImages/avatars/run_in_box.gif">
dieciottantunesimi
Messaggi: 218
Iscritto il: 01 gen 1970, 01:00
Località: (0;1/5)

Messaggio da dieciottantunesimi »

<font color=red>Hint prob. 2 : </font>
<BR><font color=white> Dobbiamo trovare una regolarità e questo esercizio si presta bene a questo modo di procedere: esprimi tutto in funzione di x<sub>1</sub> e x<sub>2</sub>.
<BR></font>
<img src="http://www.ocf.berkeley.edu/~wwu/YaBBImages/avatars/run_in_box.gif">
AleX_ZeTa
Messaggi: 625
Iscritto il: 01 gen 1970, 01:00
Località: Milano
Contatta:

Messaggio da AleX_ZeTa »

10/81 ti ho mandato un pm... se hai tempo/voglia di rispondermi te ne sono grato <IMG SRC="images/forum/icons/icon_wink.gif"> sto impazzendo su questo maledetto problema<BR><BR>[ Questo Messaggio è stato Modificato da: AleX_ZeTa il 13-01-2004 16:38 ]
"E se si sono rotti i freni?"
"Se si sono rotti i freni non ci resta che l'autostop e il viaggio si complica. Faremo il giro del mondo a piedi."
AleX_ZeTa
Messaggi: 625
Iscritto il: 01 gen 1970, 01:00
Località: Milano
Contatta:

Messaggio da AleX_ZeTa »

credo di esserci...
<BR>
<BR>SOL 2.
<BR>
<BR><font color=white>
<BR>Poniamo anzitutto delle condizioni di esistenza iniziali in modo da non porci poi alcun problema su denominatori & co.
<BR>
<BR>si ottiene facilmente che:
<BR>x<sub>2</sub> != 2x<sub>1</sub>
<BR>x<sub>1</sub> != 0
<BR>x<sub>2</sub> != 0
<BR>
<BR>tali condizioni garantiscono anche che x<sub>n</sub> != 0 per qualunque n>2
<BR>
<BR>
<BR>facendo qualche facile prova con n=3,4 si intuisce che x<sub>n</sub> si può scrivere come:
<BR>
<BR>x<sub>n</sub>=(x<sub>1</sub>x<sub>2</sub>)/[(n-1)x<sub>1</sub>-(n-2)x<sub>2</sub>]
<BR>
<BR>lo dimostriamo ora per induzione: abbiamo già verificato che è valido per n=3,4 quindi possiamo porre oltre a x<sub>n</sub> anche x<sub>n-1</sub>:
<BR>
<BR>x<sub>n-1</sub>=(x<sub>1</sub>x<sub>2</sub>)/[(n-2)x<sub>1</sub>-(n-3)x<sub>2</sub>]
<BR>
<BR>Calcoliamo ora x<sub>n+1</sub>:
<BR>
<BR>[1] x<sub>n+1</sub>=(x<sub>1</sub>x<sub>2</sub>)/[nx<sub>1</sub>-(n-1)x<sub>2</sub>]
<BR>
<BR>ma contemporaneamente
<BR>
<BR>x<sub>n+1</sub>=(x<sub>n</sub>x<sub>n-1</sub>)/(2x<sub>n-1</sub>-x<sub>n</sub>)
<BR>
<BR>sostituiamo in quest\'ultima i valori ottenuti in precedenza e dopo qualche passaggio otteniamo proprio la [1] quindi la proprietà è dimostrata.
<BR>
<BR>
<BR>Quindi sappiamo che:
<BR>
<BR>x<sub>n</sub>=(x<sub>1</sub>x<sub>2</sub>)/[(n-1)x<sub>1</sub>-(n-2)x<sub>2</sub>]
<BR>
<BR>svolgendo i conti al denominatore:
<BR>
<BR>x<sub>n</sub>=(x<sub>1</sub>x<sub>2</sub>)/(nx<sub>1</sub>-x<sub>1</sub>-nx<sub>2</sub>+2x<sub>2</sub>)
<BR>
<BR>x<sub>n</sub>=(x<sub>1</sub>x<sub>2</sub>)/[n(x<sub>1</sub>-x<sub>2</sub>)-x<sub>1</sub>+2x<sub>2</sub>]
<BR>
<BR>è ora evidente che condizione sufficiente perchè x<sub>n</sub> sia INTERO è che x<sub>1</sub>=x<sub>2</sub> e che x<sub>1</sub>,x<sub>2</sub>€N
<BR>
<BR>controlliamo ora che sia anche condizione necessaria: torniamo quindi in R e poniamo x<sub>1</sub> != x<sub>2</sub>
<BR>
<BR>perchè x<sub>n</sub> sia intero occorre che il numeratore sia multiplo del denominatore: quindi, posto k€N abbiamo
<BR>
<BR>x<sub>1</sub>x<sub>2</sub>=k*[(n-1)x<sub>1</sub>-(n-2)x<sub>2</sub>]
<BR>
<BR>da cui si ottiene [2] x<sub>1</sub>=k(n-2)x<sub>2</sub>/[x<sub>2</sub>+k(n-1)]
<BR>
<BR>dato che i valori di n per cui la [2] è valida devono essere infiniti, deve esistere almeno un j€N, j != n tale che x<sub>j</sub>€N e quindi che
<BR>
<BR>x<sub>1</sub>=h(j-2)x<sub>2</sub>/[x<sub>2</sub>+h(j-1)]
<BR>
<BR>con h€N.
<BR>
<BR>ciò è verificato, non essendo noti x<sub>1</sub> e x<sub>2</sub> se e solo se è verificato il sistema:
<BR>
<BR>k(n-2)=h(j-2)
<BR>k(n-1)=h(j-1)
<BR>
<BR>Tale sistema ha un\'unica soluzione per j: j=n. Ma tale soluzione contraddice l\'ipotesi di j != n quindi x<sub>1</sub> non può essere diverso da x<sub>2</sub> altrimenti si avrebbe al massimo un solo valore intero per x<sub>n</sub>
<BR></font>
<BR>
<BR>spero di non aver scritto troppe cazzate <IMG SRC="images/forum/icons/icon_cool.gif">
<BR>ditemi se è giusto <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>
<BR>EDIT: non ci credo... nelle condizioni iniziali per un errore di battitura ero riuscito a negare la tesi -.-\'\' vabbe ora è a posto... spero)<BR><BR>[ Questo Messaggio è stato Modificato da: AleX_ZeTa il 13-01-2004 21:16 ]
"E se si sono rotti i freni?"
"Se si sono rotti i freni non ci resta che l'autostop e il viaggio si complica. Faremo il giro del mondo a piedi."
dieciottantunesimi
Messaggi: 218
Iscritto il: 01 gen 1970, 01:00
Località: (0;1/5)

Messaggio da dieciottantunesimi »

Per Alex:
<BR><font color=white>Ritengo che la tua soluzione sia buona, nel senso che è corretta; solo che, a meno che non ho letto male, credo che una volta dimostrato x1 = x2 hai già la condizione necessaria in quanto sai che
<BR>x<sub>n</sub> = (x1 x2)/(n(x1 - x2) + (2 x2 -x1)) che è intera SE e SOLO SE x1 = x2. Non ci complichiamo la vita. Bravo comunque. </font>
<BR>
<BR>Bon, passiamo al prossimo:
<BR><font color=red>PROBLEMA 3: </font>
<BR><font color=blue> Trovare gli interi positivi n e a1, a2, a3, ...a<sub>n</sub> tali che la sum(k=1 -> n) a<sub>k</sub> = 1000 e la prod(k=1 -> n) a<sub>k</sub> sia massima.
<BR></font>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: dieciottantunesimi il 13-01-2004 22:00 ]<BR><BR>[ Questo Messaggio è stato Modificato da: dieciottantunesimi il 13-01-2004 22:08 ]
<img src="http://www.ocf.berkeley.edu/~wwu/YaBBImages/avatars/run_in_box.gif">
Bloccato