Sigarette su un tavolo

[Studente Anonimo]

Qual è il numero massimo di sigarette che si possono posizionare in equilibrio su un tavolo in modo tale che ciascuna sigaretta tocchi tutte le altre? Non si può piegarle o romperle.

[axpgn]

Tetraedro?

[Drazen77]

Se le metto in piedi, viste dall'alto, ne vedo quattro così:

[Studente Anonimo]

axpgn

Se per tetraedro intendi 4 allora no.

Drazen77

Ma come fanno a toccarsi a due a due? Una è dentro le altre...

[Drazen77]

"3m0o":

Drazen77
[spoiler]Ma come fanno a toccarsi a due a due? Una è dentro le altre...

In che senso "a due a due"?
Nel mio disegno (che era una vista dall'alto) 3 sono in piedi e si toccano tra di loro e la quarta è appoggiata in piedi sopra di loro.
Tutte e 4 si toccano tra di loro.
Rifaccio il disegno in assonometria ortogonale.

[Folpo13]

"Drazen77":
...

Ad occhio mi sembra che sopra le 3 alla base ce ne possano stare altre 3, in una configurazione simile ma leggermente "sfasata". In tutto 6 quindi (?)

Edit:

Ok mi sono reso conto che non può funzionare

[axpgn]

@3m0o

Chissà perché mi è sembrato che un tetraedro avesse 4 spigoli e che si toccassero pure tutti ...

[axpgn]

$7$

[Studente Anonimo]

Drazen77

Non avevo capito che la quarta fosse in piedi alle altre tre, e non capivo ahaha, okay funziona ma 4 non è il massimo.

axpgn

Penso anche io che 7 sia il massimo, meglio di 7 non riesco a farlo, per 1,2,3,4,5,6 e 7 riesco a farlo. Oltre no, ma non sono riuscito a dimostrare nemmeno che 7 sia il massimo quindi non posso risponderti si ma posso risponderti non lo so

Io per dimostrare che 7 è il massimo ho pensato di fare così:

Definizione grafo di una sigaretta:
Ad ogni "struttura di sigarette" sul tavolo (non necessariamente che soddisfano le condizioni del problema) associamo un grafo, dove i vertici rappresentano le sigarette e due vertici sono collegati con un arco se le sigarette si toccano.

Congettura 1:
Un grafo \(S\) associato ad una struttura di sigarette è soluzione dell'indovinello se e solo se è completo e planare o toroidale.

NB: un grafo è planare se può essere disegnato su un piano se può essere disegnato in modo tale che gli archi si intersecano solo nei vertici, in modo simili un grafo è toroidale se può essere disegnato su un toro in modo tale che gli archi si intersecano solo nei vertici.

Proposizione 1:
Il massimo di sigarette è \(7 \) se e solo se la congettura 1 è vera.

Dimostrazione proposizione 1:
Se \(7 \) è il massimo e poiché allora esistono delle soluzioni con 1,2,3,4,5,6 e 7 sigarette e sono dei grafi completi, denotati rispettivamente con \(K_1,\ldots, K_7 \) abbiamo allora che la congettura 1 è vera poiché \(7 \) è il massimo e i grafi \(K_1,K_2,K_3,K_4 \) sono planari e \(K_5,K_6, K_7 \) sono toroidali e non ci sono altre soluzioni oltre a queste.
Se la congettura 1 è vera allora se esiste una soluzione con \(n \geq 5 \) sigarette allora abbiamo che è un grafo completo con \(n\) vertici, \(K_n\), dunque contiene una copia di \(K_5 \) pertanto non è planare per il teorema di Kuratowski, risulta quindi che è toroidale per la congettura 1, ma poiché un grafo \(G\) che è toroidale possiede un numero cromatico \( \chi(G) \leq 7 \) e poiché \( \chi(K_n) = n \) abbiamo che \(n \leq 7 \).

NB: Il numero cromatico è il numero minimo di colori necessari a colorare tutti i vertici di un grafo in modo tale che se due vertici sono collegati con due archi hanno colori distinti. Purtroppo non riesco a dimostrare la congettura 1. Cioè che sia completo è banale, ma che debba essere planare o toroidale... mah...

[axpgn]

[Drazen77]