OliForum Matematico

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.
 
 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.
 
 
 Vi mando subito il 1°.

PROBLEMA 1.
 
 Dimostrate che un insieme di n differenti elementi ha esattamente 2^n sottoinsiemi differenti.
 
 [ Questo Messaggio è stato Modificato da: dieciottantunesimi il 12-01-2004 21:26 ] [ Questo Messaggio è stato Modificato da: dieciottantunesimi il 12-01-2004 21:27 ]

Come si fa a mettere il carattere bianco?

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-01-12 20:52, dieciottantunesimi wrote:
 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.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Capito kaio?

(font color=white)messaggio(/font)
 
 sostituendo () con minore/maggiore

SOL 1.
 
 
 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).
 
 quindi il numero totale di sottoinsiemi è: sumC(n,i)=sum(n,i)
 
 ma i vari (n,i) altro non sono che i coefficienti binomiali del polinomio P=(x+y)n. E la loro somma si ottiene ponendo x=y=1.
 
 Quindi sum(n,i)=(1+1)n=2n
 
 
 EDIT: errori di battitura -.- [ Questo Messaggio è stato Modificato da: AleX_ZeTa il 12-01-2004 21:46 ]

SOL 1.
 
 
 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.
 è 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

SOL. 1
 
 Io preferisco farlo induttivamente e molto + semplicemente...
 
 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.
 Con n elementi abbiamo 2n elementi
 
 
 Fatto... <IMG SRC="images/forum/icons/icon_biggrin.gif">
 
 P.S. mi sono dimenticato l\'insieme con 0 elementi che cmq ha 20 =1 sottoinsiemi cioè solo Ø [ Questo Messaggio è stato Modificato da: Simo_the_wolf il 12-01-2004 21:57 ]

PROBLEMA 2:
 Siano x1, x2, x3 ... una sequenza di numeri reali che soddisfano
 xn = ( xn-2 x n-1 ) / ( 2xn-2 - xn-1 ), n = 3, 4, 5, ...
 
 Stabilire le condizioni necessarie e sufficienti per x1 e x2 affinchè xn sia un intero per infiniti valori di n.

Uhm... ripeto, lodevole come iniziativa, fai benissimo... magari mr. Larson avrebbe qualcosa da ridire sul copyright...
 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...
 In secondo luogo, non ci starebbe male una soluzione \"ufficiale\" che impieghi la tecnica euristica in oggetto...
 
 Ex. PATTERN = experimentations alla ricerca di regolarità.
 Per il problema dei sottoinsieme l\'approccio patternoso è semplicemente una tabella...
 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\"
 
 Ok, comunque continuate e perdonate gli oziosi commenti, l\'opera è meritoria

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.

Hint prob. 2 : 
 Dobbiamo trovare una regolarità e questo esercizio si presta bene a questo modo di procedere: esprimi tutto in funzione di x1 e x2.

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 [ Questo Messaggio è stato Modificato da: AleX_ZeTa il 13-01-2004 16:38 ]

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

Per Alex:
 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
 xn = (x1 x2)/(n(x1 - x2) + (2 x2 -x1)) che è intera SE e SOLO SE x1 = x2. Non ci complichiamo la vita. Bravo comunque. 
 
 Bon, passiamo al prossimo:
 PROBLEMA 3: 
 Trovare gli interi positivi n e a1, a2, a3, ...an tali che la sum(k=1 -> n) ak = 1000 e la prod(k=1 -> n) ak sia massima.
 
 
 [ Questo Messaggio è stato Modificato da: dieciottantunesimi il 13-01-2004 22:00 ] [ Questo Messaggio è stato Modificato da: dieciottantunesimi il 13-01-2004 22:08 ]

OliForum Matematico

1. PATTERN