In a fish shop with 28 kinds of fish, there are 28 fish sellers. In every seller, there exists only one type of each fish kind, depending on where it comes, Mediterranean or Black Sea. Each of the $k$ people gets exactly one fish from each seller and exactly one fish of each kind. For any two people, there exists a fish kind which they have different types of it (one Mediterranean, one Black Sea). What is the maximum possible number of $k$?
1. **Restate the problem in terms of binary strings:**
   We are given an \( n \times n \) board where each cell contains either a 0 or a 1. We need to choose exactly \( n \) cells such that all the chosen cells are in different rows and different columns. For each row, we append the value of the chosen cell to form a binary string of length \( n \). The goal is to determine the maximum number of different binary strings that can be created.

2. **Define the problem in terms of binary strings:**
   Let \( n = 28 \). We need to find the maximum number of different binary strings of length \( n \) that can be created under the given constraints.

3. **Upper bound on the number of binary strings:**
   Consider the complement string of each column. Let \( s_i \) be the complement string of column \( i \). It is clear that we cannot create the strings \( s_1, s_2, \dots, s_n \) because each string \( s_i \) would require selecting the complement of the entire column \( i \), which is not possible under the given constraints. Therefore, the number of different binary strings \( k \) must satisfy:
   \[
   k \leq 2^n - n
   \]
   This is because there are \( 2^n \) possible binary strings of length \( n \), and we cannot create \( n \) specific strings (the complement strings of each column).

4. **Construction to achieve the upper bound:**
   To show that \( k = 2^n - n \) is achievable, we can use a construction method. We can construct the binary strings by ensuring that for any two people, there exists a fish kind (or equivalently, a column in the binary string) where they have different types (one 0, one 1). This construction can be proven by induction.

5. **Inductive proof:**
   - **Base case:** For \( n = 1 \), there are \( 2^1 - 1 = 1 \) possible binary string, which is achievable.
   - **Inductive step:** Assume that for \( n = k \), we can create \( 2^k - k \) different binary strings. For \( n = k + 1 \), we can extend the construction by adding one more row and column, ensuring that the new binary strings still satisfy the condition that for any two people, there exists a fish kind where they have different types. This can be done by carefully choosing the values in the new row and column.

6. **Conclusion:**
   By the inductive proof, we can achieve the upper bound \( k = 2^n - n \).

The final answer is \( \boxed{ 2^n - n } \).