35. Fratelli dispettosi

[Gottinger95]

Elisa e Gianni sono due fratelli molto litigiosi. Elisa ha comprato un nuovo stampino fiorellino a forma di cerchio di diametro 3 e lo vuole provare su un foglio A3 (33 x 48). Gianni, volendo rovinare il disegno, riesuma il suo vecchio stampino capra satanica, un cerchio di diametro 3. L'inchiostro che gli rimane basta peró solo per 50 stampi.

Dimostrare che, comunque Gianni decida di guastare il disegno, la sorellina avrá sempre lo spazio bianco per provare il suo nuovo stampino.

[karlosson_sul_tetto]

Elisa e Gianni sono due fratelli molto litigiosi. Elisa ha comprato un nuovo stampino fiorellino a forma di cerchio di diametro 1 su un foglio A3 (33 x 48). Gianni, volendo rovinare il disegno, riesuma il suo vecchio stampino capra satanica, un cerchio di diametro 1. L'inchiostro che gli rimane basta peró solo per 117 stampi.

Dimostrare che, comunque Gianni decida di guastare il disegno, la sorellina avrá sempre lo spazio bianco per provare il suo nuovo stampino.

Immagino che "girare il foglio" non valga, giusto?

[Chuck Schuldiner]

riesuma il suo vecchio stampino capra satanica.

Per maggior chiarezza dico di cosa si tratta:

[Gottinger95]

Scusate, scrivevo da cell e mi si è spento mentre modificavo Edito con i dati giusti!

@ Karlosson_sul_tetto: eh ci avevo pensato pur io, ma ho chiamato elisa e mi ha detto che gli stampini capra satanica sono TERRIBILI...l'inchiostro macchia entrambi i lati.

@Chuck Schuldiner: non so come tu faccia a conoscere Gianni, però si, lo stampo è quello. Certo lo potevi mettere nascosto, così che gusto c'è a fare il problema...

[enrico_s]

Se Gianni disponesse i suoi timbri a formare un reticolo fatto da quadrati nei cui vertici ci sono i centri dei cerchi, la distanza tra due cerchi vicini (verticalmente o orizzontalmente) sia 1 e la distanza dai bordi del foglio dei cerchi sia 1 , allora rimarrebbero tanti spazi vuoti in cui la sorella può provare il timbro.
Per fare questa costruzione ha bisogno di $ 2n+1\leq 33 \rightarrow n=16 $ cerchi in ogni riga e $ 2k+1\leq 48 \rightarrow k=23 $ cerchi in ogni colonn, quindi in totale gli servono$ nk=16 \cdot 23=368 $ cerchi, ma lui può farne solo 117 quindi non riesce a completare questa costruzione, che se anche riuscisse a completare non sarebbe sufficiente affinchè si scateni l'ira della sorella

Va bene come dimostrazione?

[enrico_s]

L ho fatto coi dati sbagliati ahahha mi sembrava troppo semplice

[Gottinger95]

Si scusa enrico_s xD Ti ho fatto penare per nulla!

[enrico_s]

Comunque si può fare lo stesso ragionamento e si ottengono 10 cerchi sulle righe e 15 sulle colonne, quindi ne servirebbero altri 100 per essere in una situazione comunque non sufficiente al fine del dispetto

[Gottinger95]

Aspetta, in questo modo hai "impacchettato" (quasi) tutto il foglio, ma in realtà ne servono parecchi di meno per non lasciare nessun cerchio di diametro 3 bianco! Pensa per esempio a una striscia 3k x 3: secondo il tuo ragionamento servirebbero \(k\) cerchi (se ho capito bene il comportamento sui bordi, altrimenti \(k-1\) o \(k-2\)) mentre ne bastano \(k/2\) per indispettire la sorellina!

[xXStephXx]

Puoi mettere qualche hint?
Secondo me questa potrebbe essere una buona colorazione... se solo l'inchiostro finesse dopo $49$ timbrate

Testo nascosto:

Infatti supponendo che ogni cerchio piccolo abbia diametro $3$, si addice bene alle misure del foglio e vengono esattamente $50$ cerchi piccoli. Se almeno uno di quei $50$ cerchi piccoli resta completamente libero Elisa ha vinto. Se invece tutti i cerchi piccoli sono occupati si nota che con una timbrata si può occupare al massimo un cerchio piccolo per volta (i cerchi grandi hanno diametro triplo rispetto a quelli piccoli). Ora prendendo in considerazione l'ultima riga da $6$ cerchi si ha che da quel punto in poi (verso il basso) Gianni può fare al massimo 6 timbrate e probabilmente è proprio grazie al piccolo margine libero sotto la nona riga che Elisa riesce a trovare lo spazio per una timbrata. Però anche se con paint sembra funzionare non lo saprei fare in modo rigoroso. C'è qualche trucco?

[Gottinger95]

Il primo hint è sull'approccio, il secondo è un po' più vicino alla soluzione:

Hint 1:

Testo nascosto:

Semplificare il problema.
Invece di provare che in ogni configurazione in cui metto 50 cerchietti capra mi avanza un cerchietto da 3, mmm...dovrei trovare qualcosa di più pratico. Tipo tipo, riesco a incorporare l'informazione "ci troverò lo spazio libero per un cerchio da 3" nel cerchio con cui ricopro? E se considerassi cerchi di diametro 6 invece che di diametro 3 e riuscissi a dimostrare che avanza sempre un punto bianco?

Hint 2:

Testo nascosto:

Fare i conti.
Se avete provato a fare con il metodo dell'altro hint ma non vi viene, c'è bisogno di ingegnarsi anche un pochito alla fine. Ci conviene che i cerchi si sovrappongano? E che siano staccati? Siamo certi di poter usare proprio tutto tutto il foglio? Oppure forse ci sono dei pezzetti che rimarranno sempre bianchi per il fatto che stiamo usando dei cerchi invece che dei quadrati? Fate qualche conticino e fatevi uscire un 50!

Li ho scritti un po' vaghi per non rovinare il divertimento, ma se sono stato troppo vago da non essermi affatto spiegato, ditemelo.

[Gottinger95]

Visto che nessuno posta la soluzione ed è decisamente passata la scadenza, posto la mia:

Consideriamo 50 cerchi di diametro 6 e cerchiamo di dimostrare che comunque li si dispongano rimane un punto bianco nel foglio. Questo implica la tesi. Per farlo, moltiplichiamo il numero di cerchi (50) per l'area di un cerchio (\(9\pi\) ) per la densità massima che una disposizione di cerchi può assumere (\(\rho = 0.92..\) ), e verifichiamo che questa quantità è minore dell'area del foglio.(EDIT ) Inoltre dobbiamo ritagliare dai bordi \(1.5\)cm, altrimenti se rimanesse un punto bianco sul perimetro avremmo spazio solo per mezzo cerchio, e non uno intero . C'è un modo per trovare \(\rho\): si consideri che la densità massima si ottiene quando i centri dei cerchi formano un reticolo di triangoli equilateri; si divida, in un triangolo equilatero, l'area totale diviso l'area occupata dai cerchi in quel triangolo.

Ritagliando i bordi, la superficie si riduce a:
\(33 \cdot 48 - 2 \cdot 1.5 (33+48)+(1.5)^2 = 1343.25\)
Verifichiamo:
\(50 \cdot 9 \pi \cdot 0.92 = 1300.62 < 1343.25\)
Effettivamente \(50\) non è il massimo, ma è più carino di 51 e 52 e serve comunque di usare la densità ( \( 50 \cdot 9 \pi = 1413.71 > 1343.25\)).

[darkcrystal]

Perché dovresti moltiplicare per $\rho$? In ogni caso, $50 \cdot 9\pi < 33 \cdot 48$ resta vera...

[jordan]

In ogni caso, $50 \cdot 9\pi < 33 \cdot 48$ resta vera...

Mi pare che l'affermazione che $50$ è il massimo tale che la tesi è verificata sia un po'..

[<enigma>]

A parte che il fatto sull'impacchettamento ottimale non è banale e andrebbe dimostrato (o perlomeno dato un link)...

Il punto è che quella è la densità massima, e il reticolo triangolare dà l'impacchettamento migliore, solo sull'intero piano.
In altre parole, se consideri il massimo numero di cerchi che puoi impacchettare in un rettangolo con rapporto tra i lati fissato, e fai poi tendere le dimensioni del rettangolo all'infinito, ti viene che il limite del rapporto è $\pi/2 \sqrt 3<0,91$.
Che però tale reticolo, fissate le dimensioni del rettangolo, dia l'impacchettamento migliore è falso per più o meno qualsiasi dimensione del rettangolo, come puoi vedere dai disegni qua. Inoltre le dimensioni del rettangolo sono abbastanza piccole da rendere difficile aggiustare la soluzione con un ragionamento di media sul bordo-le correzioni che hai sono di ordine $O(\sqrt \ell)$.