Let A and B be 4-sided dice with the below labels, and similarly for the [5-sided dice](http://www.shapeways.com/product/JF6RYWM66/d5-jack-blank?li=shop-results&optionId=40685693) 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.