Newsgroup: it.hobby.enigmi
Titolo: Cerchi, punti e rondelle ...

Siccome siete troppo bravi, vi propongo una cosetta che spero vi impegnerà un po' di più.
Quando lessi questo quesito non sapevo proprio come prenderlo (e non mi illudo di saperlo prendere non conoscendolo) ... mi ricordo che leggendo la dimostrazione rimasi basito dal tipo di ragionamento usato. Bando alle ciance vi lascio al quesito .. tanto immagino che non servirà scrivere la dimstrazione.  
 
 Ciò che si ha:
    1) abbiamo un cerchio con un raggio di 16 unità;
    2) all'interno del cerchio vengono seminati casualmente 650 puntini (nel senso euclideo del termine);
    3) abbiamo a disposizione una rondella il cui raggio più grande misura 3 quello più piccolo 2.
 
Il compito è quello di posizionare ovunque, nel cerchio, la rondella e coprire con il suo anello (quindi non vale il buco) almeno 10 punti disseminati all'interno del cerchio.
 
La domanda è: sarà sempre possibile adempiere a tale compito ? Si ? No ? Perchè Si o Perchè No ?


_____________________
Provo a rispondere di primo acchito con lo spannometro. :-)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
.
Per me e' SI'.
La densita' dei puntini nel cerchio vale 650/Pi/16^2 = 0.808+
Se sono uniformemente distribuiti, la rondella coprira' Pi(3^2-2^2)*0.808 > 12 puntini.
Se non sono uniformemente distribuiti bastera' mettere la rondella dove i puntini
sono piu' densi.
 
Ciao :-)
Livio
 

 Livio
 
 
Direi che mi hai spiazzato ... hai risposto in maniera semplice ad un quesito che ricordavo avere una risposta più arzigogolata ... che abbia sbagliato la domanda ? ... son dovuto andarmi in cerca dell'articolo per capire se avevo posto la questione nella maniera corretta ... in effetti avrei dovuto mettere l'accento sul fatto che in caso affermativo si proceda a dimostrare come trovare quel particolar punto.


___________________
https://s27.postimg.org/pdlor0akz/Rondella_EPuntini.png
 
 
In caso di distribuzione uniforme su lattice quadrato, e' banale osservare che,
centrando la rondella su un punto qualunque, si coprono esattamente 12 puntini.
Si potrebbe pensare che la distribuzione peggiore sia quella di addensare nove
puntini alla volta, in modo tale che la rondella riesca a coprire solo nove di
essi. Ma e' evidente che non e' cosi'. 
 
Un po' di pigrizia :-) mi trattiene dal fare simili considerazioni su lattice
triangolare, che onestamente potrebbe essere il caso peggiore.
 

Le tue risposte sono indubbiamente corrette e per quato mi riguarda inattaccabili.
 
Comunque, giusto per confronto rilascio quella che era la risposta data al quesito da un matematico Canadese Honsberger, il quale ha eseguito una serie di operazioni per la costruzione della dimostrazione, partendo dal fatto di immaginare di centrare 650 rondelle su ogni uno dei 650 punti disposti nel cerchio di raggio 16 unità.
In questa maniera avremmo che tutte le rondelle saranno sicuramente all'interno di un cerchio di raggio 19, in quanto potrebbero esservi alcuni punti che giacciono sulla circonferenza del cerchio di raggio 16 e quindi "sborderanno" da tale cerchio di 3 unità.
Ora l'area della rondella (l'anello) è data dalla differenza tra l'area di un cerchio di raggio tre e uno di raggio due, ossia 5pi(greco).
Se ora sommiamo le superfici di tutte le 650 rondelle (ribadisco tutte all'interno del cerchio da 19 unità)  otteniamo 650*5pi = 3250pi. Naturalmento alcune rondelle saranno in buona parte sovrapposte.
Supponendo, per ora, che nessun punto "seminato" all'interno del cerchio da 16 sia coperto da più di 9 rondelle, in questo caso, la quantità totale di area coperta nel cerchio da 19 non potrebbe essere superiore a 9*(19*19)pi  cioè 9 volte l'area del cerchio più grande, cioè 3249pi.
Siccome 3249pi < 3250pi allora esiste un punto x coperto da almeno 10 anelli di rondella, questo per quello che Honsenberger chiama "il pricipio della colombaia", per cui se costruiamo 9 nicchie per 10 colombi, almeno una nicchia ha più di un colombo.
A questo punto se diligentemente togliamo le 10 rondelle che vanno a coprire il punto x e ne mettiamo una centrata nel punto x, avremo che l'anello della rondella testè posizionata andrà a coprire i 10 centri (punti "seminati") delle 10 rondelle tolte.


_____________
Wow! :-)


__________________________
La dimostrazione e' sicuramente bella.
Pero' dalle simulazioni che sto facendo, si dovrebbe garantire la copertura
di un maggior numero di punti, 12 certamente, forse 14 o anche 15.
Quanti puntini possiamo garantire di coprire con 'sta rondella per qualunque 
loro distribuzione nel cerchio?
 
Insomma, sarebbe carino lavorarci ancora un po'. :-)

 Insomma, sarebbe carino lavorarci ancora un po'. :-)
 
Bhe così di primo acchito direi che possiamo garantire che la rondella possa coprire tutti e 650 i punti ... naturalmente solo nei casi in cui la "semina" casuale faccia in modo che i puntini cadano tutti all'interno dell'anello. 8)
 
A parte la baggianata, penso che tratti di capire, seguendo il ragionamento della dimostrazione, quante rondelle si andranno a sovrapporre per forza.
Ma dalla dimostrazione si vede che ci sono per forza 9 livelli di rondelle ma se provi a ipotizzarne 10 superi di gran lunga il limite di 3250pi per cui solo una distribuzione "densa" ti potrebbe permettere una torretta più alta di rondelle. 


_________________
Penso anch'io che con questa dimostrazione non si vada oltre n=10.
 
Eppure... se lancio a caso la rondella su quel cerchio costellato
a caso dai 650 puntini, il calcolo delle probabilita' mi dice che,
mediamente, copriro' 12.69+ puntini. Se ora posiziono la rondella
con oculatezza e mi accontento di coprire 10 puntini, vuol dire 
che mi piace giocare facile! :-)
 
Ho provato il reticolo triangolare:
 
https://s30.postimg.org/sugax0wk1/Rondella_EPuntini3.png
 
 
Come si puo' vedere non e' difficile, in queste condizioni coprire 
15 puntini. Io penso che questa sia la condizione peggiore perche'
a ogni rarefazione che si provocasse da una parte, corrispoderebbe
una maggiore concentrazione di puntini da un'altra parte, in cui
potremmo posizionare la rondella. 
 
Naturalmente questa e' piu' un'intuizione che un formalismo matematico, 
non credo che nessuno me la accetterebbe come dimostrazione.
 
Che fare, dunque? Beh, visto il ng, intanto potremmo lanciare una
sfida: trovare una distribuzione di puntini con densita' 0.808 dove
la rondella non riesca a coprire 15 puntini.
 
 
Ciao :-)
Livio
 

 la rondella non riesca a coprire 15 puntini.
 
Vedi la domanda che ho fatto sopra.
 


____________________
A me sembra che qualunque tentativo io faccia fuori dal reticolo 
triangolare finisca per darmi soluzioni migliori. Esempio:
 
https://s24.postimg.org/xzxygi02t/Rondella_EPuntini4.png
 
 
Qui ci vorrebbe qualcuno intenzionato a dimostrare il contrario. :-)

 la rondella non riesca a coprire 15 puntini.
 
Butto lì un'idea, se vi pare valida qualcuno potrà impegnarsi in calcoli 
precisi e disegni (che non so fare, ma qui c'è qualcuno che li sa fare molto 
bene! ;) ).
 
Partiamo da un raggruppamento di puntini uniformemente distribuiti in 
un'area circolare di raggio 2 (praticamente il buco della rondella). Se 
posizioniamo la rondella con il buco in corrispondenza esatta del cerchio 
dei puntini, nessuno verrà coperto. Se spostiamo la rondella, arriveremo a 
coprire il massimo possibile quando il suo anello sarà circa in 
corrispondenza del centro del cerchio dei puntini. Qui bisognerebbe saper 
fare i calcoli ma io stimo che verranno coperti al massimo circa un terzo 
dei puntini presenti. Quindi il cerchio potrebbe contenere circa 40 puntini. 
Ipotizziamo altri cerchi simili distribuiti su un reticolo triangolare e 
distanziamoli in modo che quando la rondella si sposta dal punto di massima 
copertura del cerchio iniziale cominci a coprire alcuni puntini dei due 
cerchi vicini del reticolo, in modo da compensare il numero totale e non 
superare mai 14. A che distanza devono essere messi? Se ci limitiamo a 3 
cerchietti , una volta che circoscriviamo questi 3 cerchietti con il cerchio 
contenitore, quest'ultimo che area avrà: da qui potremo calcolare la densità 
e confrontarla con il famoso 0.808.
 
Considerazioni:
- trovare la densità con soli 3 cerchietti di punti è un caso ottimale, non 
è detto che si riesca a fare altrettanto bene con i valori forniti 
all'inizio (650 punti e raggio 16).
- il cerchietto iniziale potrebbe anche avere raggio leggermente superiore a 
2 in modo che la rondella inizialmente copra già 14 punti disposti in 
prossimità della circonferenza. In questo modo si può pensare di inserire un 
maggior numero di punti nel cerchietto pur mantenendo sempre gli stessi 
valori di copertura.
 
Se non me la smontate subito con considerazioni teoriche, temo che qualcuno 
si dovrà mettere a fare calcoli.
 
Ciao.
 
Giorgio
 
 


______________________
Ciao Giorgio!
Io il disegno l'ho fatto:
 
https://s28.postimg.org/3sdjmwvm5/Congettura_Giorgio_Vecchi.png
 
 
Ora faccio i calcoli con lo spannometro, lasciando ad altri il compito, se
vorranno, di affinarli.
 
Il piano sia coperto da cerchi di r=2 coperti di una certa densita' D di puntini,
disposti in modo da formare sul piano un reticolo triangolare. Calcoleremo
la densita' D all'interno dei cerchietti r=2, in modo che la densita' globale 
sul piano sia d=0.808.
 
Li ho disegnati ai vertici di un triangolo equilatero in modo tale che la
rondella in basso, quando copre due cerchietti, li copra con un'area circa
uguale a quella che copre la rondella in alto, la quale interessa solo un 
cerchietto di puntini. Ho stimato quindi il lato del triangolo rosso il
L=8, calcolo ovviamente affinabile.
 
Il triangolo rosso tassellera' il piano e contiene esattamente 1/2 superficie
di un cerchietto r=2. Quindi calcoliamo la densita' D.
 
D = Area_triangolo/Area_cerchietto*d*2 = 3.56+
 
Quindi ogni cerchietto r=2 conterra' Pi*2^2*D = 44.78+ puntini.
 
La rondella in alto coprira' mediamente circa un rettangolo 1x4, cioe' 
4D = 14.24 puntini.
 
Ora bisognera' proprio affinare (o correggere) i miei calcoli. :-)
 
Ricordo che la rondella in una distribuzione uniforme di puntini con
densita' d=0.808 copre mediamente 5Pi*d= 12.69 puntini, quindi questa
sopra esposta sembra una condizione peggiorativa.
 
Ciao :-)
Livio
 

 sopra esposta sembra una condizione peggiorativa.
 
Ciao Livio!
 
Anche io nel frattempo avevo fatto un disegno: 
https://postimg.org/image/skldcq92f/
 
 
I cerchi sono più ravvicinati dei tuoi. Va poi anche detto che il mio 
disegno non rispecchia le mie reali intenzioni: i cerchietti con i puntini 
dovrebbero essere più grandi per fare il modo che la rondella, posizionata 
per coprire il buco, copra sempre anche un certo numero di puntini. Insomma 
l'idea generale è di far in modo che, dovunque sposti la rondella, questa 
continui sempre a coprire mediamente lo stesso numero di puntini. In 
definitiva io sfrutto il buco della rondella per avere un pattern di 
distribuzione dei puntini diverso dalla distribuzione uniforme, che però 
mantenga sempre una copertura costante. Il fatto che i miei cerchi siano più 
vicini mi ha permesso di ridurre il numero dei puntini, ma non so se sia più 
attendibile la distanza che ipotizzo io o la tua! Facendo due conti con la 
disposizione del mio disegno verrebbe una copertura media di 10.x quindi 
direi che sono stato troppo ottimista. Si potrebbe dedurre la misura del 
lato del triangolo in funzione della copertura media, ma è poi da dimostrare 
che la mia congettura relativa alla copertura costante per qualunque 
posizione della rondella sia vera.
 
Ma ammesso anche che sia vera, il problema è sempre lo stesso. Questi 
puntini bisogna pure disporli in un qualche modo e non se se sia facile 
trovare la disposizione che evita la copertura di 15 o più puntini.
 
Ciao! :)
 
Giorgio
 


________________________
Nel tuo disegno il lato del triangolo che unisce i centri dei cerchietti r=2
diventa L = 8*cos(30) = 6.928
 
La densita' D all'interno dei cerchietti:
 
D = 6.928^2*sqr(3)/4 / (Pi*2^2) *d*2 = 2.67
 
che corrisponde a P1*2^2*D = 33.5 puntini per cerchietto
 
La posizione piu' favorevole alla copertura dei puntini diventa quella
disegnata qua:
 
https://s27.postimg.org/avmgqw49f/Congettura_Giorgio_Vecchi2.png
 
 
dove un calcolo grafico approssimato da' una copertura media di 14.9
puntini contro quella di 12.69 dei puntini uniformemente distribuiti
nel piano. Anche in questo caso, quindi, mi sembra che siamo in una 
situazione peggiorativa.
 
Ciao :-)
Livio
 

 situazione peggiorativa.
 
Sì, a parte i calcoli, anche a occhio si vede che spostando la rondella in 
varie direzioni la copertura totale non rimane costante, il che coincide con 
avere distribuito i puntini in modo non uniforme, quindi peggiorando la 
situazione.
 
L'unica altra cosa che mi viene in mente, per come è proposto il problema, è 
sfruttare il fatto che il cerchio grande ha un confine e lì si potrebbe 
concentrare un maggior numero di puntini. L'idea è che la rondella per 
coprire eventuali gruppi di puntini lungo la circonferenza deve uscire dal 
bordo, quindi si può compensare lo spazio vuoto coperto dalla rondella con 
una maggiore concentrazione di puntini in prossimità del bordo. Questo 
ridurrebbe la densità media per la rimanente area del cerchio. Di quanto? 
Presumo poco... ;)
 
Ciao.
 
Giorgio
 


__________________________
https://s24.postimg.org/q3ysg5izp/Congettura_Giorgio_Vecchi5.png
 
 
In FIG.1 ci sono soli 31 punti per cerchietto a distanza 8cos(30), per una
densita' media di 0.745 (< 0.808). Come si vede non c'e' nessuna difficolta'
a coprire 15 punti.
 
In FIG.2 e' evidente che addensando i punti sulla circonferenza, se ne possono
sempre comprire piu' della meta'.
 
In FIG.3 c'era una mia idea: essendo 15 dispari, se faccio un reticolo di
punti ravvicinati a coppie, magari devo fermarmi a 14. Niente da fare: in
entrambi i casi di reticolo triangolare e quadrato, riesco sempre a coprire
16 punti.
 
---
 
Io azzarderei una generalizzazione della congettura. :-)
 
"Se su un piano sono distribuiti uniformemente punti euclidei con densita' d
e una figura geometrica (qualunque? convessa?) copre N di questi punti, la 
stessa figura geometrica sara' in grado di coprire N punti per qualsiasi 
distribuzione casuale o periodica dei punti sul piano, a parita' di densita' d."
 
Purtroppo con "qualunque" non funziona perche' basta fare una figura filiforme
o vermiforme e per alcuni pattern non funziona. Se invece uso figure convesse,
c'e' subito un caso che non funziona: un triangolo che copra esattamente tre 
punti sul reticolo triangolare non riesce a fare altrettanto su un reticolo
a coppie come in fig.3.
 
Che la rondella abbia proprieta' particolari? :-)
 
Ciao :-)
Livio
 

 Che la rondella abbia proprieta' particolari? :-)
 
Ciao Livio.
 
Riguardo a figura 1, come dicevo, bisognerebbe che i cerchi di puntini 
fossero più grandi (con uno stesso numero di puntini sempre distribuiti 
uniformemente) in modo da permettere alla rondella di coprire 14 punti anche 
quando rondella e cerchietto sono concentrici. Ma, sempre come dicevo, non 
penso che risolva nulla.
 
Riguardo a figura 2, intendevo non il cerchietto di puntini ma il cerchio 
grande dato dal problema (quello di 16 di raggio). E' lungo la sua 
circonferenza che addenserei i puntini. Anche ammesso che si riesca a 
rosicchiare qualcosa, non è comunque una soluzione generalizzabile.
 
Secondo me la proprietà particolare della rondella è di essere circolare, 
altre forme ti permettono di giocare sulla rotazione. Penso che un cerchio 
di uguale area si comporterebbe allo stesso modo.
 
Ciao.
 
Giorgio
 

 rosicchiare qualcosa, non è comunque una soluzione generalizzabile.
 
_________________________
Si'. Ho provato ad addensare i punti sulla circonferenza r=16 + su una 
circonferenza r=10 + su una zona centrale r=4 e densita' 0.6.
Si ottiene una copertura di 17..18 punti che non fa promettere nulla
anche con qualche piccolo rosicchiamento.
 
Io mi arrendo qua. :-)
 
Ciao :-)
Livio