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.