griglie,test ed animali

[info]

Ecco tre esercizi carini (nel senso che richiedono poca teoria ma ciononostante presentano difficoltà), per i partecipanti di Cesenatico... Così controllo se ciò che ho fatto è corretto ...


1) Presa una griglia quadrata nXn, all'interno della quale ogni numero da 1 a n compare esattamente n volte, si dimostri che esiste una riga o una colonna nella quale ci sono almeno sqrt(n) numeri diversi...

[questi es sono cattivi!. Sol facile da capire, meno facile da trovare, sempre che il mio ragionamento sia corretto]


2) ci sono 8 esercizi che sono stati proposti ad 8 ragazzi. Ogni esercizio è stato risolto da 5 ragazzi. Dimostrare che esistono due ragazzi tali che ogni esercizio è stato risolto da almeno uno dei due.

**** ne aggiungo un terzo che usa un'idea carina (provengono tutti da un elenco di quesiti [privi di sol] on line);

3) in un' isola ci sono dei camaleonti. Al momento ce ne sono 13 rossi, 15 neri e 17 oro. Se due camaleonti di due colori diversi si incontrano, entrambi cambiano colore in quello rimanente. E' possibile che i camaleonti arrivino ad essere tutti dello stesso colore?

[phi]

Proviamo un po' col 2...
Io avrei ragionato così. Tutte le possibili coppie di ragazzi da considerare sono C(8 2)=28. Per ogni esercizio ci sono (solo) 3 ragazzi che non l'hanno risolto. Perciò dobbiamo escludere le 3 coppie che si possono formare con questi ragazzi, che non soddisfano la condizione data. Il massimo numero di coppie che possiamo escludere in questo modo è quindi 3(coppie)*8(esercizi)=24<28. Quindi una coppia che soddisfa la condizione esiste (e, se non ho sbagliato, anche più di una...)
Mah, questa sol è breve per i miei standard...
[OT]
Ah, a proposito di allenamento per Cesenatico, non si può aprire un thread tipo quelli prima di febbraio con tanti begli esercizi e qualcuno che si prende la briga di correggerli? Va be', immagino che gli esercizi non spuntano dal nulla e che correggere le sol dev'essere una bella fatica... però sarebbe bello e utile!
[/OT]

[info]

Mi pare buona, phi! Cmq sono esercizi propedeutici, nel senso che richiedono solo una singola idea da applicare e per forza sono brevi. Anche quello che ho aggiunto è sulla stessa linea... il primo a mio parere è il più ostico.

2- si poteva anche agire in modo "costruttivo" (scrivo solo per proporre un'altra via).

* deve esistere per il principio dei cassetti almeno uno studente che ha risolto un numero di es >=5;

* ammettiamo ne abbia risolti 5. Gli altri 7 si devono dividere gli altri 3 esercizi. Per il principio dei cassetti tra gli altri 7 almeno uno li avrà risolti tutti e 3. Infatti dobbiamo inserire 21 soluzioni in 7 studenti e supposto che uno studente non può risolvere due volte lo stesso esercizio si conclude... analogamente per i casi 6,7...

[thematrix]

per il terzo,bisogna prendere a due a due gli insiemi dei camaleonti rossi,neri e oro,e considerare le loro differenze modulo 3.Poichè queste non cambiano durante i cambiamenti di colore,e non sono pari a zero,i camaleonti non avranno mai lo stesso colore.

[info]

a parte il fatto che il bianco su blu si legge...

ok, trovare un invariante è un classico!... ma è sempre una tecnica da ricordare e tenere presente...

dai ora fate il primo!

[thematrix]

d'oh! e poi io lo vedo grigio...
comunque,per il primo,dovrei aver trovato una strada:
caso 1:n non è un quadrato perfetto.
in questo caso,supponiamo sia possibile fare una griglia con al massimo [sqrt(n)] numeri diversi per ogni riga e ogni colonna.Allora ogni numero comparirà in media in [sqrt(n)]righe e [sqrt(n)] colonne,per un totale di massimo [sqrt(n)]^2 caselle.Poichè [sqrt(n)]^2 < n,si ha l'assurdo.

caso 2:n è un quadrato perfetto.con lo stesso ragionamento,si ottiene che ogni numero comparirà in media in (sqrt(n)-1) righe e (sqrt(n)-1) colonne,per un totale di max (sqrt(n)-1)^2 caselle,che è minore di (sqrt(n))^2 = n caselle,e anche qui si ha l'assurdo.

non son sicuro che vada bene,eventualmente la correggo più tardi

[MindFlyer]

Per cortesia, per facililtare la consultazione del forum, vi chiedo di postare problemi diversi in thread diversi.
Grazie a tutti

[info]

beh Mind non si possono mica fare 30 thread per problemi di questo tipo!
E poi scrivere a caratteri enormi è maleducato ... il galateo dice che equivale ad urlare...

[EvaristeG]

quando info ha ragione, ha ragione

[Simo_the_wolf]

per il 2°: si sono in totale 40 problemi risolti e ovviamente uno degli 8 ne ha risolti almeno 5. Escludiamo questo e i 5 problemi da lui risolti.

1) ne ha risolti esattamente 5: ci troviamo con 3 problemi e 7 persone e ogni problema ha 5 solutori tra questi. Abbiamo 15 soluzioni e 7 persone quindi per i piccioni almeno una persona ha risolto tutti e tre i problems.

2) ne ha risolti più di 6: ci troviamo con 2 problemi e 7 persone e ogni problema ha almeno 4 solutori tra questi. Abbiamo 8 soluzioni e 7 persone e sempre per i piccioni almeno una ha risolto entrambi i problemi

forse è un po' lunghetta ma è elementare..

D'oh..scusa info ma nn avevo viso la sol

[MindFlyer]

beh Mind non si possono mica fare 30 thread per problemi di questo tipo!

Non si possono fare 30 thread per lo stesso problema.
Si dovrebbero fare 3 thread per 3 problemi diversi.

E poi scrivere a caratteri enormi è maleducato ... il galateo dice che equivale ad urlare...

E l'acustica dice che urlare equivale a farsi sentire meglio (visto che questa cosa l'ho già detta e ripetuta).
Ben più maleducato è contravvenire a delle regole insultando le autorità che te lo fanno notare gentilmente.

[info]

guarda, non voglio "avere l'ultima parola" e quindi credo proprio che questo sarà il mio ultimo post... se vuoi rispondere dopo la chiudiamo lì...
Rimango della mia idea che se devo postare 3 esercizi di questo tipo è stupido aprire 3 thread (30 era per dire che se volessi scriverne più di 3 verrebbe fuori un numero spropositato) che si risolverebbero in 2 messaggi ognuno... Ma se devo rispettare le regole per forza vorrà dire che posterò solo le cose che mi interessano particolarmente...
Poi non mi sembra di avere insultato nessuno... il mio ultimo msg era a mio parere una critica costruttiva ed una battuta... in quanto all'autorità, sinceramente non capisco perchè dovrei portare più rispetto ad uno dei mods rispetto a qualsiasi altro utente...

Per concludere potevi lasciare i caratteri cubitali se rimani dell'idea che non sia maleducato... ma a mio padre hanno regalato il galateo versione 2002 e nella parte "internet" riporta esattamente quanto ho detto...

[Boll]

Pare che sia irrisolto, se non è così scusatemi ma non ho ancora letto tutti i post precedenti

3) in un' isola ci sono dei camaleonti. Al momento ce ne sono 13 rossi, 15 neri e 17 oro. Se due camaleonti di due colori diversi si incontrano, entrambi cambiano colore in quello rimanente. E' possibile che i camaleonti arrivino ad essere tutti dello stesso colore?

Ragionamento brutale
Allora, inizialmente, modulo 3, siamo messi così:
1 0 2
proviamo a metterli nel primo blocco avremo
0 2 1
nel secondo
0 2 1
nel terzo
0 2 1
Evviva!!

Dimostrazione formale

Se si potessero avere ad un certo punto tutti camaleonti dello stesso colore, poichè il totale degli camaleonti è invariante ed è 45, dovrebbe essere, detta $ c_i $ la congruenza modulo $ 3 $ del numero dei camaleonti dell'$ i $-esimo colore. Ad un certo puntò dovrà essere $ (c_1,c_2,c_3)=(0,0,0) $ dove non si è tenuto conto dell'ordine. Ora dimostriamo che invece la terna di congruenze rimane sempre $ (2,1,0) $ sempre non tenendo conto dell'ordine. Ragioniamo per induzione, è chiaro che per $ 0 $ mosse (posizione iniziale) la tesi è valida. Ora supponiamo che funzioni dopo $ n $ mosse, quindi avremo ancora la situazione $ (2,1,0) $ . La $ n+1 $-esima potrà essere:
1) Si incontrano $ 2 $ diversi da $ c_1 $, si avrà $ (1,0,2) $
2) Si incontrano $ 2 $ diversi da $ c_2 $, si avrà $ (1,0,2) $
3) Si incontrano $ 2 $ diversi da $ c_3 $, si avrà $ (1,0,2) $
Si è tornati, a meno dell'ordine, nella posizione iniziale, quindi la tesi è provata per induzione e la risposta è NO.

[Marco]

Bello!!!

La soluzione di brutta copia prima e di bella poi. Stupendo!!

Penso che avremo modo di riparlarne.... Stay Tuned.

7 punti per il Boll (ma davvero non ti sei qualificato per l'individuale?)

Ciao. M.

[Boll]

Devi proprio rigirare il coltello nella piaga???? C'è anche qualcuno che ha perso una scommessa (ovviamente io mi scommisi contro) e che non ho ancora visto post Febbraio