OliForum Matematico

Dati nel piano $2013$ punti rossi e $2014$ punti blu, a tre a tre non allineati, trovare il minimo numero di rette per dividere il piano in regioni contenenti solo punti dello stesso colore.

Se i punti non sono allineati a tre a tre, posso vedere (e semplificare) il tutto come una lista di coppie di punti rossi e coppie di punti blu, tranne per un punto rosso che deve necessariamente rimanere da solo (2013 non è divisibile per 2). In tal caso il minimo numero di rette necessarie per assicurare che il piano (e la lista) sia diviso in regioni contenenti lo stesso colore è (2013+2014)/2 = 2013

Tutto troppo banale

ps - non sparate sulla croce rossa

acs ha scritto: (2013+2014)/2 = 2013

Il risultato è esatto (credo), l'unico guaio è che il conto che hai fatto per trovarlo è errato (di poco però), e in più è completamente a caso. Prova a capire dove il tuo ragionamento fa acqua. PS: Il problema è abbastanza arduo.

Questo problema mi incuriosiva, ma più ci pensavo e più mi si complicavano le idee. Poi, nel tentativo di semplificare le cose, ho forse semplificato troppo.
Per ciò che riguarda la divisione a me interessava la parte intera (le rette che dividono il piano). Forse sarebbe stato meglio se avessi scritto:

nrette = ((2013+2014+1)/2) - 1 = 2013 (la prima e l'ultima regione non hanno bisogno di essere divise ulteriormente dal piano)

Se mi dici che il risultato è corretto e lo svolgimento è molto più complesso sono ancora più incuriosito.

Spero che qualcuno dei grandi provi a risolvere il problema e la mia soluzione fuori strada serva da apripista.

Provo a capire cosa hai fatto. Consideri 2013 coppie di punti dello stesso colore (più l'ultimo punto blu), e vuoi mandare 2013 rette in modo da isolare ogni coppia in una sezione di piano. Il problema è che non puoi farlo sempre: i punti sono distribuiti casualmente sul piano e nessuno ti assicura che siano ordinati in modo tale da poter fare ciò che vuoi tu. Mi spiego?

Non ti dirò se il numero è giusto o no. Dovete abituarvi a scrivere una dimostrazione e verificare che quella sia corretta, non vedere se il numero torna.

Piuttosto, posso suggerire di comprendere che 2013 e 2014 sono a caso (in buona misura). Se ho 4 punti rossi e 5 punti blu, che succede? probabilmente in questo caso si riesce a disegnare una configurazione "generica" e si può provare a vedere quante rette servono...

In effetti è cio che avevo fatto. E per quanto ingarbugliassi la matassa, essendo i punti non allineati a 3 a 3, mi sembrava di riuscire sempre a 'semplificare' il tutto in coppie di due punti con lo stesso colore.

Forse è stato un caso e per questo ho detto che era tutto troppo banale.

Beh, caso o non caso, il fatto è questo:
1. non hai scritto una dimostrazione, quindi non possiamo dirti se è giusto o sbagliato
2. può essere che 2013 rette bastino, ma che tu ne possa usare meno, in particolare non hai fornito un esempio in cui servono esattamente 2013 rette.

Ripeto, prova a farlo con 4 e 5 punti e guarda che succede.

Provo a scrivere una dimostrazione, magari imparo qualcosa:
Allora ho pensato che se prendo due punti dello stesso colore posso. Tracciare 2 rette parallele che li isolano da tutti gli altri, tanto non possono essere allineati 3 punti, quindi se isolo tutti i rossi o tutti i blu necessito massimo di 2014 rette, a questo punto dovrei spiegare perchè secondo me è il minimo, credo che sia sbagliato ma ci provo: visto che i punti sono disposti casualmente ogni punto necessita di almeno 2 rette per essere isolato dai punti di altro colore, le due rette possono poi essere sfruttate con massimo 2 punti contemporaneamente quindi il minimo è 2014, correggetemi il correggibile che devo imparare a scrivere queste maledette dimostrazioni

Albertobucci95 ha scritto:Provo a scrivere una dimostrazione, magari imparo qualcosa:
Allora ho pensato che se prendo due punti dello stesso colore posso. Tracciare 2 rette parallele che li isolano da tutti gli altri, tanto non possono essere allineati 3 punti, quindi se isolo tutti i rossi o tutti i blu necessito massimo di 2014 rette, a questo punto dovrei spiegare perchè secondo me è il minimo, credo che sia sbagliato ma ci provo: visto che i punti sono disposti casualmente ogni punto necessita di almeno 2 rette per essere isolato dai punti di altro colore, le due rette possono poi essere sfruttate con massimo 2 punti contemporaneamente quindi il minimo è 2014, correggetemi il correggibile che devo imparare a scrivere queste maledette dimostrazioni

C`é qualcosa che non va nel caso di uguaglianza (che poi estendi a tutte le configurazioni possibili, che è falso), d'altronde la risposta non è 2014...però il tuo metodo è lo stesso che ho usato io e fidati che puoi usare una retta in meno Poi le configurazioni che verificano l'altro verso della disuguaglianza solitamente prevedono una disposizione molto semplice dei punti

Mi spieghi meglio il fatto del poligono?

Albertobucci95 ha scritto:Mi spieghi meglio il fatto del poligono?

Consideri il poligono convesso che racchiude tutto...esiste perché puoi prendere una retta e farla ruotare intorno al tutto usando i vertici come perni, avvicinandola da lontano. Se tutti i vertici di questo poligono sono blu prendi 2 cosi blu consecutivi e li puoi isolare con una sola retta. Poi per le altre 1006 coppie di blu si fa come hai detto tu. Se invece c'è un rosso nel poligono lo isoli con una retta e rimangono 1006 coppie di rossi. Quindi con 2013 rette è sempre possibile.

Per quanto riguarda il caso peggiore:
prendo un poligono regolare con $4027$ vertici e ne coloro alternatamente uno blu e uno rosso.
Dovrei avere che tutti i lati di questo poligono aventi estremi di colore diverso devono essere intersecati da una retta, altrimenti si troverebbero nella stessa sezione (visto che non è possibile separare due punti senza tagliare il segmento che li congiunge... credo...).
Quindi in pratica vanno tagliati tutti i lati eccetto l'unico lato avente entrambi gli estremi blu, ovvero $4026$.
Ma ogni retta che attraversa il poligono entra da un lato ed esce da un altro, quindi può tagliare al massimo $2$ lati. Di conseguenza con meno di $2013$ rette non riesco a tagliare tutti i lati.
Può andare così?

oghei

Ho visto che per aiutarvi nella dimostrazionme ad un certo punto avete tirato in ballo i poligoni.
E' la prassi per questa classe di problemi oppure è qualcosa che vi è venuto in mente per l'occasione?

Perdonate l'ignoranza, stò cercando di capire come fare per 'imbastire' una dimostrazione.