Consider the set $D$ of all divisors of $10000$. What is the number of subsets $H \subseteq D$ containing at least two elements such that for every $a, b \in H$, $a \mid b$ or $b \mid a$?
I tried translating the problem into one about integer grid, which makes it ask for the number of ways to choose at least two points in the square with vertices $(0, 0)$ and $(4,4)$ ordered in such a way that they can be reached sequentially by only moving up and right. But I fail to see a way to calculate it besides setting up this recurrence: let $a_{m,n}$ be the number of subsets of the square between $(0,0)$ and $(m,n)$ that satisfy the above property. We can form such a subset in a number of ways: it could be a subset already counted in $a_{m-1,n}$, or in $a_{m,n-1}$, or one of those same subsets with the addition of $(m,n)$, or be composed of $(m,n)$ and a point in the rectangle with vertices $(0,0$) and $(m, n)$ (there are $(m+1)(n+1)-1$ such points). If we simply added $a_{m-1,n}$ and $a_{m,n-1}$ we would be counting twice the subsets already counted in $a_{m-1, n-1}$.
The recurrence is thus: $\begin{cases} a_{0, 0} = 0 \\ a_{n,0} = a_{0,n} = 2a_{n-1, 0} + n \\ a_{m,n} = 2(a_{m-1,n} + a_{m,n-1} - a_{m-1,n-1}) + (m+1)(n+1)-1\end{cases}$.
And the answer we are looking for is $a_{4,4}$. Is there a more elegant way to answer this however?
I'm not sure if you'll think this is elegant but here goes:-
For convenience, temporarily drop the restriction that $H$ must contain $2$ elements. We can form a variant on Pascal's triangle as follows.
Write $1$ in the top right square i.e. $(4,4)$. This represents the number of sets $H$ with $(4,4)$ as the 'least' point.
Now consider the squares in the next diagonal down i.e. $(3,4)$ and $(4,3)$. For each of these squares we calculate $1$ more than the sum of the numbers above and to the right of it i.e. a total of $2$. For $(3,4)$, the first $1$ represents the number of sets $H$ which only contain $(3,4)$. The sum of the other numbers adds up all those sets $H$ containing $(3,4)$ and at least one other point.
Subsequent diagonals contain the numbers $$4,6,4$$ $$8,16,16,8$$ $$16,40,52,40,16$$ $$96,152,152,96$$ $$416,504,416$$ $$1536,1536$$ $$5136$$
So, I obtain the number $5136$ in square $(0,0)$ i.e. as the number of sets $H$ with $(0,0)$ as the 'least' point.
That means that the sum of all the numbers in the $5\times 5$ block is $ 5136+5135=10271$. We must now exclude the $5^2$ cases where we have only $1$ element in $H$ giving a total of $10246$.