Soluzioni proposte

Soluzione dell'esercizio 1  $(603,144)=9\mathrel{\big\vert}18 = 27-9$ quindi il sistema e` risolubile. Inoltre $9 = (-5) \cdot 603 + (21) \cdot 144$ quindi $27-9= 18 = 9 \cdot 2 = 603 \cdot (-10) + 144 \cdot 42$ quindi $x_0=-6021 = 27 -42 \cdot 144 = 9 -10\cdot 603$ è una soluzione del sistema. Tutte le soluzioni sono allora date da $\{ -6021 + k [144,603] \mid k\in\mathbb{Z}\}=\{ -6021 + k 9648 \mid k\in\mathbb{Z}\}=\{ 3627 + k 9648 \mid k\in\mathbb{Z}\} = \left[3627\right]_{9648}$     

Soluzione dell'esercizio 2 Nella figura 1 c'è la soluzione proposta da Charles M. Schulz.

Figura 1: Una soluzione dell'esercizio 2.

Cerchiamo di trovarne una matematicamente più corretta.

Il problema può essere affrontato nel modo seguente. Prima si dispongono i libri di matematica, quindi per ogni $k=0,\dots,m$ si scelgono $k$ libri di scienze che si dispongono alla loro sinistra mentre i rimanenti si dispongono alla loro destra. Contiamo in quanti modi si possono fare queste operazioni.

Gli $n$ libri di matematica possono essere disposti in $n!$ modi. Fissato $k=0,\dots,m$ i $k$ libri di scienze da porre alla sinistra possono essere scelti in ${m \choose k}$ modi diversi, e questi libri possono essere permutati n $k!$ modi diversi mentre i rimanenti (quelli da mettere alla destra) possono essere disposti in $(m-k)!$ modi diversi. Quindi, fissata una disposizione di libri di matematica, i libri di scienze possono essere disposti in

$$\sum_{k=0}^{m} {m \choose k} k!(m-k)! = \sum_{k=0}^{m} m! =(m+1)m! = (m+1)!$$

modi diversi attorno a quelli di matematica. Quindi il numero totale delle disposizioni del tipo voluto è $n!(m+1)!$.

Nel caso del problema di Piperita Patty il risultato è quindi $3!\cdot5!=6\cdot120=720$.     

Soluzione dell'esercizio 3  Un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d_2$ dovrebbe avere $14$ vertici, un vertice $v$ di grado $13$ (ovvero collegato a tutti gli altri) ed un vertice $u$ di grado $12$. Ne consegue che l'insieme dei vertici collegati ad entrambi questi due vertici ha almeno $11$ elementi. D'altra parte $\deg(u)\ge 2$ e $\deg(v)\ge 2$ e quindi l'insieme dei vertici che ha cardinalità almeno $2$ deve avere almeno $13$ elementi e pertanto al massimo un vertice può avere grado $1$. Ma lo score ha due $1$ e quindi un tale $G$ non può esistere.

Per $d_1$ usiamo il teorema dello score:

$$\begin{array}{lcl} d_1 & = & (1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4,... ... 2, 2, 3, 10) \\ d_1'' & = & (0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2) \end{array}$$

Dato che $d_1''$ è realizzabile come score di un grafo, anche $d_1$ lo è. La costruzione standard produce il grafo in figura.

Figura 2: Il grafo costruito per la soluzione dell'esercizio 3. La configurazione di partenza è data dai vertici $1,2,3,4,5,6,7,8,9,10,11,12$, e dai lati $\{1,2\},\{2,3\}$ che realizza $d_1''$ a cui sono successivamente aggiunti il vertice $13$ ed i lati $\{i,13\}$ con $i=1,\dots,10$ ed infine il vertice $14$ ed i lati $\{i,14\}$ con $i=2,\dots,13$, ottenendo dei grafi, che realizzano, nell'ordine, $d_1'$ e $d_1$.

(1). La risposta è no, dato che qualsiasi grafo $G$ con $\mathop{\rm score}\nolimits (G)=d_1$ ha $14$ vertici e $(1+1+1+2+2+2+2+2+2+3+3+4+11+12)/2=24$ lati, quindi per ogni tale grafo $\left\vert E(G)\right\vert\ne\left\vert V(G)\right\vert-1$.

(2). La risposta è no, dato che i grafi $2$-connessi hanno tutti i vertici di grado almeno $2$, ma in ogni garfo $G$ con $\mathop{\rm score}\nolimits (G)=d_1$ esistono $3$ vertci di grado $1$.

(3). Anche in questo caso la risposta è no. Proviamo che se $\mathop{\rm score}\nolimits (G)=d_1$ allora $G$ è connesso. Infatti sia $v$ il vertice di grado $12$. Sia $w$ l'unico vertce non adiacente a $v$. Per come è fatto $d_1$, $\deg(w)\ge 1$, quindi esiste un vertice $u\ne w$ tale che $\{u,w\}\in E(G)$. Ma allora anche $\{u,v\}\in E(G)$, quindi ogni vertice di $G$ è congiungibile con $v$, da cui la tesi.     

Soluzione dell'esercizio 4 Se per assurdo per ogni $e$ si avesse che $G+e$ è aciclico, allora per il teorema di caratterizzazione degli alberi, $G$ sarebbe un albero, ma allora dovrebbe aversi $\left\vert V(G)\right\vert=\left\vert E(G)\right\vert+1$, e ciò è assurdo.

Osserviamo che se si aggiunge un lato con gli estremi in una stessa componente connessa di $G$, allora dato che questa è un albero, per il teorema di caratterizzazione degli alberi, si ottengono dei cicli. Quindi se si vuole che il grafo rimanga aciclico, bisogna aggiungere un lato con i vertici su due diverse componenti connesse. Proviamo che in tal caso il grafo rimane aciclico. Infatti se ci fosse un ciclo questo dovrebbe contenere il lato $e$ che si sta aggiungendo. Ma ciò significa che i due vertici a capo di questo lato dovrebbero essere congiunti da un cammino in $G$, ma questo è impossibile perché i due stremi stanno su componenti connesse di $G$.

Aggiungendo un lato in questo modo si ottiene un nuovo grafo aciclico, con lo stesso numero di vertici ed un lato in più (e una componente connessa in meno). Si può quindi iterare il procedimento fino a quando il grafo non risulta connesso, ossia fino a quando il numero di lati è pari al numero di vertici meno $1$, ossia per $2$ volte.

Pertanto il massimo numero di lati che si possono aggiungere a $G$ facendolo rimanere aciclico è $2$.