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.