Let
be a bijective function. Prove that you can find two other bijective functions
,
from
to
such that
,
.
Update (23/03/2008): Solution posted! (show solution)
A solution was written in the comments (in italian), but i will still post the "official" solution because it is short and instructive. Chose an inductive ordering for (for instance ). Suppose now that we have defined and on a finite set such that they are injective and , , and start with . Now we can:
Extend the domain: chose the smallest (w.r.t the ordering) , and define and with and so that and are still injective .We have infinite possible choices for that automatically also determine , and they are all good but a finite number (those that make or no longer injective).Extend the image of : let's chose the smallest , and look for an such that we can define , keeping and injective. Again, we have infinite that we can try ( are all different!), this choice also determines , and only a finite number of them is bad.The same as 2, but with in the place of .After applying any rule the functions will stay injective. Note that if we apply the rule 1 infinite times, we cannot be sure that and are sujective, if we apply 2 infinite times, will be surjective, but possibly not defined everywhere, and similarly for 3 (w.r.t. ). But if we apply all them infinite times as 1,2,3,1,2,3,1... we can be sure that and are defined everywhere and that they are surjective, because any missing value would be definitively caught by the right rule.
5 comments:
Io proverei cosi': preso il set dei primi dispari ovviamente indicizzati {p_i} proietterei il problema su F_(p_i) definendo
m_i := (p-1)/2
u_(p_i)(n) = m_i (n+1) (mod p_i)
v_(p_i)(n) = m_i (n-1) (mod p_i)
Per ogni n si ha
f(n) = u_(p_i)(n) + v_(p_i)(n) (mod p_i)
e qualunque sia f(n) in Z, conoscere
u_(p_i)(n), v_(p_i)(n)
per ogni i che va da 1 a (abbondiamo)
ceiling(log(f(n))^2)
implica conoscere, per il teorema cinese, l'immagine di n, secondo f, in Z. E' dunque possibile definire due applicazioni da Z in Z che sollevano u_(p_i) e v_(p_i) per i che varia nell'opportuno set di indici. In sostanza risolviamo il problema in F_(p_i) (semplice) e poi liftiamo.
E' corretto? -Jack
No, con gli F_p non funziona. Riprovo:
a meno di comporre con l'inversa di f
basta provare che esistono u,v
bigezioni di Z tali che per ogni n
n = u(n) + v(n)
Ovvero che esiste un insieme J in ZxZ
tale per cui
pi_x(J)=pi_y(J)=Z
e per ogni k esiste un solo elemento
(u,v) di J tale per cui u+v = k.
Preso un ordinamento su Z con minimo,
tipo 0,1,-1,2,-2,3,-3,... possiamo
costruire J induttivamente.
Imponiamo (0,0) in J, e il caso k=0
e' a posto. Guardiamo cosa possiamo
legalmente prendere sulla diagonale
u+v=1 e inseriamo in J l'elemento
con norma-1 |u|+|v| minima (se ce ne
sono due prendiamo quello con |u| piu'
piccola).
Cosi' arriviamo a
k=0 -> (0,0)
k=1 -> (-1,2)
k=-1 -> (1,-2)
k=2 -> (3,-1)
k=-2 -> (-3,1)
k=3 -> (-2,5)
k=-3 -> (2,-5)
k=4 -> (7,-3)
k=-4 -> (-7,3)
...
Con J simmetrico rispetto all'origine,
contenuto nel secondo e nel quarto
quadrante. Notiamo che le curve di
livello della norma |u|+|v|
sono ortogonali rispetto alle diagonali
{u+v = k}, e questo dovrebbe bastare
a garantire la suriettivita' su Z
delle proiezioni di J sugli assi, anche
se devo ancora convincere per bene
me stesso.
J{-} = {(u,v) in J con u<17}
J{+} = {(u,v) in J con u>17}
Credo tu abbia dimenticato di dire che richiedi anche che abbia fibra di un solo punto per le proiezioni (a propri potrebbe essere piu' grande). Nei termini del problema stai costruendo il grafico della funzione
In realta' le curve di livello di questa norma sono parallele (e non ortogonali) alle diagonali alle diagonali nel primo e terzo quadrante (ovvero con entrambi e positivi, o entrabi negativi), e ortogonali negli altri due quadranti. In parole povere formano dei quadrati ruotati di 45 gradi, e non mi sembra chiaro come si possa dimostrare usando questa norma che prima o poi vengono presi tutti i valori di .
Credo che con qualche piccolo aggiustamento la tua idea si possa far funzionare, magari scegliendo una "euristica" migliore per far funzionare l'algoritmo, che non sia la norma 1 (non ho verificato, ma sono convinto che se minimizzi la quantita' tutto dovrebbe funzionare nel modo giusto).
J sta tutto nel secondo e nel quarto quadrante; dalla regia mi dicono che il trucchetto di considerare min(|x|,|y|) funziona ed è detto "proprietà del va e vieni"; funziona tuttavia anche la norma-1: supposto che la riga x=37 sia sempre vuota, a patto di andare piuttosto lontano con la norma si ha che la scelta di un punto sulla riga x=37 risulta conveniente rispetto ad ogni altra possibilità, da cui la suriettività; anche perché si ha che P=(u,v) in J implica 37(u+v) < ||P||_1.
Interessante.
Avevo visto che era abbastanza facile dimostrare la surgettività con , ma effettivamente anch'io parlandone con Nicolò mi sono convinto che la norma andava bene e l'algoritmo di Jack sembrava riempire tutto, e che le scelte dovevano essere nel secondo e quarto quadrante.
Mi piacerebbe però sapere perché, ed inoltre non trovo del tutto convincente la tua dimostrazione per , va bene che definitivamente le scelte con sarebbero convenienti, non mi è chiaro perché non possano essere tutte proibite (ovvero non posso prendere con perché è già stato preso, e questo ogni volta).
Ciao!
Post a Comment