Problemino base $2^p$
Non sapevo se postarlo in informatica, ma mi sembra piu' matematico che informatico... cmq e' interessante come applicazione alle funzioni hash
Supponiamo di avere due numeri di $n$ cifre $x=x_{0}x_{1}...x_{n}$ e $y=y_{0}y_{1}...y_{n}$ e consideriamo la loro rappresentazione in base $2^p$, chiamiamola $x_{2p}$ e $y_{2p}$.
Dimostrare che se $y$ e' una permutazione delle $x_{i}$ cifre di $x$ allora $x_{2p} = y_{2p}$ $mod {2^(p-1)}$
Supponiamo di avere due numeri di $n$ cifre $x=x_{0}x_{1}...x_{n}$ e $y=y_{0}y_{1}...y_{n}$ e consideriamo la loro rappresentazione in base $2^p$, chiamiamola $x_{2p}$ e $y_{2p}$.
Dimostrare che se $y$ e' una permutazione delle $x_{i}$ cifre di $x$ allora $x_{2p} = y_{2p}$ $mod {2^(p-1)}$
Risposte
errata corrige:
per rappresentazione in base $2^p$ di $x$ e $y$ intendo $x_{2p}=x_{n}(2^p)^n + x_{n-1}(2^p)^(n-1) + ... + x_{1}(2^p) + x_{0}$ (in altre parole x e y sono gia' in base $2p$)
altra cosa, ho parlato di permutazione delle $x_{i}$ cifre ma cmq possono esserci anche cifre ripetute ad esempio $x=13155$ $y=53115$
per rappresentazione in base $2^p$ di $x$ e $y$ intendo $x_{2p}=x_{n}(2^p)^n + x_{n-1}(2^p)^(n-1) + ... + x_{1}(2^p) + x_{0}$ (in altre parole x e y sono gia' in base $2p$)
altra cosa, ho parlato di permutazione delle $x_{i}$ cifre ma cmq possono esserci anche cifre ripetute ad esempio $x=13155$ $y=53115$
Continuo ad avere seri problemi nel capire il testo...
allora $x$ e $y$ hanno $n$ cifre e sono scritti in base $2^p$,
trasformiamo in base dieci e otteniamo $x_{2p}$ e $y_{2p}$ con numero di cifre rispettivamente $x_{i}$ e $y_{i}$.
Se non questo che cosa è $x_{i}$?
e poi ?
allora $x$ e $y$ hanno $n$ cifre e sono scritti in base $2^p$,
trasformiamo in base dieci e otteniamo $x_{2p}$ e $y_{2p}$ con numero di cifre rispettivamente $x_{i}$ e $y_{i}$.
Se non questo che cosa è $x_{i}$?
e poi ?
Supponiamo che $y$ si ottenga da $x$ tramite lo scambio di due sole cifre, $y_i=x_j$ e $y_j=x_i$ con $i\ne j$.
Allora $x_{2p}-y_{2p}=(x_i-x_j)(2^{ip}-2^{jp})$. Poichè $2^{p-1}|(2^{ip}-2^{jp})$ è $x_{2p}\equiv y_{2p}(\mod 2^{p-1})$.
In generale, sia $y$ ottenuto da $x$ tramite una permutazione qualunque delle sue cifre. Dato che ogni permutazione è prodotto di scambi, esistono $z_0,z_2,\ldots, z_k$ tali che
$z_0=x$
$z_k=y$
e per ogni $r$, $z_{r+1}$ si ottiene da $z_r$ tramite lo scambio di due sole cifre.
Osserviamo che
$y-x = (z_k-z_{k-1})+(z_{k-1}-z_{k-2})+(z_{1}-z_{0})$.
Per quanto provato prima è $z_{r+1}-z_{r}\equiv 0 (\mod 2^{p-1})$, per ogni $r$, pertanto
$y-x \equiv 0 (\mod 2^{p-1})$.
Allora $x_{2p}-y_{2p}=(x_i-x_j)(2^{ip}-2^{jp})$. Poichè $2^{p-1}|(2^{ip}-2^{jp})$ è $x_{2p}\equiv y_{2p}(\mod 2^{p-1})$.
In generale, sia $y$ ottenuto da $x$ tramite una permutazione qualunque delle sue cifre. Dato che ogni permutazione è prodotto di scambi, esistono $z_0,z_2,\ldots, z_k$ tali che
$z_0=x$
$z_k=y$
e per ogni $r$, $z_{r+1}$ si ottiene da $z_r$ tramite lo scambio di due sole cifre.
Osserviamo che
$y-x = (z_k-z_{k-1})+(z_{k-1}-z_{k-2})+(z_{1}-z_{0})$.
Per quanto provato prima è $z_{r+1}-z_{r}\equiv 0 (\mod 2^{p-1})$, per ogni $r$, pertanto
$y-x \equiv 0 (\mod 2^{p-1})$.
quindi e' per induzione sul numero di scambi di due cifre... ingegnosa 
io avevo provato con le classi dei resti ma mi sono accorto che ho fatto un errore... dopo ci ripenso
io avevo provato con le classi dei resti ma mi sono accorto che ho fatto un errore... dopo ci ripenso
"vl4d":
quindi e' per induzione sul numero di scambi di due cifre... ingegnosa
Non è prorpio per induzione...diciamo, dato che la proprietà vale per uno scambio, allora vale anche per il prodotto di un numero (finito) di scambi (e quindi per ogni permutazione).
Dimostrare che se $y$ e' una permutazione delle $x_{i}$ cifre di $x$ allora $x_{2p} = y_{2p}$ $mod {2^(p-1)}$
chiedo scusa, ho sbagliato a digitare... sarebbe :$mod {2^(p)-1)}$ e non $mod{2^(p-1))}$
la mia dimostrazione era con questo problema ed e' per quello che poi pensavo di averla sbagliata... in ogni caso ho preso le classi di resto modulo $2^p-1$ di $x_{2p}$ e $y_{2p}$ e sfruttando il fatto che $[x_{i}(2^p)^i]_{2^p-1} = [x_{i}]_{2^p-1}[1]_{2^p-1}$ si arriva quasi subito alla tesi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo