Let A and B be 4-sided dice with the below labels, and similarly for the 5-sided dice C and D: $$ \begin{array}{ll} A = [1,2,3,4] & B=[1,6,11,16]\\ C=[0,1,2,3,4] & D=[0,4,8,12,16] \end{array} $$ Notice that adding the rolls of A and D produces a random number between 1 and 20, so that A and D together simulate a d20, or A + D = d20. Similarly, B + C = d20, so $$ \text{d20 }+\text{d20}=(A+D) + (B+C) $$ To get a different labeling, let's shuffle these factors around: $$ \text{d20 }+\text{d20}=(A+C) + (B+D) $$ Rolling B and D together produces a random number in the list $$ E=[1,6,11,16,5,10,15,20,9,14,19,24,13,18,23,28,17,22,27,32] $$ so B + D is equal to a 20-sided die E with these labels. Similarly, A + C is equal to the 20-sided die F featuring the labels $$ F=[1,2,3,4,2,3,4,5,3,4,5,6,4,5,6,7,5,6,7,8] $$ This shows that d20 + d20 = E + F, so E and F are labelings that work.

Let A and B be 4-sided dice with the below labels, and similarly for the 5-sided dice C and D: $$ \begin{array}{ll} A = [1,2,3,4] & B=[1,6,11,16]\\ C=[0,1,2,3,4] & D=[0,4,8,12,16] \end{array} $$ Notice that adding the rolls of A and D produces a random number between 1 and 20, so that A and D together simulate a d20, or A + D = d20. Similarly, B + C = d20, so $$ \text{d20 }+\text{d20}=(A+D) + (B+C) $$ To get a different labeling, let's shuffle these factors around: $$ \text{d20 }+\text{d20}=(A+C) + (B+D) $$ Rolling B and D together produces a random number in the list $$ E=[1,6,11,16,5,10,15,20,9,14,19,24,13,18,23,28,17,22,27,32] $$ so B + D is equal to a 20-sided die E with these labels. Similarly, A + C is equal to the 20-sided die F featuring the labels $$ F=[1,2,3,4,2,3,4,5,3,4,5,6,4,5,6,7,5,6,7,8] $$ This shows that d20 + d20 = E + F, so E and F are labelings that work.

This same method shows that there exist pairs of alternative $n$-sided dice which simulate regular $n$-sided dice, as long as $n$ is composite. The problem is impossible when $n$ is prime, which can be shown using abstract algebra by representing dice as polynomials.