Uhm lo piazzo qui anche se forse non è la sezione più adatta...
Sia P un poligono regolare con n vertici. Un sottopoligono regolare di P è un sottinsieme di vertici di P con almeno due vertici tale che divide la circonferenza circoscritta in archi uguali. Dimostra che esiste un sottinsieme Q non vuoto di vertici di P tale che la sua intersezione con ogni sottopoligono regolare ha un numero pari di vertici.
Bonus question: Qual è la cardinalità minima di Q?
Bonus question 2: Qual è la cardinalità massima di Q?
p.s. era il POTD su mathlinks pochi giorni fa
p.p.s. le bonus sono OWN e anche carine se non ho segato la dimostrazione xD
p.p.p.s. ci tengo a dire che ho completamente segato la dimostrazione xD
Sub-poligoni regolari (IRAN 2008 round 3)
Sub-poligoni regolari (IRAN 2008 round 3)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Diciamo che un sub-poligono "salta ogni M" se la distanza tra due vertici consecutivi (è ovvio cosa "consecutivo" voglia dire, penso) del sub-poligono è di M vertici del poligono grande; posso dare questa definizione perché la distanza tra due vertici consecutivi è sempre la stessa, in quanto il sub-poligono "divide la circonferenza circoscritta in archi uguali". Ovviamente M|n e M<n
Ora distinguiamo due casi:
1) $ n= p^a $ dove p è primo.
Allora scegliamo un sottoinsieme formato da 2 punti a distanza $ p^{a-1} $; ovviamente $ M|p^{a-1} $; quindi, se uno dei due punti è parte del sub, allora anche l'altro ne è parte. Cioè l'intersezione tra quest'insieme ed il sub è di 2 oppure 0 punti. Inoltre questo insieme è anche di cardinalità minima, perché un solo punto non va bene.
2) n è multiplo di almeno due primi distinti, chiamiamoli p e q
Allora numeriamo i vertici del poligono grande da 0 a n-1 prendiamo l'insieme costituiti dai punti {$ 0, \frac{n}{p}, \frac{n}{q}, \frac{n}{q}+\frac{n}{p} $}. Notiamo che ognuno di questi punti ha un altro punto dell'insieme a distanza $ \frac{n}{q} $ ed un altro a distanza $ \frac{n}{p} $ Allora M divide almeno uno tra $ \frac{n}{p} $ e $ \frac{n}{q} $.
-se non ci sono punti in comune tra il sub e l'insieme ho vinto
-se M divide entrambi quei numeri e c'è un vertice "preso", allora tutti i quattro vertici sono "presi"
-se M divide solo uno di quei numeri e c'è un vertice preso allora ci sono due vertici presi, cioè ho vinto di nuovo.
Inoltre anche in questo caso l'insieme è minimo perché 1 e 3 non va bene come cardinalità nel caso M=1, mentre 2 punti a distanza D non vanno bene nel caso in cui è preso uno dei due vertici è M non divide D (esiste un tale M che divide n, ovviamente, perchè D<n e M ha più di un fattore primo)
Quanto alla cardinalità maxima sto pensando a fare il negativo di qualcosa, ma non ci ho ancora pensato benisssssimo
Ora distinguiamo due casi:
1) $ n= p^a $ dove p è primo.
Allora scegliamo un sottoinsieme formato da 2 punti a distanza $ p^{a-1} $; ovviamente $ M|p^{a-1} $; quindi, se uno dei due punti è parte del sub, allora anche l'altro ne è parte. Cioè l'intersezione tra quest'insieme ed il sub è di 2 oppure 0 punti. Inoltre questo insieme è anche di cardinalità minima, perché un solo punto non va bene.
2) n è multiplo di almeno due primi distinti, chiamiamoli p e q
Allora numeriamo i vertici del poligono grande da 0 a n-1 prendiamo l'insieme costituiti dai punti {$ 0, \frac{n}{p}, \frac{n}{q}, \frac{n}{q}+\frac{n}{p} $}. Notiamo che ognuno di questi punti ha un altro punto dell'insieme a distanza $ \frac{n}{q} $ ed un altro a distanza $ \frac{n}{p} $ Allora M divide almeno uno tra $ \frac{n}{p} $ e $ \frac{n}{q} $.
-se non ci sono punti in comune tra il sub e l'insieme ho vinto
-se M divide entrambi quei numeri e c'è un vertice "preso", allora tutti i quattro vertici sono "presi"
-se M divide solo uno di quei numeri e c'è un vertice preso allora ci sono due vertici presi, cioè ho vinto di nuovo.
Inoltre anche in questo caso l'insieme è minimo perché 1 e 3 non va bene come cardinalità nel caso M=1, mentre 2 punti a distanza D non vanno bene nel caso in cui è preso uno dei due vertici è M non divide D (esiste un tale M che divide n, ovviamente, perchè D<n e M ha più di un fattore primo)
Quanto alla cardinalità maxima sto pensando a fare il negativo di qualcosa, ma non ci ho ancora pensato benisssssimo
Bravo utente misterioso di cui non verrà svelata l'identità 
La mia soluzione era completamente toppata (avevo fatto cagnara di vario genere) ma era molto sullo stile della tua, che però è giusta
Le bonus le avevo inventate quando pensavo di averlo risolto, non essendo così non è detto esista una soluzione "abbordabile" comunque per il minimo è perfetto così Comunque complimenti perchè il problema non era affatto facile, almeno per me, e non so come ti sia venuta in mente la questione degli n/p e n/q; io nonostante mi ci fossi dedicato un bel po non ero arrivato all'intuizione giusta ma ero arrivato a fare a mano il caso n=45 xD
La mia soluzione era completamente toppata (avevo fatto cagnara di vario genere) ma era molto sullo stile della tua, che però è giusta
Le bonus le avevo inventate quando pensavo di averlo risolto, non essendo così non è detto esista una soluzione "abbordabile" comunque per il minimo è perfetto così
Comunque complimenti perchè il problema non era affatto facile, almeno per me, e non so come ti sia venuta in mente la questione degli n/p e n/q; io nonostante mi ci fossi dedicato un bel po non ero arrivato all'intuizione giusta ma ero arrivato a fare a mano il caso n=45 xD...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Uhm... io ho provato a trovare l'errore, non l'ho trovato, chiarisci un po meglio dove toppa il ragionamento...
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
esempio pratico, prendiamo n=30, p=2, q=3 e M=6: M non divide né 15 né 10 e infatti se scegliamo come sottoinsieme i vertici di posizione 0, 10, 15, 25 (come nel claim di abc) il sub-poligono {0,6,12,18,24} avrebbe solo una intersezione con i vertici scelti.
e in generale il problema consiste nel fatto che se n ha almeno tre fattori primi (per es. $ n=p^aq^bd $) scegliendo $ M=p^aq^b $ abbiamo che M è minore di n, divide n, ma non divide nessuno tra $ \frac{n}{p} $ e $ \frac{n}{q} $ e in questo caso il sottoinsieme toppa, appunto, come sopra
spero di essermi spiegato, cmq dimmi se è più chiaro adesso!
(PS in ogni caso ne approfitto per farti i complimenti x gli RMM )
e in generale il problema consiste nel fatto che se n ha almeno tre fattori primi (per es. $ n=p^aq^bd $) scegliendo $ M=p^aq^b $ abbiamo che M è minore di n, divide n, ma non divide nessuno tra $ \frac{n}{p} $ e $ \frac{n}{q} $ e in questo caso il sottoinsieme toppa, appunto, come sopra
spero di essermi spiegato, cmq dimmi se è più chiaro adesso!
(PS in ogni caso ne approfitto per farti i complimenti x gli RMM
)Fabio91
Grazie :)
Uhm... più che giusto il contro-esempio, anche io oggi a scuola avevo trovato lo stesso identico controesempio xD Sembrava così credibile xD
Chissa se si riesce ad aggiustare... il problema torna aperto.
Uhm... più che giusto il contro-esempio, anche io oggi a scuola avevo trovato lo stesso identico controesempio xD Sembrava così credibile xD
Chissa se si riesce ad aggiustare... il problema torna aperto.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
in realtà l'idea base che ai tempi mi aveva portato alla soluzione non è così diversa da quella di abc...
gli elementi fondamentali in effetti ci sono tutti, solo che dato il testo del problema, uno spera (se il problema è decoroso, ma quelli iraniani generalmente lo sono
) che la soluzione sia un insieme di punti "simmetrico" rispetto ai primi che dividono n.
la soluzione di abc propone infatti l'insieme $ (0,\frac{n}{p}) $ se esattamente un primo divide n, e va bene, e poi l'insieme $ (0,\frac{n}{p},\frac{n}{q},\frac{n}{p}+\frac{n}{q}) $ e questo funziona se esattamente due primi dividono n: ora, se k primi dividono n cosa si può fare? mah, faccio che riportare in breve la mia soluzione, anche se veramente in breve..
il claim è che se $ n=p_1^a_1...p_k^a_k $ allora l'insieme di vertici$ S=(f(A_1), ..., f(A_2^k)) $ soddisfa le condizioni richieste, dove gli $ A_i $ sono tutti i $ 2^k $ possibili sottoinsiemi dell'insieme $ (p_1,...,p_k) $ e f è la funzione che associa un certo sottoinsieme $ (p_a,p_b,p_c,...) $ al vertice $ \frac{n}{p_a}+\frac{n}{p_b}+\frac{n}{p_c}+... $ (e il sottoinsieme vuoto a 0)
non resta dunque che verificare che il claim è vero, e per questo basta mostrare:
-innanzitutto che i $ 2^k $ elementi di S sono tutti distinti modulo n (e dunque l'insieme S è realmente composto da $ 2^k $ vertici), ma questo non è così difficile
-infine, che effettivamente ciascun subpoligono di lato d (cioè che "salta ogni d"), con d|n e d<n, ha un numero pari di intersezioni con S: infatti si ha (adesso veramente ) che d|$ \frac{n}{p_x} $ per qualche x. Se dividiamo quindi gli $ A_i $ in 2^(k-1) coppie, ottenute accoppiando un insieme che non contiene $ p_x $ con l'insieme corrispondente che si ottiene aggiungendo al precedente $ p_x $ stesso, abbiamo che i due vertici associati a ciascuna coppia distano $ \frac{n}{p_x} $ e d divide questa distanza; dunque o il subpoligono li prende entrambi, oppure nessuno dei due, e con questo si conclude..
è un po' scritta alla veloce, ma spero si capisca!
gli elementi fondamentali in effetti ci sono tutti, solo che dato il testo del problema, uno spera (se il problema è decoroso, ma quelli iraniani generalmente lo sono
) che la soluzione sia un insieme di punti "simmetrico" rispetto ai primi che dividono n.la soluzione di abc propone infatti l'insieme $ (0,\frac{n}{p}) $ se esattamente un primo divide n, e va bene, e poi l'insieme $ (0,\frac{n}{p},\frac{n}{q},\frac{n}{p}+\frac{n}{q}) $ e questo funziona se esattamente due primi dividono n: ora, se k primi dividono n cosa si può fare? mah, faccio che riportare in breve la mia soluzione, anche se veramente in breve..
il claim è che se $ n=p_1^a_1...p_k^a_k $ allora l'insieme di vertici$ S=(f(A_1), ..., f(A_2^k)) $ soddisfa le condizioni richieste, dove gli $ A_i $ sono tutti i $ 2^k $ possibili sottoinsiemi dell'insieme $ (p_1,...,p_k) $ e f è la funzione che associa un certo sottoinsieme $ (p_a,p_b,p_c,...) $ al vertice $ \frac{n}{p_a}+\frac{n}{p_b}+\frac{n}{p_c}+... $ (e il sottoinsieme vuoto a 0)
non resta dunque che verificare che il claim è vero, e per questo basta mostrare:
-innanzitutto che i $ 2^k $ elementi di S sono tutti distinti modulo n (e dunque l'insieme S è realmente composto da $ 2^k $ vertici), ma questo non è così difficile
-infine, che effettivamente ciascun subpoligono di lato d (cioè che "salta ogni d"), con d|n e d<n, ha un numero pari di intersezioni con S: infatti si ha (adesso veramente
) che d|$ \frac{n}{p_x} $ per qualche x. Se dividiamo quindi gli $ A_i $ in 2^(k-1) coppie, ottenute accoppiando un insieme che non contiene $ p_x $ con l'insieme corrispondente che si ottiene aggiungendo al precedente $ p_x $ stesso, abbiamo che i due vertici associati a ciascuna coppia distano $ \frac{n}{p_x} $ e d divide questa distanza; dunque o il subpoligono li prende entrambi, oppure nessuno dei due, e con questo si conclude..è un po' scritta alla veloce, ma spero si capisca!
Fabio91
Fabio... non solo stesso controesempio, anche stessa idea, ieri leggendo la tua correzione avevo congetturato lo stesso identico claim tuo, poi però non avevo voglia (ne ci credevo tanto) di controllare se funzionasse o meno.
Ora non ho voglia di leggere quanto hai scritto dopo, ma mi fido che funzioni xD Entro oggi o domani lo leggo Complimenti comunque per l'elegante soluzione.
Ora non ho voglia di leggere quanto hai scritto dopo, ma mi fido che funzioni xD Entro oggi o domani lo leggo
Complimenti comunque per l'elegante soluzione....tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
LOL
sìsì, fai pure con comodo
cmq volevo solo aggiungere un'ultima cosa riguardo al problema di minimalità e massimalità: sinceramente non so se esista un modo carino per risolverlo (e neanche se ne esiste uno brutto, in realtà...), ma dopo aver dato uno sguardo all'insieme S di cui sopra sinceramente non nutro molte speranze...
in realtà non è che ci abbia pensato molto (anzi...), anche perché questo problema l'avevo visto tempo fa nel testo originale di mathlinks e ai tempi non mi ero messo minimamente a pensare se l'insieme proposto era "ottimale" o faccende simili; ma in questo caso mi sembra veramente una battaglia persa in partenza e la darei morta lì...
sìsì, fai pure con comodo
cmq volevo solo aggiungere un'ultima cosa riguardo al problema di minimalità e massimalità: sinceramente non so se esista un modo carino per risolverlo (e neanche se ne esiste uno brutto, in realtà...), ma dopo aver dato uno sguardo all'insieme S di cui sopra sinceramente non nutro molte speranze...
in realtà non è che ci abbia pensato molto (anzi...), anche perché questo problema l'avevo visto tempo fa nel testo originale di mathlinks e ai tempi non mi ero messo minimamente a pensare se l'insieme proposto era "ottimale" o faccende simili; ma in questo caso mi sembra veramente una battaglia persa in partenza e la darei morta lì...
Fabio91
Uhm... secondo me invece è dimostrabile che l'insieme S deve avere almeno $ $2^{w(n)} $elementi... un po nello stile di come l'aveva fatto guido... il massimo... quello lo vedo infattibile xD Le bonus esistono semplicemente perchè quando pensai di averlo risolto venivano fuori (tra l'altro il minimo era proprio questo) massimo e minimo facilmente... peccato che la mia soluzione fosse toppata xD
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai