[L06] Che favola!

[Delfad0r]

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.

[Rho33]

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?

[Delfad0r]

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

[cip999]

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ì:

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

[Delfad0r]

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ì:

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!