Are there any Trainer IDs that have the same Munchlax trees in DPP?

Question

There are 21 different trees. I was just messing with the Cave of Dragonflies generator and was just wondering if any two trainer IDs and Secret IDs produce the same 4 Munchlax as another.

Comments

The Munchlax trees are calculated by finding the remainders of certain numbers when dividing by 21. Remainders are not one-to-one functions, so lots of different numbers can have the same remainder when dividing by 21.

---

Are those 'certain numbers' Trainer IDs or something else?

---

I think they're floor(trainer ID / 256), trainer ID % 256, floor(secret ID / 256), and secret ID % 256.

Answer 1

Yes. You can prove this trivially by recognising that the number of combinations of Munchlax trees (21 choose 4 = 5,985) is less than the number of unique TID/SID pairs (above four million).

Furthermore: Munchlax trees are selected using division and the modulo operation (more info; also explained by TCoD itself), and of course different numbers can have the same quotient or remainder. This is another way to convince yourself there will be clashes between distinct TID/SID pairs.

Comments

Wouldn't it be (21 choose 4) + (21 choose 3) + (21 choose 2) + 21? I think it's possible for one save file to have less than 4 Munchlax trees.

---

I believe it says that some save files can have only 3 Munchlax trees on the Cave of Dragonflies page.

---

As described by Bulbapedia, the game tries to ensure that there will be four different Munchlax trees, so 21 choose 4 is correct (aside from implementation details).
As TCoD alludes, the game's match-checking procedure has a bug where it doesn't check if it has incremented a clashing "tree index" to an index that is already present. (For example, A=4 B=3 C=5 D=3 will set your trees to 4, 3, 5, 4 so you effectively have three trees.) But all of this is auxiliary to the answer for this question.