# 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. – AlienAtSystem Jan 31 '20 at 19:10
• Could you please provide some test cases? – lolad Jan 31 '20 at 20:25
• 0.375, 0.75, 1.125, 1.5234375, 1.93505859375, ...? – Jonathan Allan Jan 31 '20 at 22:53
• The denominator will be a power of two, so the decimal will terminate. – Christian Sievers Feb 1 '20 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. – Christian Sievers Feb 1 '20 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 '20 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. – Nicolas Feb 4 '20 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! – Christian Sievers Feb 4 '20 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 '20 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). – Jonathan Allan Feb 1 '20 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)