C'era una volta un numero primo $p$. $p$-ppuccetto rosso abitava in un bosco contenente un numero finito di radure e un numero finito di sentieri (bidirezionali) fra esse; potevano esserci più sentieri che collegavano le stesse radure, ma mai nessun sentiero poteva collegare una radura a se stessa (che senso avrebbe?). $p$-ppuccetto rosso conosceva molto bene il bosco, e sapeva che da ogni radura partivano al più $2p-1$ sentieri (provate voi a far uscire più di $2p-1$ sentieri dalla stessa radura!); inoltre, il numero medio di sentieri che uscivano da una radura era più di $2p-2$.
Un giorno, girando per il bosco, $p$-ppuccetto rosso incontrò il lupo cattivo, che le propose una sfida: «Ecco, - disse - tieni questa vernice rossa. Ti sfido a colorare alcuni sentieri in modo che, in qualunque radura io mi trovi, se vedo almeno un sentiero rosso davanti a me (cioè che esce dalla mia radura), allora ne vedo esattamente $p$».
$p$-ppuccetto rosso accettò la sfida (pur di colorare i sentieri di rosso!), e si mise subito al lavoro. Nel frattempo il lupo cattivo raggiunse la casetta della nonna, la sbranò (la nonna) e visse per sempre felice e contento.
Riuscirà $p$-ppuccetto rosso, nonostante il lutto familiare, a prendersi una rivincita sul lupo cattivo colorando i sentieri come da lui richiesto?
EDIT: a causa dell'influsso malevolo del lupo cattivo il testo era sbagliato, ora è corretto.
[L06] Che favola!
Re: [L06] Che favola!
Giusto per capire, anche se il problema è fuori portata, il testo è equivalente a:
Giusto?
Testo nascosto:
Re: [L06] Che favola!
Sì, al più con "multigrafo" al posto di "grafo". Però così togli tutta la dimensione fiabescaRho33 ha scritto:Giusto per capire, anche se il problema è fuori portata, il testo è equivalente a:
Giusto?Testo nascosto:
Re: [L06] Che favola!
Testo nascosto:
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
Albert Einstein
Re: [L06] Che favola!
Chapeau!cip999 ha scritto:Testo nascosto: