Minimal number of questions I am trying to solve the following problem :
$49$ distinct numbers are written in a $7\times7$ cell board.
You are allowed to pick any $3$ cells on the board and find out the set of numbers written in them with a single question. What is the minimal number of questions needed to ask in order to know what number is written in each cell?
 A: Arrange each cell of the grid, in a circular loop in anyway you wish. To uniquely determine numbers in $3$ distinct cells, you'll need $3$ questions.  Start from an arbitrary cell in the circular loop, and index them. Question one will be about cells indexed $1,2,3$. The next will be about cells indexed $3,4,5$ and so on and  you'll end up at cells indexed $49,1,2$. Counting them, you'll require 25 questions.
The number of cells doesn't matter, for any grid containing $n$ cells, you'll need $[n/2]$ questions if even, or $[n/2] + 1$, if odd.
A: Here is one way to find a lower bound. It uses the idea of the 'decision tree'. At the beginning when you haven't asked any questions there are $49!$ possible configurations of the board. When you ask the first question you could receive $\frac{49*48*47}{3*2*1} = 18424$ different answers. Now imagine a rooted tree $T$ where the nodes are the sets of all current possible configurations of the board (the root node is of course the set of all $49!$ configurations). The edges of the tree will be the different answers you get when you ask a question. So every node will have $\leq 18424$ edges. You could easily see that the node $P$ is parent of the node $C$, then $C \subseteq P$ (because every question eliminates some of the possibilities). You are done when you get a node $L$ containing only one possible configuration (the configuration you are searching). This node is a leaf of the tree because you don't have to ask more questions. So $T$ tree should have at least $49!$ leaves (one per each of the possible configurations). The least number of questions you need to ask to determine the configuration is then the least possible height of the tree. The tree with the minimal height is of course the complete one (every node has exactly $18424$ children). In such trees there is a handy formula that links the height $h$, the number of leaves $l$ and the number of children per node $n$. Namely $$l = n^{h}$$
In your case $49! \leq l = 18424^h$. So if my calculations are correct $h \geq 15$. Now to check if this is the real minimum you should try to find an actual algorithm solving the problem using $15$ questions.
