A few days ago, I decided to revisit Project Euler, a site dedicated to mathematical computing problems, i.e., problems that are solved through a combination of mathematical thinking and clever brute force via program.

I'm not allowed to publish solutions or code for any of the problems, but I want to share the approaches I used to solve two recent problems I saw that piqued my curiousity.

I should preface this by saying that I haven't solved problems on this site for over 5 years, so I just went to the recent problem page and solved two problems. Perhaps their solutions are a bit easier to find for those who solved prior problems. Regardless, I was in the top 100 fastest solvers for both!

Window into a Matrix II

A window into a matrix is a continguous submatrix

Consider a \(16\times n\) matrix where every entry is either \(0\) or \(1\). Let \(B(k,n)\) be the total number of these matrices such that the sum of the entries in every \(2\times k\) window is \(k\).

Find \(B(10^5,10^{16})\). Give your answer \(\bmod{10^9+7}\).

For those unfamiliar with the site, the "give your answer mod _" part of the question is used by Project Euler to ensure that answers aren't humongous, and to allow for mod based simplifications when computing the answer. We won't bother since we aren't writing code here.

So how do you approach this? Well, given that for the value of \(B\) we need to compute, \(k\) is a divisor of \(n\), we will assume that \(k\) is always a divisor of \(n\). This makes the problem a lot more manageable, as you will see.

In the diagram above, I'm assuming \(k=3\), \(n=9\) (the diagram is rotated so that rows are columns and columns are rows: sorry!), but this logic should work for the general case. Red squares indicate \(1\), and blue squares indicate \(0\).

First, we want to find how many ways are there to pick the first \(k\) columns of our window pane. Suppose the first row has \(0\leq i\leq k\) red squares. Then the row above it must have \(k-i\) red squares, and the row above it \(i\) red squares, etc. This forms a valid configuration of the first \(k\) columns. The diagram above shows an example of this for \(i=2\)

Thus, given \(i\), there are \({k\choose i}^8\cdot{k\choose k-i}^8={k\choose i}^{16}\) ways to pick the first \(k\) columns, as for each odd row, we pick \(i\) red squares from the \(k\) squares, and for each even row, we pick \(k-i\) red squares from the \(k\) squares. So, the total number of ways to pick the first \(k\) columns is $$G(k)=\sum\limits_{i=0}^k{k\choose i}^{16}$$

This is a good first step, but now we need to pick the remainder of the columns. Here's an interesting claim: the \(j\)th column, where \(j\) is not one of the first \(k\) columns, must be identical to the \(j-k\)th column in all but \(2\) cases.

Here's why: Let \(A_{i,j}\) refer to the square in the \(i\)th row and \(j\)th column. If there exists \(0\leq i\lt k\) such that \(A_{i,j-k}=A_{i+1,j-k}\), then consider the \(2\times k\) rectangle spanning the rows \(i,i+1\) and columns \(j-k,\ldots,j-1\). This rectangle must have \(k\) red squares. Likewise, the \(2\times k\) rectangle spanning the rows \(i,i+1\) and columns \(j-k+1,\ldots,j\) also must have \(k\) red squares. Thus, $$A_{i,j-k}+A_{i+1,j-k}=A_{i,j}+A_{i+1,j}$$Since the left side is even, so must the right side, implying that all \(4\) squares have the same value (if you don't understand this, write out the possibilities explicitly).

Moreover, this implies $$A_{i-1,j-k}+A_{i,j-k}=A_{i-1,j}+A_{i,j}\to A_{i-1,j-k}=A_{i-1,j}$$$$A_{i+1,j-k}+A_{i+2,j-k}=A_{i+1,j}+A_{i+2,j}\to A_{i+2,j-k}=A_{i+2,j}$$Repeating this logic shows that column \(j-k\) and column \(j\) are identical under these conditions. So, as long as there are two squares adjacent to each other in the same column with the same value, each column \(k\) columns forward must be identical to the current column.

So, the only possibility in which this doesn't happen is if column \(j-k\) is \(0101010101010101\) or \(1010101010101010\). Call these columns \(v_0,v_1\). Note that if column \(j-k\) is \(v_0\) or \(v_1\), column \(j\) can be either of columns \(v_0,v_1\).

Thus, the total number of possibilities for the entire window pane is determined by the number of \(v_0,v_1\) columns in the first \(k\) columns. Let \(H(i)\) for \(0\leq i\leq k\) represent the number of placements of the first \(k\) columns such that there are \(i\) \(v_0,v_1\) columns in the first \(k\) columns.

Given a configuration of the first \(k\) columns with \(i\) \(v_0,v_1\) columns, how many possibilities are there for the whole window pane? Well, for every non-\(v_0,v_1\) column, each column \(k\) columns forward must be identical to the current column, and for the \(v_0,v_1\) columns, there are two possibilities for the column \(k\) columns forward. So, the answer is \(2^{in/k}\). Thus, the final answer to this problem is $$\sum\limits_{i=0}^kH(i)\cdot2^{in/k}$$

All we need to do now is compute \(H(i)\). This, unfortunately, is messy. We work backwards. Note that \(H(k)=2^k\), since each column can be \(v_0\) or \(v_1\).

Now, assume that we know the values of columns \(H(i+1),\ldots,H(k)\). Now, we want to compute \(H(i)\). There are \(k\choose i\) ways of picking which \(i\) columns will be \(v_0,v_1\) columns, \(2^i\) ways of picking which one of \(v_0,v_1\) each of them will be, and \(G(k-i)\) ways of picking the remaining columns. Thus, we might guess that $$H(i)=2^i\cdot{k\choose i}\cdot G(k-i)$$The issue is that we have also counted cases in which there are more than \(i\) \(v_0,v_1\) columns.

How many times have we counted a configuration from \(H(j)\) in \(2^i\cdot{k\choose i}\cdot G(k-i)\), where \(j\gt i\)? Well, any configuration in \(H(j)\) has \(j\) \(v_0,v_1\) columns. There are \(j\choose i\) ways of choosing \(i\) of these columns as we did in computing \(H(i)\). So, we need to subtract out \({j\choose i}\cdot H(j)\) from our initial guess. This gives us the following final formula: $$H(i)=2^i\cdot{k\choose i}\cdot G(k-i)-\sum\limits_{j=i+1}^k{j\choose i}\cdot H(j)$$We've theoretically solved the problem, but how would one actually solve the problem? Well, there's a nice simplification of \(B(k,n)\) using the formulas I've provided you. Like Fermat chose not to provide his proof of Fermat's Last Theorem due to lack of space, I'll leave the rest to you (unlike Fermat, I actually solved the problem, so it is possible without spending 20 years of your life).

Stealthy Numbers

A positive integer \(N\) is stealthy if there exists positive integers \(a,b,c,d\) such that \(ab=cd=N\) and \(a+b=c+d+1\). For example, \(36\) is stealthy because$$36=4\times9=6\times6$$

How many stealthy numbers don't exceed \(10^{14}\)?

Solving the second equation for \(b\) and substituting it in the first equation gives us $$cd=ac+ad+a-a^2$$So, we have $$(c-a)(d-a)=cd-ac-ad+a^2=a$$Let \(c-a=x\), \(d-a=y\). So, \(a=xy\). Thus, we have \(xy+x=a+c-a=c\) and \(xy+y=a+d-a=d\). So, \(c=x(y+1)\) and \(d=(x+1)y\). So, \(b=(x+1)(y+1)\). Since all of our steps are reversible, this shows that these expressions are the general form for \(a,b,c,d\). Thus, the general form for a stealthy number is $$x(x+1)y(y+1)$$So, all we need to do is count the number of numbers of this form \(\lt10^{14}\). I'll leave it to you to finish the rest.

Category: Puzzles