[IMO13 - P2] Apartheid

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

[IMO13 - P2] Apartheid

Messaggio da EvaristeG »

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.
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Re: [IMO13 - P2] Apartheid

Messaggio da acs »

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 :mrgreen: :?: :!:

ps - non sparate sulla croce rossa
Ultima modifica di acs il 30 lug 2013, 23:40, modificato 2 volte in totale.
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: [IMO13 - P2] Apartheid

Messaggio da kalu »

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.
Pota gnari!
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Re: [IMO13 - P2] Apartheid

Messaggio da acs »

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.
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: [IMO13 - P2] Apartheid

Messaggio da kalu »

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?
Pota gnari!
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: [IMO13 - P2] Apartheid

Messaggio da EvaristeG »

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...
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Re: [IMO13 - P2] Apartheid

Messaggio da acs »

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.
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: [IMO13 - P2] Apartheid

Messaggio da EvaristeG »

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.
Albertobucci95
Messaggi: 45
Iscritto il: 12 gen 2013, 15:00

Re: [IMO13 - P2] Apartheid

Messaggio da Albertobucci95 »

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
Chuck Schuldiner
Messaggi: 308
Iscritto il: 11 feb 2012, 14:37
Località: Hangar 18

Re: [IMO13 - P2] Apartheid

Messaggio da Chuck Schuldiner »

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
Testo nascosto:
considera il poligono convesso tale che ogni altro punto stia al sto interno
Poi le configurazioni che verificano l'altro verso della disuguaglianza solitamente prevedono una disposizione molto semplice dei punti
Testo nascosto:
ad esempio a poligono regolare
https://www.youtube.com/watch?v=35bqkTIcljs

Mare Adriatico: fatto
tetto del Di Stefano: fatto
finestra del Verdi: fatto
lavandino del Cecile: fatto
Arno: fatto
Mar Tirreno: fatto
Mar Ionio: fatto
tetto del Carducci: fatto
mura di Pisa: fatto

ho fatto più allo scritto in normale che alla maturità \m/

non aprire questo link

un pentacolo fatto col mio sangue
Testo nascosto:
Immagine
Albertobucci95
Messaggi: 45
Iscritto il: 12 gen 2013, 15:00

Re: [IMO13 - P2] Apartheid

Messaggio da Albertobucci95 »

Mi spieghi meglio il fatto del poligono?
Chuck Schuldiner
Messaggi: 308
Iscritto il: 11 feb 2012, 14:37
Località: Hangar 18

Re: [IMO13 - P2] Apartheid

Messaggio da Chuck Schuldiner »

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.
https://www.youtube.com/watch?v=35bqkTIcljs

Mare Adriatico: fatto
tetto del Di Stefano: fatto
finestra del Verdi: fatto
lavandino del Cecile: fatto
Arno: fatto
Mar Tirreno: fatto
Mar Ionio: fatto
tetto del Carducci: fatto
mura di Pisa: fatto

ho fatto più allo scritto in normale che alla maturità \m/

non aprire questo link

un pentacolo fatto col mio sangue
Testo nascosto:
Immagine
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: [IMO13 - P2] Apartheid

Messaggio da xXStephXx »

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ì?
Chuck Schuldiner
Messaggi: 308
Iscritto il: 11 feb 2012, 14:37
Località: Hangar 18

Re: [IMO13 - P2] Apartheid

Messaggio da Chuck Schuldiner »

oghei
https://www.youtube.com/watch?v=35bqkTIcljs

Mare Adriatico: fatto
tetto del Di Stefano: fatto
finestra del Verdi: fatto
lavandino del Cecile: fatto
Arno: fatto
Mar Tirreno: fatto
Mar Ionio: fatto
tetto del Carducci: fatto
mura di Pisa: fatto

ho fatto più allo scritto in normale che alla maturità \m/

non aprire questo link

un pentacolo fatto col mio sangue
Testo nascosto:
Immagine
acs
Messaggi: 25
Iscritto il: 18 lug 2013, 08:40

Re: [IMO13 - P2] Apartheid

Messaggio da acs »

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.
Rispondi