7
$\begingroup$

Inspired by my struggles with this puzzle.

In that puzzle, I needed to mix two words, meaning blend them together without changing the order. For example, "ab" mixed with "cd" would give us 6 new words: 'abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab'.

Now, if we have a common letter, there would be repeated words, and we want to eliminate those. For example, "ab" mixed with "acd" would give us 7 words: 'aabcd', 'aacbd', 'aacdb', 'abacd', 'acabd', 'acadb', 'acdab'.

This got me thinking about the combinatorics problem: How would we work out that "ab" and "acd" has 7 mixtures without just listing them out and counting them?

So the puzzle is this:
1. Calculate "by hand" the number of mixtures of "evince" and "decor".
2. Explain the methodology you used. There is a neat tweak on a standard method that gets the answer out.

Note: "By hand" doesn't literally need to be by hand. What I'm looking for is any non-brute-force method, ie doesn't involve listing them out and counting them.

$\endgroup$
  • 1
    $\begingroup$ Gah, I'm so close yet so far away. The breakthrough is right there, lol. $\endgroup$ – Brandon_J Sep 6 at 18:09
  • $\begingroup$ I'll give a hint in a day or two if needed. It probably won't be though. You got this! $\endgroup$ – Dr Xorile Sep 6 at 18:51
  • 1
    $\begingroup$ Looks like @ArnaudMortier got it before me. Nice answer, and nice puzzle! $\endgroup$ – Brandon_J Sep 6 at 20:18
  • $\begingroup$ @Brandon_J Sorry I hadn't seen that you were on it. Better luck next time! $\endgroup$ – Arnaud Mortier Sep 7 at 20:34
  • $\begingroup$ @ArnaudMortier No worries; I'd had to step away from the puzzle anyway. Good luck to you, too! $\endgroup$ – Brandon_J Sep 7 at 21:18
6
$\begingroup$

The answer is

358.

First, we calculate the number of blendings where the $e$'s and $c$'s are labelled ($e_1$, $e_2$,...). Then we will count the number of such words where two $e$'s or two $c$'s are next to each other and subtract it accordingly.

The total amount of letters is $6+5=11$. To produce a blending all you need to choose is which $5$ of $11$ placeholders are going to contain the letters of the word $decor$. Therefore the number of blendings is ${11\choose 5}=462$. This combinatorics technique is commonly known as the stars and bars trick.

Now

In how many blendings does the last $e$ of evince stand next to the $e$ of decor? You have to choose where the $d$ of decor is: $6$ options, and you have to choose the relative order of the two $e$'s: $2$ options. $12$ blendings in total, in other words that is $6$ blendings that we counted twice.

Similarly

To build a word where the first $e$ of evince is next to the $e$ of decor, we have no choice about the $d$, we have two options as to the relative order of the $e$'s, and we have to build a blending of $cor$ and $vince$. By the stars and bars formula, there are ${3+5\choose 3}=56$ blendings that were counted twice.

Finally

To get the $c$'s next to each other we need to choose a blending of $de$ and $evin$: ${2+4\choose 2}=15$, and independently a blending of $or$ and $e$: ${2+1\choose 1}=3$. That's $3\times 15=45$ blendings in total. So the answer would be $$462-6-56-45=355.$$

Wait a minute.

What about those blendings where both $c$'s and $e$'s are next to each other?

E.g. we initially counted $$d\color{red}{e_1e_2}vin\color{red}{c_1c_2}e_3or - d\color{red}{e_2e_1}vin\color{red}{c_1c_2}e_3or - d\color{red}{e_1e_2}vin\color{red}{c_2c_1}e_3or - d\color{red}{e_2e_1}vin\color{red}{c_2c_1}e_3or$$ for four blendings instead of just one. And then we said:

Hey! we counted $d\color{red}{e_1e_2}vin\color{green}{c_1c_2}e_3or - d\color{red}{e_2e_1}vin\color{green}{c_1c_2}e_3or$ for two words instead of just one, let's take out one from our count.
Hey! we counted $d\color{red}{e_1e_2}vin\color{green}{c_2c_1}e_3or - d\color{red}{e_2e_1}vin\color{green}{c_2c_1}e_3or$ for two words instead of just one, let's take out one from our count.
Hey! we counted $d\color{green}{e_1e_2}vin\color{red}{c_1c_2}e_3or - d\color{green}{e_1e_2}vin\color{red}{c_2c_1}e_3or$ for two words instead of just one, let's take out one from our count.
Hey! we counted $d\color{green}{e_2e_1}vin\color{red}{c_1c_2}e_3or - d\color{green}{e_2e_1}vin\color{red}{c_2c_1}e_3or$ for two words instead of just one, let's take out one from our count.

So, for this one quadruple of blendings where we should have taken three off our count, we took four off instead. So we need to add $1$ back to our count for every such quadruple. This combinatorics technique is known as the inclusion-exclusion principle. To build such a quadruple, we have no choice about the $d$, no choice about the $vin$, we have to build a blending of $e$ and $or$. There are three options. Therefore the final answer is $$355+3=358.$$

$\endgroup$
  • 1
    $\begingroup$ This was the approach that I was going for, and while I think it is the intended approach, I think it's worth mentioning that in the general case, sometimes this is just as expensive as enumerating all the unique interleaved words. Specifically, when you have lots of repeated/shared characters. For most English words, though, which have few repeated/shared characters, it is significantly fewer steps than the brute force approach. Take for example the strings "aaaaaaaaa" and "aaaaaaaaa". The number of interleaves is 1, but this method (as an algorithm) would require a lot of steps to show that. $\endgroup$ – hdsdv Sep 6 at 19:47
  • 1
    $\begingroup$ @hdsdv Sure, but in the specific example chosen by the OP, the method isn't too expensive. Good point however - always think before diving into computations, that's what I always tell my students :) $\endgroup$ – Arnaud Mortier Sep 6 at 19:50
  • 1
    $\begingroup$ Yes - sorry if I implied otherwise - I think this is the correct solution for the given problem, and in most practical cases. I just always like to think about the pathological cases :) $\endgroup$ – hdsdv Sep 6 at 19:52
  • $\begingroup$ Great job! Thanks for working it out. The method I had is more "puzzle"-y in the sense that it's a simple grid that you fill out using a set of rules. It's an adaption of the method of finding the number of routes from SW corner of a grid to the NE corner going only N and E. Of course, your answer is 100% right, so I will award the tick shortly. $\endgroup$ – Dr Xorile Sep 7 at 21:23
  • $\begingroup$ @DrXorile Thanks! The SW-NE problem is another classic example where stars and bars kill the game. $\endgroup$ – Arnaud Mortier Sep 7 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.