# Choose 3 strings and output the exact minimum Hamming distance between any pair

Consider $$\3\$$ binary strings of length $$\n\$$ chosen independently and uniformly at random. We are interested in computing the exact expected minimum Hamming distance between any pair. The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Given an input n between 2 and 10, inclusive, consider $$\3\$$ binary strings of length $$\n\$$ chosen independently and uniformly at random. Output the exact expected minimum Hamming distance between any pair.

Output should be given as a fraction.

Your code should run in TIO without timing out.

• Challenges should be self-contained: Please add the definition of Hamming Distance. Jan 31, 2020 at 19:10
• Could you please provide some test cases? Jan 31, 2020 at 20:25
• 0.375, 0.75, 1.125, 1.5234375, 1.93505859375, ...? Jan 31, 2020 at 22:53
• The denominator will be a power of two, so the decimal will terminate. Feb 1, 2020 at 0:42
• @xnor My code may have three loops, but it only iterates over the $n+3 \choose 3$ ways to write $n$ as a sum of four nonnegative integers. For $n=10$ that is 286 cases. Feb 1, 2020 at 1:14

# Pari/GP, 92 90 bytes

2 bytes saved thanks to @Nicolas!

n->sum(a=0,n,sum(b=0,n-a,sum(c=0,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*min(a+b,min(a+c,b+c)))))/4^n


Try it online!

$$f(n) = \frac{1}{4^n} \sum_{\substack{a+b+c+d=n\\a,b,c,d\geq 0}} \binom{n}{a,b,c,d}\min(a+b,a+c,b+c)$$

A more direct brute force approach may be shorter in some languages, but I'm not sure if that's true for Pari. Anyway, it's a shame that Pari's min only accepts two arguments.

I can avoid the min and be about 6 times faster, but the compensating additional code makes it longer. Maybe in another language this is the shorter way. And maybe it is possible to simplify further and get rid of the innermost sum.

n->sum(a=0,n,sum(b=a,n-a,sum(c=b,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*(a+b)*6/(1+(a==b)+(b==c))!)))/4^n


Try it online!

• This is a really elegant mathematical solution!
– user9207
Feb 1, 2020 at 18:04
• Would it be acceptable to place the f(n)= in the header section and save 5 bytes ? Asking as a new code-golfer. Feb 4, 2020 at 15:47
• @Nicolas The remaining part would be a term with n as free variable which is not okay, but I can rewrite it as f=n->... and don't count f=, then the remaining part states the function without binding it to a name. Thanks for reminding me! Feb 4, 2020 at 18:37

# Jelly, 31 bytes

Ḷṗ4S⁼¥Ƈɓ!×Ṗṁ4SƝṂƲ}:!P$}ð€S,4*$}


A monadic Link accepting an integer which yields a pair of integers, [numerator, denominator] (not reduced to simplest form).

Try it online! Or see all of n=2 to 10 reduced to simplest form.

### How?

Uses the same approach as Christian Sievers' Pari/GP answer

Ḷṗ4S⁼¥Ƈɓ!×Ṗṁ4SƝṂƲ}:!P$}ð€S,4*$} - Link: integer, n
Ḷ                               - lowered range -> [0..n-1]
ṗ4                             - Cartesian power 4 (all length 4 tuples using alphabet [0..n-1]
Ƈ                         - filter keep those for which:
S                            -     sum
⁼                           -     equals n?
ɓ               ð€       - for each tuple do f(n, tuple):
!                       -   factorial = n*(n-1)*...*1
}              -   use right argument:
Ṗ                     -       pop i.e. (a,b,c,d)->(a,b,c)
ṁ4                   -       mould like 4 -> (a,b,c,a)
Ɲ                 -       for neighbours:
S                  -         sum -> (a+b,b+c,c+a)
Ṃ                -       minimum
×                      -   multiply
}         -   use right argument:
$- last two links as a monad: ! - factorial -> (a!,b!,c!,d!) P - product -> a!×b!×c!×d! : - integer division S - sum } - use right argument:$  -   last two links as a monad:
4    -     four
*   -     exponentiate -> 4^n
,     - pair

• Very nice. Maybe I should have made the range 2..30 :)
– user9207
Feb 1, 2020 at 18:04
• This does $n=30$ in ~18 seconds. It's much slower than the Pari/GP because I create all $n^4$ (a,b,c,d) tuples and filter to those that sum to $n$ (because it's golf). Feb 1, 2020 at 18:11

# 05AB1E, 26 bytes

Ý4ãʒOQ}ε¨Ćü+ßI!*y!P÷}O4Im‚


Port of @JonathanAllan's Jelly answer, which uses the same formula as @ChristianSievers's Pari/GP answer.
Just like his answer, the output is not reduced to its simplest form.

Explanation:

Ý                 # Push a list in the range [0, (implicit) input-integer]
#  [0,input], but that doesn't pose an issue, since the mapped value will
#  result in 0, not affecting the total sum)
4ã               # Create all possible quartets by using the cartesian product with 4
ʒ              # Filter these quartets by:
O             #  Take the sum
Q            #  And check if it's equal to the (implicit) input-integer
}ε             # After the filter: map each remaining quartet [a,b,c,d] to:
¨            #  Remove the last item d: [a,b,c]
Ć           #  Enclose the list, appending its own head: [a,b,c,a]
ü+         #  Sum each consecutive pair: [a+b,b+c,c+a]
ß        #  Pop and push the minimum of this
I!      #  Push the input, and take its factorial
*     #  Multiply both by each other
y!   #  Take the factorial of each value in the quartet: [a!,b!,c!,d!]
P  #  Take the product of this: a!*b!*c!*d!
÷ #  Integer-divide the two: (min(a+b,b+c,c+a)*n!) // (a!*b!*c!*d!)
}O            # After the map: take the sum of all values in the list
I          # Push the input-integer again
4 m         # And take 4 to the power this
‚        # And finally pair both together
# (after which this pair is output implicitly as result)