Cesenatico 1990 quesito 6

[gst_113]

il testo del problema è:

Alcune palline sono distribuite in 2n + 1 sacchetti. Supponiamo che,
tolto un qualunque sacchetto, sia possibile suddividere i rimanenti in
due gruppi di n sacchetti, in modo che ciascun gruppo contenga lo stesso
numero complessivo di palline. Dimostrare che i sacchetti contengono
tutti lo stesso numero di palline.

è possibile risolverlo per induzione?

[julio14]

Per quello che tu credo intenda come induzione, non so. Poi si può usare una discesa infinita, che è un'induzione camuffata.

[Tibor Gallai]

è possibile risolverlo per induzione?

Per quello che credo julio14 intenda dicendo che crede tu intenda come induzione, non so nemmeno io.
In compenso, puoi trovare la soluzione al problema nella prima edizione del libro delle olimpiadi italiane, quella del 1994 circa. Se non ricordo male, il problema fu dato a Cortona o giù di lì. Sono quasi certo che lì non venga usata l'induzione, ed inoltre ogni mio grezzo tentativo dell'epoca di risolvere il problema per induzione fallì. Ciò non esclude che si possa tranquillamente fare per induzione: infatti, se quello che dice julio14 sulla discesa infinita è vero, considera che essa è de facto un'induzione.

EDIT:
Ok, mi è venuto in mente come farlo con la discesa infinita. Si può in effetti convertire in un'induzione, ma non su n, bensì sul numero totale di monetine, o quel cappero che sono.

EDIT^2:
Hai anche detto che è un Cesenatico e non un Cortona, sono sveglio!

[Fedecart]

A me è venuta in mente un'idea ma si tratta di ragionare per assurdo. Secondo voi funzionerebbe?

[gst_113]

come soluzine a questo problema ho letto quella di Giove, che tra l'altro mi è piaciuta molto, solo che prima di guardarla mi era venuta in mente un idea e volevo controllare se avrei fatto giusto.
Ecco quello che pensavo:

Prendiamo il caso n=1, allora ci sono tre sacchetti con un munero a,b,c di palline.
se togliamo il secchetto con a allora b=c, se togliamo b allora a=c e quindi a=b=c.

Passo induttivo:
Supponiamo che 2n+1 sacchetti hanno tutti lo stesso numero di palline a, per passare al caso sucessivo n+1 bisogna aggiungere due sacchetti con b e c palline.
Se si toglie un sacchetto dei due aggiunti si vede che si devono poter dividere i rimanenti 2n+2 sacchetti in modo che la somma delle palline sia la stessa, da una parte ci vanno n+1 sacchetti con a palline e dall'altra ce ne vanno n con a palline e uno con b.

(n+1)*a=n*a+b
(n+1-n)*a=b
a=b.

si dimostra allo stesso modo che a=c e così è dimostrato che tutti gli 2(n+1)+1 sacchetti contengono lo stesso numero di palline.

é giusto? e se no, cosa ho sbagliato?

[SkZ]

postala. Spesso si dimostra per assurdo. Chiamasi Modus tollens
http://it.wikipedia.org/wiki/Modus_tollens

[Tibor Gallai]

é giusto? e se no, cosa ho sbagliato?

E' sbagliata l'applicazione dell'ipotesi induttiva dentro al passo induttivo.
Esamina i dettagli (logici) della dimostrazione, e vedi dov'è che scazza.

[gst_113]

Non capisco qual'è l'errore (sono un novizio nell'induzione)

[Tibor Gallai]

Allora, formalizza! Scrivi per filo e per segno la proposizione che intendi dimostrare per induzione. Poi vedi cosa dice l'ipotesi induttiva al momento in cui la applichi, vedi cosa dice il passo induttivo, etc. Insomma riscrivi tutto senza andare "a braccio".

[julio14]

Ussignur! non ditemi che qua inizia un altro thread chilometrico come per Sylvester, eh!

[Tibor Gallai]

Stavo pensando la stessa cosa, ma non sarebbe mica un male, eh!
L'importante è che non lo mettano più come problema 6 dell'ammissione SNS del prossimo anno (come successe con Sylvester nel 2004), con conseguente ammissione di capre che per puro caso hanno letto questa cosa sul forum un mese prima del test.

[gst_113]

Scusate se non ho risposto per una settimana, ma sono stato in gita.

La mia idea per il passo induttivo era questa:
2n+1 insiemi hanno la stessa cadinalità |A|=a.
2(n+1)+1=2n+1+2.
i 2n+1 insiemi hanno cardinalità a, gli altri due hanno cardinalità b e c.
gli insiemi sono quindi (2n+1)A+B+C

supponendo di togliere l'insieme B si deve poter dividere (2n+1)A+C in due gruppi di n+1 insiemi tali che la somma delle cardinalità degli insiemi di ciasscun gruppo sia uguale.
i due gruppi sono (n+1)A e nA+B
quindi (n+1)|A|=n|A|+|B|
(n+1)|A|-n|A|=|B|
|A|=|B|=a.

si fa lo stesso per C e si mostra che tutti gli insiemi hanno cardinalità a.

Dov'è l'errore? Mi potete anche postare una formalizzazione più corretta?(sono sicuro che ce ne sono)

(ah, cos'è successo con Sylvester quella volta?)

[julio14]

2n+1 insiemi hanno la stessa cadinalità |A|=a.

L'errore sta qua. Il resto non l'ho letto ma dovrebbe essere giusto, l'importante è che tu capisca dove sta l'errore nel fare questa affermazione. Il resto lascialo pure perdere, ma come ha detto TG, formalizza per bene fin qua, nel senso che devi scrivere per bene quali sono passo base, ipotesi induttiva etc.

p.s. Sylvester è un altro simpatico teoremuccio che con un'induzione che fa il tuo stesso errore si dimostra in 2 minuti, altrimenti è un po' più difficile.
viewtopic.php?t=11710&start=0

[gst_113]

Grazie per la dritta, adesso devo pensarci un po' su.
Cmq, se faccio un errore del genere a Cesenatico mi stroncano?

[julio14]

Beh si perché tutta la dimostrazione cade fin dal primo passo... poi dipende da quanto è salvabile, da quanto potrebbe funzionare un approccio simile senza ipotesi induttiva etc., sta un po' alla fantasia e al sadismo dei correttori. Comunque dubito che a cesenatico venga messa una "trappola" del genere, o perlomeno io non l'ho mai vista.