Here's a math problem inspired by the boardgame "Pandemic", neither my boardgame buddies or I have any idea, so here it is:

Given a finite simple graph G with n vertices and a natural number k much smaller than n. We can choose k vertices of G and add edges between these vertices so they become a k-clique. Call the resulting graph G'.

Our question is, how do we determine the optimal set of k vertices such that the average distance between pairs of vertices of G' is minimized? Algorithmically, can we do much better than trying all k-subsets? Or, can we show that the problem is NP-hard? Are there neat solutions to specific kind of graph G?

To clarify what I mean by "average distance": for every two distinct vertices, compute the distance, i.e. length of shortest path with ends at these two vertices. Then do this for all pairs of vertices of the graph, and compute the average.

2.

In the card game Hanabi, what are the arrangements of the drawing deck of cards for which it is impossible to obtain a perfect score?

One obvious example is a 4-player game where each player holds 5 cards, and the 1's of all five colours are at the bottom of the pile. Then people can only pass info or discard cards until someone draws the first 1, at which point they could not keep a copy of each of 2,3,4,5 of all five colours. Therefore no matter how ingenious the communication protocol is, it is impossible to get a perfect score with this unfortunate arrangement of cards.