Wikipedia:Reference desk/Archives/Mathematics/2019 November 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 17

MatchDragons and Math. (should have been Merge Dragons)

In the game Matchdragons, the standard merge is 3 objects of tier K gives 1 object of tier K+1. This makes the number of Tier 1 objects to make a Tier N object easy to calculate, 3^(N+1). *BUT* for most objects, the game allows you to be more efficient, also allowing 5 objects of tier K to be combined to make 2 objects of tier K+1. This means for example, that making something of Tier 3 only takes 8(=5+3) Tier 1 objects and making something of tier 4 takes 23 (4*5+3). If the tiers go high enough, the number should get close to 2.5^N, but I'm not sure it ever gets that efficient. Is there any good way beyond trial and error to get the number needed for each tier?Naraht (talk) 19:09, 17 November 2019 (UTC)

@Naraht: It's easier to ask the more general question, "Given N and M, how many Tier 1 objects do I need to make M Tier N objects?" This can be seen as a generalization of the coin problem and the following greedy algorithm should work in this case (and this case only): if f(N, M) denotes the solution to the problem, then $f(N,M)=f(N-1,5M/2)$ for even M and $f(N,M)=f(N-1,5(M-1)/2+3)$ otherwise, with the base case being $f(1,M)=M$, which should yield an $O(N)$ dynamic programming algorithm for the problem. It won't ever be exactly $2.5^{N}$ in nontrivial cases unless you ask for two, rather than one, member of the topmost level.--Jasper Deng (talk) 19:40, 17 November 2019 (UTC)

Err, unless I'm missing something, it only takes 20 tier-1 items to make a tier-4 item, not 23. Combining them all gives 8 tier-2s, which as noted above, gives a tier-4. In fact, if it takes n for a tier-n, then it'll simply take $\lceil (5/2)n\rceil$ for an n + 1-tier. So you get a sequence of 1,3,8,20,50,125,313,783,1958,... Although I do wonder what proportion of these terms are even vs. odd. –Deacon Vorbis (carbon • videos) 19:48, 17 November 2019 (UTC)

(edit conflict) @Naraht: You can actually make something of tier 4 with only 20: make 8 tier 2 objects with them, use these to make two tier 3 objects using the five-for-two rule and the remaining three to make another tier 3 object, for a total of 3 tier 3 objects, then combine those into one tier 4 object. I don't know how you got 23. I've implemented it as a simple Python program:

def matchDragons(N, M = 1):
	assert isinstance(N, int) and isinstance(M, int) and (N > 0) and (M > 0), "N and M must be positive integers"
	if N == 1:
		return M
	if M % 2 == 0:
		return matchDragons(N - 1, 5*(M//2))
	else:
		return matchDragons(N - 1, 5*((M - 1)//2) + 3)

--Jasper Deng (talk) 19:49, 17 November 2019 (UTC)

@Deacon Vorbis: You forgot a term. My program outputs 1, 3, 8, 20, 50, 125, 313, 783.--Jasper Deng (talk) 19:52, 17 November 2019 (UTC)

Fixed . –Deacon Vorbis (carbon • videos) 19:57, 17 November 2019 (UTC)

@Deacon Vorbis: Regarding parity: my program empirically suggests that it's about 50-50 odd and even, never more than about 1% away from 50-50 for N = 1000 or more or so, but a theoretical reason why doesn't come to my mind immediately.--Jasper Deng (talk) 20:12, 17 November 2019 (UTC)

I now wonder if it's possible to use something similar to exponentiation by repeated squaring to reduce the runtime to $O(\log(N))$ using Deacon's formula. Having to take the ceiling each time is annoying though.--Jasper Deng (talk) 21:06, 17 November 2019 (UTC)

Yet another observation: while $2.5^{N}$ is unattainable exactly, for large N, the answer to this problem is much closer to that than $3^{N}$ (For $N=314$, $3^{N}$ is about $10^{129}$. but both of the others are about $10^{124}$). This is to be expected because you will make at most one item of a given tier using three of the tier below, as opposed to the two-for-five rule which dominates for large N.--Jasper Deng (talk) 21:12, 17 November 2019 (UTC)

Extending 1, 3, 8, 20, 50, 125, 313, 783, 1958, ..., I get the approximation 1.283256 × 2.5ⁿ. There's probably not a simple formula since the evens vs. odds seem statistically random. The 1.283256 constant is the sum of an infinite series of the form 1+∑e_n.5×2.5⁻ⁿ where e_n is 0 or 1 depending on whether the previous term in the sequence is even or odd. So the series converges but it seems impossible to determine its exact value without computing all the terms in the sequence. --RDBury (talk) 03:46, 18 November 2019 (UTC)

PS. I've never heard of this game, but I did find some links to Merge Dragon, are they related? --RDBury (talk) 03:50, 18 November 2019 (UTC)

Thank you. Section title updated.Naraht (talk) 17:44, 18 November 2019 (UTC)