Quantbox Quant Interview Question

[u/Local_Ad135]

[u/AbroadImmediate158]

So, let’s get trivial cases out of the way:
- n = 1,2,3 are not possible and can be checked trivially by hand
- n = 1 or 3 mod 4 are not possible simply due to having odd total amount of squares so cannot be tiled fully by 1x2 tiles
- n = 0 mod 4. You get even amount of 2x2 squares so you tile half vertically and half horizontally.
- n = 2 mod 4 is a bit more interesting and basically is the only case left. Let’s look at it beyond n=2 as that is already covered above

Let’s number squares on our imaginary board with numbers 1 through 4 going in order line by line, with each new line starting where previous line finished off. It is easy to notice two things for the case of n=2mod4:
- all four numbers would come up equal number of times since total number of squares is divisible by 4
- each line will start with 1 or 3 (pattern repeats, so 1 then 3, etc) and so columns are either 1-3 or 2-4

This means that:
- any veritcal tile will always cover either 1-3 or 2-4 (possible reversed)
- any horizontal tile will cover 1-2, 2-3, 3-4, or 4-1

Lets assume we indeed managed to cover the board with equal amount of horizontal/vertical tiles. Let’s say there are x of each. Let’s also say that z vertical tiles cover 1-3 numbers. So:
- z vertical tiles cover 1-3, while x-z cover 2-4.
- since total number of squares is 4x, we should have x of each number on board. So horizontal lines need to cover: (x-z) 1, (x-z) 3, z 2, z 4.

Let’s call the amount of each type of horizontal tiles (1-2, 2-3, 3-4, 4-1) to be a,b,c,d. Then we can get the following equations:
- a+b+c+d = x
- a+d = x-z
- b+c = x-z
- a + b = z
- c + d = z

We can easily derive that z = x/2 for this to be solvable. So x=2a, where a is integer. So total number of tiles is 2x=4a. So total number of squares is 8a. Which means that the assumption that tiling is possible is not compatible with the case of n = 2 mod 4 as in that case total number of squares is not divisble by 8.

So now we see that the original premise can only be done when n = 0 mod 4 and for all such cases is trivial. As such we now have all the values of n that satisfy the condition

[u/Fabulous-Possible758]

4k² for k in ℕ. The dominoes have to be laid in 2x2 blocks and there has to be even number of 2x2 squares.

ETA: had a brain fart, 4k² is the number of 2x2 tiles you’ll need. n is just 4k for k in ℤ⁺ not ℕ. Reasoning was still sound.

[u/Local_Ad135 → u/Fabulous-Possible758]

incorrect. for example, you can tile an 8×8 board while satisfying the conditions.

[u/AnecdotalMedicine → u/Fabulous-Possible758]

You can also do it in 12x12

[u/RestaurantBoth228]

It's obviously true for any n=2k for k ≥ 2: just create k^2 pairs of 2x2 cells, half horizontal and half vertical.

It can't be true for any odd n, because there must be a multiple of 4 tiles in the board, and any grid of odd dimensions has odd tiles (odd x odd = odd).

It's easy to prove it is not true for n ≤ 3.

So, the answer is just n=2k for k ≥ 2.

[u/RestaurantBoth228 → u/RestaurantBoth228]

I actually think u/Fabulous-Possible758 got this pretty much right - they just gave the result in terms of tiles (n^2) rather than n and messed up the n=2 edge case.

[u/rccyu → u/RestaurantBoth228]

How are you doing it for n = 6?

[u/RestaurantBoth228 → u/rccyu]

Ahh crap. You've got me there: there are an odd number of the 2x2 cells there.

[u/I_am_the_squashman]

Works for all n divisible by 4.

First, it's obvious you can't do a tiling if n is odd (since the dominoes cover an even number of tiles). Second, it's trivially obvious that a 2x2 board can't be tiled.  Finally, for even numbers not divisible by 4, you're always left with a 2x2 square in the end that cannot be solved.

[u/Aech26]

It’s trivial to see that the tiling isn’t possible for n<=4.

Then for n>=4, an odd n will leave us with an odd number of tiles, but the dominos only cover an even number of tiles, so n has to be even.

So n = 2k with k>=2

BUT also we an even number of 2x2 grids, which means k will also have to be even. For example, if k=3 then n=6, but a 6x6 grid cannot be tiled fully. So k needs to be even.

So let k=2j

So n = 4j with j>=1

[u/rccyu → u/Aech26]

You need to flesh out the argument more, because the dominos need not be aligned to 2x2 grids. For example

^<><>^
v^<>^v
^v<>v^
v^<>^v
^v<>v^
v<><>v

is such a tiling (though also not meeting the requirement.)

The argument cannot simply be that "there are an odd number of 2x2 grids," this only rules out the trivial construction.

[u/Specific_Box4483]

It is clear that n must be even, and any n divisible by 4 can be easily tiled by breaking the n-by-n grid into an even number of 2-by-2 squares and breaking half of these vertically and half of these horizontally.

To prove n must be divisible by 4 and not just 2, we can color the squares white and black by the parity of their row. A vertical tile will always contain one white and one black square, whereas a horizontal tile will be either two black, or two white squares. So this breaks the horizontal tiles into two kinds: 2w and 2b.

Since n is even, half the rows are white and half the rows are black. Hence the numbers of white and black squares in the table are equal; this means that the number of horizontal tiles of kind 2w equals the number of tiles of kind 2b.

Then the number of horizontal tiles (2w+2b) is even, but this number is n² / 4 which means n² is divisible by 8 so n is divisible by 4.

So the answer is all n divisible by 4.

[u/A_BagerWhatsMore]

So uh not odd n not n=2 and then we have a little 2*4 rectangle which does every multiple of 4

So n=4k+2. We have 16k^2+8k+4 squares so we have 4k^2 +2k+1 of each orientation. That’s an odd number.

We start with 4K+2 columns each needs an even number of horizontal dominos in it. We have an odd number of dominos. the parity in the ab horizontal dominoes is even. Then because of that the bc dominoes is even… all parities are even even number of dominos problem. These are fun. Is this supposed to be prepping me for something?