SNS 2004-2005, Es. 6 - Partizioni di un intero

[kn]

Una partizione di un numero intero $ \displaystyle~n\ge 1 $ è una decomposizione di $ \displaystyle~n $ in addendi interi (parti) $ \displaystyle~m_1, . . . ,m_k $ tali che $ \displaystyle~m_i\ge 1 $ e $ \displaystyle~m_1+\ldots+m_k = n $ (aggiungo $ \displaystyle~m_i\ge m_j,~\forall 1\le i<j\le k $, o comunque una partizione distinta da un'altra non può essere una sua permutazione, NdR ) Per esempio le partizioni di 3 sono $ \displaystyle~3,~ 2+1,~ 1+1+1 $ e quelle di 4 sono $ \displaystyle~4,~ 3+1,~ 2+2, ~2+1+1, ~1+1+1+1 $.
Si dimostri che il numero delle partizioni di un intero $ \displaystyle~n $ in al più $ \displaystyle~r $ parti è uguale al numero delle sue partizioni in parti ciascuna al massimo uguale a $ \displaystyle~r $.

[Tibor Gallai]

viewtopic.php?t=8758

[kn]

Ok scusate
Però quando postate gli esercizi sns cercate di non usare caratteri strani come slash o cancelletto (che vengono considerati spazi)! Se cercate il titolo esatto del thread trovato da TG, questo non compare nei primi 250 risultati
Consiglio di fare in modo che il titolo abbia in due parole separate l'anno accademico (ad es. 1999-2000) e il numero dell'esercizio, in modo da rendere la ricerca più agevole (a chi come me non fa neanche la fatica di cercare il testo vero e proprio ma si limita a cercare l'anno)

[Tibor Gallai]

Ma aspetta... Il 2004-2005 è l'anno dello scandaloso problema di Sylvester-Gallai... Vuoi dire che nello stesso anno c'era pure questo, che è un fatto ben noto dalla teoria classica?

[kn]

Sì ma perché scandaloso?

[Tibor Gallai]

Perché è un problema impossibile da risolvere se non ne hai già visto la soluzione. Quindi non tanto nello spirito di quello che dovrebbe essere un test d'ammissione alla sns.
Dico "impossibile" perché il problema ha resistito per mezzo secolo agli attacchi dei matematici del mondo, prima che fosse trovata una dimostrazione elementare (era nota una dimostrazione di Sylvester ben poco elementare e per niente breve). Nessuno può aspettarsi che un ragazzino lo risolva in 6 ore se non lo conosce già.

Aggiungi allo scandalo il fatto che poco prima del test (un paio di mesi, credo) il problema era stato (ri-)proposto su questo forum per la 2^ o 3^ volta, come esempio di "trabocchetto" dell'induzione. Un gigantesco aiuto a favore degli utenti del forum più assidui, e una grossa penalizzazione per gli altri.

[PubTusi]

Non l'hanno risolto per mezzo secolo? Ma dai...

[Tibor Gallai]

Non l'hanno risolto per mezzo secolo? Ma dai...

http://mathworld.wolfram.com/SylvestersLineProblem.html

A quanto pare, non esisteva nemmeno una dimostrazione non elementare di Sylvester. Effettivamente, la prima dimostrazione valida (ma non elementare!) del teorema fu trovata 47 anni dopo. Per la dimostrazione standard e più nota, breve ed elementare, si dovettero attendere invece 65 anni.

[kn]

Nessuno può aspettarsi che un ragazzino lo risolva in 6 ore se non lo conosce già.

[OT] Ci sono ben 6 ore? Fisica compresa? [/OT]

Perché è un problema impossibile da risolvere

Ma non l'hai risolto proprio tu per la prima volta?

[Tibor Gallai]

[OT] Ci sono ben 6 ore? Fisica compresa? [/OT]

6 ore per matematica, 6 ore per fisica. In 2 giorni diversi.

Ma non l'hai risolto proprio tu per la prima volta?

Secondo Erdős sì... Ma poi è saltato fuori che un certo Melchior aveva trovato qualcosa di quasi equivalente un paio d'anni prima, senza però esplicitarlo nella forma enunciata da Sylvester... Maledetto guastafeste.

[Davide90]

Perché è un problema impossibile da risolvere se non ne hai già visto la soluzione. Quindi non tanto nello spirito di quello che dovrebbe essere un test d'ammissione alla sns.

Concordo, quell'anno hanno messo insieme 5 problemi fattibilissimi e questo che è abbastanza improponibile se non ne hai già visto la soluzione...

Inoltre ho scoperto solo oggi che il teorema di Sylvester-Gallai è di un certo Tibor Gallai, matematico ungherese che aveva collaborato con Erdos.. Come mai hai scelto proprio lui come nickname?

A proposito di Erdos, una volta nel libro "Proofs from the Book" avevo letto una dimostrazione (che mi sembrava di ricordare che fosse di un teorema di Sylvester, ma magari ricordo male) che usava un trucchetto spettacolare: dalla geometria piana con punti e rette passava a una geometria sferica con circoli massimi al posto di punti e poli opposti al posto di rette, o viceversa...
Forse era proprio una dimostrazione di questo teorema?