liceo Dini

[colin]

Sempre nel liceo U.Dini ci sono più di 6 studenti.
<BR>Dimostrare che ce ne sono almeno tre che si conoscono o almeno tre che non si conoscono.

[massiminozippy]

Questa \"dovrebbe\" essere più fattibile.

[lordgauss]

In realtà la tesi vale anche per esattamente sei persone.
<BR>Questo e le sue generalizzazioni sono ormai problemi classici, proposti anche alle vecchie IMO. Una trattazione accurata si trova nell\'Engel; se vi interessa, dopo che qualcuno posterà la soluzione dell\'esercizio in questione, potremo approfondire la questione.

[colin]

è vero ho sbagliato a scrivere...
<BR>

[ale86]

Se tutti, o tutti tranne uno se il numero totale di persone è dispari, conoscono una sola persona, allora si vengono a formare delle coppie. Presa una persona per coppia, queste sono almeno tre e non si conoscono.
<BR>Se c\'è una persona che conosce 3 persone o più, queste non si possono conoscere tra di loro.
<BR>Se una sola persona conosce 2 persone, queste 2 persone non si conoscono. Prendendo una persona tra quele rimaste, si forma un gruppo di 3 persone che non si conoscono.
<BR>Se più persone conoscono 2 persone, non ci può essere una coppia tra i rimanenti per il motivo del caso precedente. Ciò equivale a dire che si forma una specie di \"catena\". Prendendo una persona sì e una no, esse sono almeno tre e non si conoscono.

[alberto]

reinterpretazione: abbiamo un grafo completo di sei vertici (per ogni coppia di vertici c\'è un collegamento) colorato in rosso e blu (colegamento rosso significa \"conosce\", collegamento blu significa \"non conosce\"),dimostriamo che esiste un triangolo monocromatico. prendiamo un qualsiasi studente del liceo dini (vertice A del grafo), da esso partono esattamente 5 collegamenti con altrettanti studenti. ora siamo sicuri che almeno tre di questi collegamenti (facciamo AB,AC e AD) sono di uno stesso colore....facciamo rosso. ora nessuno dei segmenti BC,CD e DB può essere rosso...o si avrebbe un triangolo monocromatico rosso di vertici A e i 2 vertici del segmento rosso.
<BR>allora tutti i tre segmenti evono essere blu: si ha comunque un triangolo monocromatico blu.
<BR>...ora voglio sentire la trattazione accurata di Mr. Engel <IMG SRC="images/forum/icons/icon_smile.gif">

[alberto]

uff...arrivo sempre in ritardo....sarà questa ----- di influenza...
<BR>beh... ora per esercizio provate a fare questo (IMO non so che anno) un grafo completo di 17 vertici è colorato in rosso giallo e blu. dimostra che esiste un triangolo monocromatico

[ale86]

Penso di aver sbagliato qualcosa, perchè mi sembra troppo facile per le IMO...
<BR>Comunque: prendendo un vertice qualsiasi, da esso partono 16 collegamenti, per cui ce ne sono almeno 6 dello stesso colore. Consideriamo il grafo formato da sei degli estremi di questi collegamenti escluso il punto di partenza. Nessun segmento in questo grafo può essere del colore iniziale, per cui si ritorna al caso del grafo di sei vertici e due colori.

[alberto]

rilassati...niente di sbagliato... non è detto che tutti i problemi IMO siano mostruosamente difficili...
<BR>non vorrei andare fuori argomento, ma giusto sabato, durante una interessantissima lezione di storia, ho trovato questo(IMO 1962/1):
<BR>trova il più piccolo numero che finisca per 6 tale che, se sposti l\'ultimo 6 all\'inizio del numero, il numero di partenza è moltiplicato per 4.

[ale86]

Esiste?

[Maus]

Uhm...questo problema mi ha ricordato un esercizio del gruppo tutor (marzo 1998, n°6), che ho fatto tempo fa, e, se la memoria non m\'inganna, il numero cercato esiste eccome e non è nemmeno troppo difficile trovarlo. comunque ci ripenserò su e vedrò cosa si può fare. Ciao

[XT]

Ehm...che cosa sono le IMO? <IMG SRC="images/forum/icons/icon_cool.gif">

[Maus]

Sono le Olimpiadi Internazionali.
<BR>
<BR>Alura...il numero cercato dovrebbe essere 153846. Lo ricostruiamo partendo dall\'ultima cifra. Questa dovrà essere necessariamente 4, in quanto se 6 è la cifra delle unità del numero originale, 4*6=24 (non considerando le decine). Ora passiamo alla penultima cifra. Per il ragionamento di cui sopra (46*4=184, ignorando stavolta le centinaia) essa sarà pari a 8. Ripetiamo lo stesso procedimento, che ha evidentemente fine non appena arriviamo ad una cifra uguale a 6 (che abbiamo cancellato alla fine del numero originale e posto all\'inizio). In tal modo si perviene a 153846. In effetti 615384=4*153846.
<BR>
<BR>D\'altronde si può dimostrare che non può esistere un tale n con numero delle cifre minore o uguale a 5. Infatti, indicando con m il numero delle cifre di n, si ha
<BR>4*(10^(m-1)*a_(m-1)+10^(m-2)*a_(m-2)+...+6)=6*10^(m-1)+10^(m-2)*a_(m-1)+...+a_1.
<BR>Con qualche passaggio si ricava
<BR>
<BR>39*(10^(m-2)+10^(m-3)+...+a_1)=6*10^(m-1)-24
<BR>
<BR>Il secondo membro non è mai divisibile per 39 per m<6.
<BR>
<BR>Spero di essere stata esauriente. Ciao a tutti <IMG SRC="images/forum/icons/icon24.gif">

[ale86]

azz... Troppo tardi. Se non mangiavo arrivavo prima io.
<BR>4x=(x-6)/10+6*10^n
<BR>da cui:
<BR>x=(2*(10^(n+1)-1))/13, quindi bisogna trovare un valore di 10^(n+1)-1 naturale. Il primo si ha per n=5 e sostituendo si trova, appunto, 153.846.

[DD]

La trattazione che mr Engel fa del problema specifico è identica alla tua perfino nella scelta dei colori! La trattazione generale la lascio a lordgauss o a me ma quando ho più tempo (o a chiunque altro sappia e abbia voglia).
<BR>
<BR>IMO 1962/1: direi che esiste.
<BR>Dev\'essere 4*(10a+6)=6*10^([loga]+1)+a ---> 13a=2(10^([loga]+1)-4) ---> 13|10^n-4, dove n=[loga]+1. Scorrendo i resti mod 13 di 10^n si vede che il più piccolo n per cui il resto è 4 (che si annulla col -4 che segue) è 5. In effetti, 13*7692=99.996 e ci va bene perché [log7692]+1=4+1=5. Da cui la soluzione 153.846*4=615.384