# 2018 Putnam Problem A2 Exploration in R

Problem A2 of the 2018 Putnam Competition states:

Let $$S_1, S_2, \dots, S_{2^n-1}$$ be the nonempty subsets of $$\{1,2,\dots,n\}$$ in some order, and let $$M$$ be the $$(2^n-1) \times (2^n-1)$$ matrix whose $$(i,j)$$ entry is $m_{ij} = \begin{cases} 0 & \mbox{if }S_i \cap S_j = \emptyset; \\ 1 & \mbox{otherwise.} \end{cases}$ Calculate the determinant of $$M$$.

First thing to note is that we can generate all nonempty subsets of $$\{1, 2, \ldots, n\}$$ by converting each integer from $$1$$ to $$2^{n} - 1$$ to binary. We can then compute set intersection with a bitwise AND.

In R we can accomplish this with the function:

intersects <- function(x, y) as.integer(!all((intToBits(x) & intToBits(y)) == intToBits(0)))

# 5 corresponds to {3, 1}, 1 corresponds to {1}
intersects(5, 1)
## [1] 1
 # 4 corresponds to {3}, 3 corresponds to {2, 1}
intersects(4, 3)
## [1] 0

So for some $$n$$ we create the matrix $$M$$. The function outer creates a matrix by applying a specified function to each pair for entries in the first two arguments. (Note that the function must be vectorized. See ?outer for help.)

n <- 3
N <- 2^n - 1

(X <- outer(1:N, 1:N, Vectorize(intersects)))
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,]    1    0    1    0    1    0    1
## [2,]    0    1    1    0    0    1    1
## [3,]    1    1    1    0    1    1    1
## [4,]    0    0    0    1    1    1    1
## [5,]    1    0    1    1    1    1    1
## [6,]    0    1    1    1    1    1    1
## [7,]    1    1    1    1    1    1    1
det(X)
## [1] -1

Let’s wrap this up in a function

m_det <- function(n) {
intersects <- function(x, y) as.integer(!all((intToBits(x) & intToBits(y)) == intToBits(0)))

N <- 2^n - 1
X <- outer(1:N, 1:N, Vectorize(intersects))
det(X)
}

m_det(3)
## [1] -1

Now we can apply it to a sequence of numbers:

vapply(1:7, m_det, numeric(1))
## [1]  1 -1 -1 -1 -1 -1 -1

So the solution is probably $$-1$$ for all $$n > 1$$. The proof is left to the reader of course.