What determines the exchange rate of two fiat currencies if the supply of each is known? In this blog post, economist Steve Landsburg posed a question about the value of Bitcoin which he didn't know the answer to.

Imagine a future in which Bitcoins (or some other non-governmental
currency) are widely accepted and easily substitutable for dollars, at
an exchange rate of (say) $X$ dollars per Bitcoin.
Then if there are $M$ dollars and $B$ bitcoins in circulation, the money
supply (measured in dollars) is effectively $M + X B$ .
Money demand is presumably $P D$, where $P$ is the general price level and
$D$ depends on things like the volume of transactions and the payment
habits of the community. (If it helps, we can write $D = T/V$ where $T$ is
the volume of transactions and $V$ is the velocity of money.)
Equilibrium in the money market requires that supply equals demand, so
$M + X B = P D$
Now $M$ is determined by the monetary authorities; $B$ is
determined by the Bitcoin algorithm, and $D$, as noted above, is
determined outside the money market.
That leaves me with two variables ($X$ and $P$) but only one equation.
What pins down the values of these variables?

As he suggests in parenthesis, this isn't a problem specific to Bitcoin, it's a general problem for non-governmental currencies that are perfect substitutes for dollars.
So does anyone know the answer to Landsburg's question?  Are there any models that shed light on what determines the exchange rate $X$ and the price level $P$ in a situation like this?
There isn't any good way to rehabilitate the quantity theory when there are other currencies that are perfect substitutes for dollars - so in that sense, there isn't any answer to Landsburg's question. Indeed, the irrelevance of the quantity theory under perfect substitutability - which has always been theoretically clear - has become a practical reality recently, as reserves become a perfect substitute for other short-term nominal assets once the nominal interest rate hits zero.

That said, I'd make two points.

1. Anything less than perfect substitutability rescues the quantity theory.

Suppose we replace the left side of Landsburg's quantity theory equation with the more general form
$$F(M,XB) = PD$$ where $F$ is a homogenous production function that produces aggregate "monetary services" using money $M$ and bitcoins (with value stated in terms of money) $XB$. 

Landsburg's equation corresponds to the case of perfect substitutes, $F(M,XB) = M+XB$. In fact, there's another assumption that's implicit in Landsburg's formulation, which is that either $X$ is constant over time or, if $X$ varies, the risk-adjusted expected return on bitcoins relative to money is zero: otherwise, you'd strictly prefer to hold one or the other, whichever gives the highest return, given that they have equal transactional value. I'm going to continue assuming that this assumption holds for simplicity - but keep in mind that in a full-fledged dynamic model, allowing returns to differ and individuals to substitute on this basis might endogenously produce the extra equation that Landsburg seeks.

If money and bitcoins have the same returns, then anyone holding them will want to equate the marginal transactional value of the two, setting $F_M=F_{XB}$. This holds for any relative quantities of $M$ and $XB$ in Landsburg's perfect substitutes formulation, which is why he's struggling, but for general (homogenous) $F$ it will only hold for one ratio $M/XB$ of the two. This will pin down relative demand.

For instance, if $F$ is Cobb-Douglas, with $F(M,XB) = M^\alpha (XB)^{1-\alpha}$, then $F_M = \alpha F/M$ and $F_{XB} = (1-\alpha)F/XB$, and equating the two gives us $M/XB = \alpha/(1-\alpha)$. Suppose $\alpha=1/3$. Then we have $XB = 2M$, and it is trivial to solve for $P$ from $M$ and $D$:
$$F(M,XB)=PD\Longleftrightarrow M^{1/3} (2M)^{2/3} = PD\Longleftrightarrow P = 2^{2/3}\frac{M}{D}$$
Cobb-Douglas is just one parameterization I'm using for illustrative purposes, but we'll similarly be able to solve as long as $F$ has a declining marginal rate of substitution between $M$ and $XB$ - which would be true, for instance, if $M$ and $XB$ were almost perfect substitutes, but not quite. Landsburg's case of perfect substitutes is very much non-generic in this sense: it's probably not true that fiat currency and bitcoins will ever be perfect substitutes in absolutely every application.

By the way, the idea that two forms of currency combine in an imperfectly substitutable way to provide overall monetary services isn't just something I made up - you can see assumptions like this in the literature in a number of places, like equation (3) in Ireland (2011).

2. The central bank can pin down the price level in other ways, even without the quantity theory.

The modern view on monetary policy is that what really matters is the central bank's ability to set the short-term interest rate. Traditionally, this has been done by changing the supply of money through open-market operations, but that doesn't need to be the case. Indeed, Woodford's canonical text shows how it is possible to implement monetary policy even in a "cashless" world where there is no demand for money: the central bank simply pays interest on money. (By the way, this result is hard to escape when you try to microfound the "quantity theory" equation by writing down a dynamic, internally consistent model: you realize that the quantity theory operates in general equilibrium via the response of interest rates to money, and that by manipulating interest rates directly we can get the same outcome.)

Indeed, we're moving closer to Woodford's hypothetical world all the time: for instance, one of the options for the Fed when it decides to raise interest rates in the coming months will be to push up the rate of interest on reserves, while keeping its expanded balance sheet intact.

From this viewpoint, Landsburg's observation just isn't very relevant. The central bank is dedicated to price stability, and it'll enforce this by adjusting interest rates in response to deviations of inflation from trend. If it can adjust interest rates through the traditional method of adjusting $M$ via open-market operations, great. But if it can't do this (because we live in Landsburg's world of perfect substitutability), then the central bank will just adjust nominal interest rates by changing the interest it pays on reserves, and ultimately accomplish exactly the same thing.