compito di mate

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 01 gen 1970, 01:33

<!-- 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>Seguirà dimostrazione geometrica
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>attessissima, direi...
<BR>almeno da parte mia, data la semi-impenetrabilità dell\'ultima parte della dimostrazione di LB...(che non ha colpito solo me, a quanto vedo) <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>comunque una volta messo in piedi l\'\"impianto formale\" necessario x applicare il pigeonhole, e costruito l\'applicazione che associa ogni risultato con una certa somma a un\'altro, con somma \"più vicina\" a 3/2m si potevano contare brutalmente i modi di decomporre 10 in somme di 3 addendi compresi tra 0 e 7 (x il caso particolare)
<BR>certo, la risoluzione del caso generale, pur nella sua oscurità, ha molto più fascino...
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]

LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB » 01 gen 1970, 01:33

La formula di Antimateria mi pare sospetta poichè coincide con la mia solo per p <= 6.
<BR>
<BR>Essa è inoltre la versione troncata della seguente formula:
<BR>n^(p - 1) - Sum[(AMB[Floor[(p - 2*(i + 1))(n + 1)/2] + i, p - 1] + AMB[Ceiling[(p - 2*(i + 1))(n + 1)/2] + i, p - 1])*(-1)^i*Binomial[p - 1, i], {i, 0, Floor[p/2] - 1}]
<BR>dove AMB è il binomiale di Antimateria
<BR>
<BR>la quale invece (apparentemente) coincide con la mia per ogni valore.
<BR>
<BR>Ciò fa pensare che il troncamento sia errato.
<BR>
<BR>

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

Giusto LB, il fatto è che avevo costruito geometricamente lo spazio dei cubettini a due a due non confrontabili... Purtroppo, andando avanti a colpi di simplessi, succede che in troppe dimensioni questi cominciano ad ingrandirsi, e ad intersecarsi in modi strani. Avevo previsto che questo potesse succedere una volta (cosa che già in 3d non succede), e quindi ho aggiunto nella formula i termini con +(m-1)..., per riparare il danno aggiungendo dei nuovi simplessi. Non ho pensato che a loro volta questi si sarebbero intersecati (dalla dimensione 6, mi pare) ed avrebbero reso necessario l\'utilizzo del principio di inclusione-esclusione.
<BR>
<BR>Comunque, dopo giorni di pippe mentali, ho dimostrato anche il caso con 4 esercizi, ed ho qualche idea per una dimostrazione generale (anche se compaiono delle anomalie che non so come generalizzare). A breve posterò tutto, abbiate fede.

Avatar utente
Wilddiamond
Messaggi: 348
Iscritto il: 01 gen 1970, 01:00
Località: S.Anna - Pisa ...e Montale (PT)

Messaggio da Wilddiamond » 01 gen 1970, 01:33

<IMG SRC="images/forum/icons/icon_eek.gif">
-- Io sono fiero del mio sognare, di questo eterno mio incespicare --

F.Guccini "Quattro stracci" 1996

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

Forse nel messaggio precedente sono stato un po\' criptico: rimedio subito con il riassunto di tutte le mie elucubrazioni (tolte le bestemmie)!
<BR>
<BR>Supponiamo per ora di avere 3 esercizi, con voti da 1 a n ciascuno (nel caso del problema, n=8: ovviamente tutto rimane uguale a meno di traslazioni dei limiti dei voti). L\'astrazione che facciamo consiste nell\'immaginare il punteggio di uno studente come un cubetto di lato 1, in modo che tutti gli n<sup>3</sup> risultati possibili formino nel loro insieme un cubo di lato n. Ad esempio, se uno studente ha preso i voti 3, 7, 2 nei rispettivi esercizi, allora il cubetto corrispondente si troverà alle coordinate (3,7,2), etc. Naturalmente, se gli esercizi fossero 2, al posto del cubo avremmo un quadrato, se fossero 4 un ipercubo, etc.
<BR>
<BR>Definiamo la relazione simmetrica di comparabilità tra cubetti nel modo descritto dal problema: due cubetti sono comparabili se uno di essi ha le coordinate tutte minori o uguali di quelle dell\'altro. Dunque, dato il cubetto (x,y,z), i cubetti ad esso comparabili sono tutti e soli quelli che compongono l\'unione dei 2 parallelepipedi di diagonali rispettivamente (1,1,1) (x,y,z) e (x,y,z) (n,n,n). In particolare, i primi sono minori o uguali di (x,y,z), i secondi sono maggiori o uguali.
<BR>
<BR>Immaginiamo ora di tagliare il cubo con un piano ortogonale alla diagonale (1,1,1) (n,n,n), che passi per il centro di un suo cubetto. Per quanto detto sopra, tutti i cubetti che hanno il centro su tale piano sono a due a due non comparabili. Consideriamo in particolare il piano che passa per il centro del cubetto più vicino al punto medio della diagonale: i cubetti il cui centro si trova sul piano sono disposti secondo un \"esagono\", i cui lati sono delle file di quadratini messi in diagonale, una per ogni faccia del cubo. Siccome la diagonale del cubo è composta da n cubetti, se n è dispari allora l\'\"esagono\" è regolare, altrimenti no. In ogni caso, è facile dimostrare per induzione che se n è pari l\'esagono è composto da f(n)=(3/4)n<sup>2</sup> cubetti, se n è dispari è composto da f(n)=(3/4)n<sup>2</sup>+(1/4) cubetti (notare che per n=8 viene 48). Ciò che vogliamo è dimostrare che tale numero è anche il massimo numero di cubetti a due a due non comparabili presenti nel cubo.
<BR>
<BR>Per farlo, ci basta partizionare il cubo in f(n) regioni tali che i cubetti di ogni regione siano a due a due comparabili. Ora, c\'è un\'osservazione interessante che semplifica un bel po\' le cose, e permette di usare l\'induzione in modo efficace. Se proviamo a fare f(n)-f(n-2), notiamo che viene fuori un bel 3(n-1), sia nel caso pari, sia nel caso dispari. Questo suggerisce di prendere il \"guscio esterno\" del cubo, e ricoprirlo con 3 file di cubetti disposti a L. Se riusciamo a farlo, abbiamo automaticamente concluso la dimostrazione per induzione (si osservi che una spezzata orientata, tale che in ogni suo segmento vi è una coordinata che cresce mentre tutte le altre rimangono costanti, è composta da cubetti a due a due comparabili, quindi delle L disposte opportunamente possono fare al caso nostro).
<BR>
<BR>La prima fila di L ha i vertici nei seguenti cubetti:
<BR>(k,1,2), (k,1,n), (k,n,n)
<BR>con k che varia da 1 a n-1.
<BR>
<BR>La seconda fila di L ha i vertici nei seguenti cubetti:
<BR>(2,k,1), (n,k,1), (n,k,n)
<BR>con k che varia da 1 a n-1.
<BR>
<BR>La terza fila di L ha i vertici nei seguenti cubetti:
<BR>(1,2,k), (1,n,k), (n,n,k)
<BR>con k che varia da 1 a n-1.
<BR>
<BR>Vediamo che così abbiamo coperto tutto il guscio, tranne i cubetti (1,1,1) e (n,n,n), che possono essere però coperti da una qualunque delle L ad essi adiacenti, senza cambiare il \"verso\" della spezzata.
<BR>
<BR>
<BR>Tutto questo per m=3... Se vogliamo estenderci agli altri casi, usando lo stesso approccio, dobbiamo farci un\'idea della forma che avrà il luogo massimo degli ipercubetti a due a due non comparabili all\'interno dell\'ipercubo n<sup>m</sup>. Per prima cosa, notiamo che per m=2 il luogo è palesemente la diagonale (1,n) (n,1) del quadrato: essa contiene n quadratini, che è anche il massimo in quanto se due quadratini si trovassero sulla stessa riga o colonna sarebbero comparabili.
<BR>
<BR>Come informazione preliminare ci serve la misura del simplesso m-dimensionale (chiamato così per abuso di terminologia), ossia il numero di ipercubetti m-dimensionali che compongono la \"piramide\" avente m spigoli lunghi n a due a due ortogonali (che indichiamo con S<sub>m</sub>(n)). Se immaginiamo il vertice del simplesso nell\'origine, e gli spigoli giacenti sugli assi, possiamo dire che il numero di ipercubetti che lo compongono è pari al numero di m-uple di naturali aventi somma minore di n. Il che è pari al numero di (m+1)-uple di naturali aventi somma n-1 (facendo finta che vi sia una (m+1)-esima variabile, che porta la somma delle prime m a n-1). Insomma, è come se avessimo n-1 oggetti da distribuire in m+1 contenitori, e questo può essere fatto in {m+n-1║n-1} modi. Dunque, S<sub>m</sub>(n)={m+n-1║m} (sto usando le notazioni del mio post precedente).
<BR>
<BR>Ora, prendiamo il nostro ipercubo di dimensione m e tagliamolo in n fette ipecubiche di dimensione m-1. Facendo un\'analogia con i casi m=2 e m=3, possiamo congetturare che in tali fette gli ipercubetti a due a due incomparabili debbano essere disposti parallelamente al luogo massimo degli ipercubetti a due a due incomparabili nell\'ipercubo di dimensione m-1. Inoltre, le proiezioni degli n luoghi su uno di questi ipercubi (m-1)-dimensionali risultano a due a due disgiunte.
<BR>
<BR>Quindi, riunendo insieme gli n luoghi trovati nelle n sezioni dell\'ipercubo, otteniamo una figura di dimensione m-1, inclinata nell\'m-esima dimensione, che si può ricavare anche sottraendo dall\'ipercubo di dimensione m-1 i due simplessi aventi i vertici agli estremi di una diagonale e gli spigoli di lunghezza opportuna.
<BR>
<BR>Per trovare la lunghezza degli spigoli, procediamo così: prendiamo una diagonale dell\'ipercubo (m-1)-dimensionale di lato n, e contiamo quanti sono gli iperspazi (m-2)-dimensionali ad essa ortogonali che passano per il centro di qualche ipercubetto. Se si condidera un percorso di ipercubetti che unisce gli estremi della diagonale con una spezzata fatta di m-1 spigoli dell\'ipercubo, si vede che ad ogni suo ipercubetto corrisponde esattamente uno di tali iperspazi (m-2)-dimensionali, che quindi sono esattamente (m-1)(n-1)+1. Di questi, gli n centrali sono occupati dagli ipercubetti a due a due incomparabili, quindi ne restano (m-2)(n-1) da dividere tra i due simplessi, che avranno quindi spigoli lunghi rispettivamente Floor((m-2)(n-1)/2) e Ceiling((m-2)(n-1)/2).
<BR>
<BR>Ora, c\'è l\'inconveniente di cui parlavo, e cioè che per m grandi i due simplessi escono fuori dall\'ipercubo con m-1 altri simplessini, di spigoli lunghi n ipercubetti in meno. A loro volta, questi si intersecano tra loro in altri simplessi, etc etc. La formula finale è quella che ha scritto lb_ nel suo ultimo post.
<BR>
<BR>
<BR>Passiamo ora a dimostrare che la congettura è vera per 4 esercizi. Sostituendo m=4 nella formulazza e facendo le dovute semplificazioni, si ricava f(n)=(2n<sup>3</sup>+n)/3. Anche questa volta, salta fuori un appagante f(n)-f(n-2)=4(n-1)<sup>2</sup>+2, che suggerisce di usare di nuovo i pezzi a forma di L per comporre il guscio esterno dell\'ipercubo, e dimostrare quindi la congettura per induzione (naturalmente, ogni L dovrà essere orientata in modo che i suoi ipercubetti siano a due a due comparabili). Questa volta, siccome il guscio è formato da 8 cubi di lato n, ognuno dei quali ha in comune una faccia con ognuno dei 6 cubi adiacenti, possiamo raggruppare le L in 4 gruppi da (n-1)<sup>2</sup>, e fare in modo che ogni gruppo riempia 2 cubi adiacenti. Rimarrà scoperto qualcosa, che sarà riempito dalle 2 regioni rimanenti (quel +2 nella formula...).
<BR>
<BR>Le L del primo gruppo hanno i vertici nei seguenti ipercubetti:
<BR>(j,k,1,2), (j,k,1,n), (j,k,n,n)
<BR>con j che varia da 1 a n-1, e k che varia da 2 a n.
<BR>
<BR>Le L del secondo gruppo hanno i vertici nei seguenti ipercubetti:
<BR>(2,1,j,k), (n,1,j,k), (n,n,j,k)
<BR>con j che varia da 1 a n-1, e k che varia da 2 a n.
<BR>
<BR>Le L del terzo gruppo hanno i vertici nei seguenti ipercubetti:
<BR>(k,j,1,1), (k,j,n,1), (k,j,n,n-1)
<BR>con j che varia da 1 a n-1, e k che varia da 2 a n.
<BR>
<BR>Le L del quarto gruppo hanno i vertici nei seguenti ipercubetti:
<BR>(1,1,k,j), (1,n,k,j), (n-1,n,k,j)
<BR>con j che varia da 1 a n-1, e k che varia da 2 a n.
<BR>
<BR>Le strisce di cubetti che restano fuori possono essere coperte con le 2 spezzate che hanno i vertici nei seguenti ipercubetti:
<BR>(1,1,1,1), (1,n,1,1), (n,n,1,1), (n,n,n,1), (n,n,n,n-1);
<BR>(1,1,1,2), (1,1,1,n), (1,1,n,n), (n,1,n,n), (n,n,n,n).
<BR>
<BR>
<BR>A questo punto, verrebbe voglia di procedere nello stesso modo anche per m=5, e tentare una generalizzazione della dimostrazione. Purtroppo, se si prova a scrivere l\'espressione per il numero di regioni nel guscio esterno dell\'ipercubo 5d, pare che non si riesca ad esplicitare il termine 5(n-1)<sup>3</sup>, come ci si sarebbe aspettati, e quindi vaffanculo.
<BR>
<BR><!-- BBCode Start --><IMG SRC="http://images.google.it/images?q=tbn:3g ... onspir.jpg"><!-- BBCode End --><BR><BR>[ Questo Messaggio è stato Modificato da: Antimateria il 22-11-2003 17:59 ]

Ospite

Messaggio da Ospite » 01 gen 1970, 01:33

gh, mi dai delle ripetizioni?
<BR> <IMG SRC="images/forum/icons/icon_eek.gif"> [addsig]

Ospite

Messaggio da Ospite » 01 gen 1970, 01:33

scusate ma ho bisogno di qualche spiegazione quindi...
<BR>UP!!![addsig]

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 01 gen 1970, 01:33

....improvvisamente le funzioni generatrici mi stanno molto + simpatiche!!!
<BR> <IMG SRC="images/forum/icons/icon_razz.gif"> <IMG SRC="images/forum/icons/icon_razz.gif"> <IMG SRC="images/forum/icons/icon_razz.gif">
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

Mancava un /2, come avete fatto a non accorgervene?

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 01 gen 1970, 01:33

<IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">

Bloccato