[L06] Che favola!

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

[L06] Che favola!

Messaggioda Delfad0r » 07/04/2016, 14:22

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.
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: [L06] Che favola!

Messaggioda Rho33 » 07/04/2016, 17:25

Giusto per capire, anche se il problema è fuori portata, il testo è equivalente a:

Testo nascosto:
Sia $p$ un primo. Ho un grafo finito senza cappi. Da ogni vertice partono al massimo $2p-1$ archi, mentre il numero medio di archi per ogni vertice è $> 2p-2$ . Esiste una colorazione monocromatica degli archi tale che da ogni vertice escano $0$ oppure $p$ archi colorati ?


Giusto?
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: [L06] Che favola!

Messaggioda Delfad0r » 07/04/2016, 17:33

Rho33 ha scritto:Giusto per capire, anche se il problema è fuori portata, il testo è equivalente a:

Testo nascosto:
Sia $p$ un primo. Ho un grafo finito senza cappi. Da ogni vertice partono al massimo $2p-1$ archi, mentre il numero medio di archi per ogni vertice è $> 2p-2$ . Esiste una colorazione monocromatica degli archi tale che da ogni vertice escano $0$ oppure $p$ archi colorati ?


Giusto?

Sì, al più con "multigrafo" al posto di "grafo". Però così togli tutta la dimensione fiabesca :(
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: [L06] Che favola!

Messaggioda cip999 » 07/04/2016, 20:15

Testo nascosto:
$p$-ppuccetto passò un sacco di tempo cercando una colorazione dei sentieri che soddisfacesse le condizioni imposte dal lupo cattivo. Passarono circa $\text{Ackermann}(6)$ minuti da quando aveva iniziato a pensarci, ma non aveva assolutamente nessuna idea: non era nemmeno in grado di claimare che una siffatta colorazione esistesse davvero. Proprio quando ogni speranza sembrava ormai perduta, $p$-ppuccetto rosso si imbatté fortuitamente nel cacciatore, e si rivolse a lui con fare implorante: «Ti prego, cacciatore, dammi un fucile per minacciare il lupo cattivo così che mi sveli la soluzione dell'enigma che mi ha proposto (e anche per ucciderlo, ovviamente)». Ma il cacciatore, che oltretutto era in grado di leggere nella mente e conosceva quindi la sfida lanciata dal lupo a $p$-ppuccetto, le rispose: «Purtroppo non ho un fucile. Posso però donarti questo potente Cannone, con il quale sarai perlomeno in grado di dimostrare che è effettivamente possibile colorare i sentieri nel modo giusto» e, nel dire ciò, porse alla pulzella il Cannone, che recitava più o meno così:
Cacciatore ha scritto:Teorema che serve solo a far venire i problemi fatti apposta per usare questo teorema (e quelli del lupo cattivo), altresì noto come Chevalley-Warning. Siano $q$ un primo, $n$ un intero positivo, $P_1(x_1, \: \dots, \: x_n), \: \dots, \: P_k(x_1, \: \dots, \: x_n)$ polinomi a coefficienti interi in $n$ variabili tali che:
(a) $P_1(0, \: \dots, \: 0) = \cdots = P_k(0, \: \dots, \: 0) = 0$;
(b) $\text{deg}(P_1) + \cdots + \text{deg}(P_k) < n$.
Allora, esiste una $n$-upla di interi $(a_1, \: \dots, \: a_n)$ tale che $P_i(a_1, \: \dots, \: a_n) \equiv 0 \pmod{q}$ per ogni $i = 1, \: \dots, \: k$ e $a_j \not\equiv 0 \pmod{q}$ per almeno un $1 \le j \le n$
.

$p$-ppuccetto rosso, nonostante la nota antipatia che ella nutriva per i primi che si chiamano $q$, accettò volentieri il Cannone e, avendo capito immediatamente come doveva usarlo ($p$-ppuccetto, dopotutto, era piuttosto potente: pur non essendo mai andata alle IMO, si era piazzata per ben tre volte al settimo posto nel PMLTST (Paese Molto Lontano Team Selection Test)), si congedò dal cacciatore e iniziò ad assegnare a ciascuno degli $E$ sentieri del bosco un numero intero compreso tra $1$ ed $E$, in modo che ogni sentiero avesse un numero diverso. Successivamente, per ciascuna delle $V$ radure del bosco (diciamo la $k$-esima) considerò l'insieme $S_k = \{a_{k,1}, \: a_{k,2}, \: \dots, \: a_{k,d}\}$ dei numeri associati ai $d$ sentieri che partivano da quella radura, e costruì il polinomio $\displaystyle P_k(x_1, \: \dots, \: x_E) = \sum_{i = 1}^d x_{a_{k,i}}^{p - 1}$. Ora, si aveva chiaramente $P_k(0, \: \dots, \: 0) = 0$ per ogni $k$; inoltre, essendo il numero medio di sentieri che uscivano da una radura maggiore di $2p - 2$, valeva $\displaystyle \frac{2E}{V} > 2p - 2 \implies V < \frac{E}{p - 1}$, da cui $$\text{deg}(P_1) + \cdots + \text{deg}(P_V) = (p - 1)V < E$$ $p$-ppuccetto aveva dunque tutte le ipotesi per usare il Cannone! In particolare, era in grado di dire con sicurezza che esisteva una soluzione non banale $(a_1, \: \dots, \: a_E)$ del sistema di congruenze $$\begin{cases}P_1(x_1, \: \dots, \: x_E) \equiv 0 \pmod{p} \\ \qquad \qquad \vdots \\ P_V(x_1, \: \dots, \: x_E) \equiv 0 \pmod{p}\end{cases}$$ L'acuta fanciulla si era accorta che, se avesse colorato di rosso l'$i$-esimo sentiero se e solo se $a_i \not\equiv 0 \pmod{p}$, il numero totale di sentieri rossi uscenti da ogni radura sarebbe stato un multiplo di $p$. D'altra parte, da ciascuna radura non partivano più di $2p - 1$ sentieri: pertanto tale numero doveva necessariamente essere $0$ o $p$!
$p$-ppuccetto, che si era esaltata tantissimo per la dimostrazione che aveva trovato, volle subito correre alla casetta della nonna per comunicarle la fantastica notizia. Quando la raggiunse, vi trovò il cadavere della nonna orribilmente mutilato dalle fauci del lupo cattivo, e poi morì.
FINE
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L06] Che favola!

Messaggioda Delfad0r » 07/04/2016, 21:28

cip999 ha scritto:
Testo nascosto:
$p$-ppuccetto passò un sacco di tempo cercando una colorazione dei sentieri che soddisfacesse le condizioni imposte dal lupo cattivo. Passarono circa $\text{Ackermann}(6)$ minuti da quando aveva iniziato a pensarci, ma non aveva assolutamente nessuna idea: non era nemmeno in grado di claimare che una siffatta colorazione esistesse davvero. Proprio quando ogni speranza sembrava ormai perduta, $p$-ppuccetto rosso si imbatté fortuitamente nel cacciatore, e si rivolse a lui con fare implorante: «Ti prego, cacciatore, dammi un fucile per minacciare il lupo cattivo così che mi sveli la soluzione dell'enigma che mi ha proposto (e anche per ucciderlo, ovviamente)». Ma il cacciatore, che oltretutto era in grado di leggere nella mente e conosceva quindi la sfida lanciata dal lupo a $p$-ppuccetto, le rispose: «Purtroppo non ho un fucile. Posso però donarti questo potente Cannone, con il quale sarai perlomeno in grado di dimostrare che è effettivamente possibile colorare i sentieri nel modo giusto» e, nel dire ciò, porse alla pulzella il Cannone, che recitava più o meno così:
Cacciatore ha scritto:Teorema che serve solo a far venire i problemi fatti apposta per usare questo teorema (e quelli del lupo cattivo), altresì noto come Chevalley-Warning. Siano $q$ un primo, $n$ un intero positivo, $P_1(x_1, \: \dots, \: x_n), \: \dots, \: P_k(x_1, \: \dots, \: x_n)$ polinomi a coefficienti interi in $n$ variabili tali che:
(a) $P_1(0, \: \dots, \: 0) = \cdots = P_k(0, \: \dots, \: 0) = 0$;
(b) $\text{deg}(P_1) + \cdots + \text{deg}(P_k) < n$.
Allora, esiste una $n$-upla di interi $(a_1, \: \dots, \: a_n)$ tale che $P_i(a_1, \: \dots, \: a_n) \equiv 0 \pmod{q}$ per ogni $i = 1, \: \dots, \: k$ e $a_j \not\equiv 0 \pmod{q}$ per almeno un $1 \le j \le n$
.

$p$-ppuccetto rosso, nonostante la nota antipatia che ella nutriva per i primi che si chiamano $q$, accettò volentieri il Cannone e, avendo capito immediatamente come doveva usarlo ($p$-ppuccetto, dopotutto, era piuttosto potente: pur non essendo mai andata alle IMO, si era piazzata per ben tre volte al settimo posto nel PMLTST (Paese Molto Lontano Team Selection Test)), si congedò dal cacciatore e iniziò ad assegnare a ciascuno degli $E$ sentieri del bosco un numero intero compreso tra $1$ ed $E$, in modo che ogni sentiero avesse un numero diverso. Successivamente, per ciascuna delle $V$ radure del bosco (diciamo la $k$-esima) considerò l'insieme $S_k = \{a_{k,1}, \: a_{k,2}, \: \dots, \: a_{k,d}\}$ dei numeri associati ai $d$ sentieri che partivano da quella radura, e costruì il polinomio $\displaystyle P_k(x_1, \: \dots, \: x_E) = \sum_{i = 1}^d x_{a_{k,i}}^{p - 1}$. Ora, si aveva chiaramente $P_k(0, \: \dots, \: 0) = 0$ per ogni $k$; inoltre, essendo il numero medio di sentieri che uscivano da una radura maggiore di $2p - 2$, valeva $\displaystyle \frac{2E}{V} > 2p - 2 \implies V < \frac{E}{p - 1}$, da cui $$\text{deg}(P_1) + \cdots + \text{deg}(P_V) = (p - 1)V < E$$ $p$-ppuccetto aveva dunque tutte le ipotesi per usare il Cannone! In particolare, era in grado di dire con sicurezza che esisteva una soluzione non banale $(a_1, \: \dots, \: a_E)$ del sistema di congruenze $$\begin{cases}P_1(x_1, \: \dots, \: x_E) \equiv 0 \pmod{p} \\ \qquad \qquad \vdots \\ P_V(x_1, \: \dots, \: x_E) \equiv 0 \pmod{p}\end{cases}$$ L'acuta fanciulla si era accorta che, se avesse colorato di rosso l'$i$-esimo sentiero se e solo se $a_i \not\equiv 0 \pmod{p}$, il numero totale di sentieri rossi uscenti da ogni radura sarebbe stato un multiplo di $p$. D'altra parte, da ciascuna radura non partivano più di $2p - 1$ sentieri: pertanto tale numero doveva necessariamente essere $0$ o $p$!
$p$-ppuccetto, che si era esaltata tantissimo per la dimostrazione che aveva trovato, volle subito correre alla casetta della nonna per comunicarle la fantastica notizia. Quando la raggiunse, vi trovò il cadavere della nonna orribilmente mutilato dalle fauci del lupo cattivo, e poi morì.
FINE

Chapeau!
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti