4
$\begingroup$

Problem: Given that you have n different characters, find the least length needed for a string of characters to contain all possible pairs from those n characters with the order of pairs not mattering, that is, ab is the same as ba.

I'm having trouble trying to make a general approach to the problem.

Examples: With the letters a, b, c, so n = 3: one the strings with the least length containing all possible pairs (ab, bc, ac) would be 'abca' (which has ab, bc, and ca which is equal to ac). So the least length needed is 4.

I also solved this for n = 6, so with letters a, b, c, d, e and f: one the strings with the least length containing all possible pairs (ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef) would be 'abcadeafbdcefcebfd'. So the least length needed is 18.

I currently don't know how to prove these are the least lengths needed, and also don't know how to approach this in a general manner. I would gladly appreciate it if someone could give me some insight on how to solve this.

Sorry if my english isn't good enough to translate the problem, I've tried my best. Thanks everyone.

$\endgroup$
1
  • $\begingroup$ Please upvote and accept my answer if you found it useful. For the latter click the tick on the left of my answer. $\endgroup$ Commented Oct 7, 2022 at 16:23

1 Answer 1

5
$\begingroup$

Since the order does not matter and we are dealing with pairs, we can translate the problem to graph theory – each vertex corresponds to a letter and each edge to the pair of letters associated with its endpoints. Then the problem becomes (essentially) the route inspection problem on $K_n$ (recall that $K_n$ has $\frac{n(n-1)}2$ edges):

  • If $n$ is odd there is an Eulerian cycle using all $\frac{n(n-1)}2$ edges exactly once. The shortest string has $\frac{n(n-1)}2+1$ letters.
  • If $n$ is even at least $\frac n2-1$ edges must be added for an Eulerian path (only two odd vertices), so the shortest string has $\frac{n(n-1)}2+\frac n2=\frac{n^2}2$ letters. (Adding fewer edges won't work since each new edge removes at most two odd vertices, with $n$ odd vertices initially.) For example, a shortest string for $n=4$ is $acdabdcb$.
$\endgroup$
2
  • $\begingroup$ Using the characterisation of graphs with Eulerian paths isn't exactly what I'd call "trivial". Elementary, certainly, but not really trivial. Also, for even $n$ there is the fact that we aren't actually interested in solving the true route inspection problem on the full augmented complete graph, so a small argument is needed to prove that the answer that falls out at the end is actually the answer we're interested in. $\endgroup$
    – Arthur
    Commented Oct 7, 2022 at 15:21
  • $\begingroup$ Hi Parcly, I love the elegance of your answer, it definitely helped me. I would like to know if you think that there is a way to solve this without resorting to graph theory or any non-trivial kind of solutions, with non-trivial I mean a solution that you can arrive to with simple combinatorics. Also, is there a way to do this solution visually with graph theory? If there is, I'd love to see your attempt at drawing it. I'll wait for your answer with great expectations. Thank you. $\endgroup$ Commented Oct 8, 2022 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .