Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random binary string of length $k$ with equal probability. For each vertex $v$ let $b(v)$ denote the attached binary string. For a binary string $b$, let $x_0(b)$ denote the number of zeroes in $b$ and $x_1(b)$ be the number of one's in $b$. For each pair of vertices $u,v$ put 

$$w(\{u,v\}) = \max\{x_0(b(u) + b(v)), x_1(b(u)+b(v))\}$$

Let $X_{n,k}$ denote the random variable 

$$X_{n,k} = \max \{ w(\{u,v\}) : u,v \in V(K_n)\}.$$

What is $E(X_{n,k})$ as a function of $n$ and $k$?