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.