# Project Euler Problem 85

After detail-laden Problem 84 solving Project Euler Problem 85 is a breeze. Nevertheless, prior to coding we need to do some preparatory math.

For our grid of **h*w** cells a specific rectangle can be selected by crossing 2 horizontal lines with 2 vertical. We can pick 2 horizontal lines in **(h + 1)!/2!*(h + 1 – 2)!** ways (see combination for justification). Similar is true for vertical lines: **(w + 1)!/2!*(w + 1 – 2)!**. After simplification it comes out that the number of different rectangles on a grid of **h*w** cells is **h*(h + 1)*w*(w + 1)/4**.

Now, let’s express approximate value of **w** via **h** assuming that overall number of rectangles is less, than 2000000:

**w = int(sqrt(float(8000000/(h*(h + 1)))))**. As we took **w*w** for **w*(w + 1)** approximation sometimes we may overshoot by 1; in these cases we would need to decrease **w** by 1.

The rest is quite simple: starting with **h=1** and ending with largest **h **less, than** w **let’s find all pairs ** (w,h) **that function

**yields value closest to 2000000. Of this sequence we select such area**

**rectangles w h****w*h**that yields minimal difference with 2000000:

let rectangles w h = w * (w + 1) * h * (h + 1) / 4 let solutions = Seq.unfold(fun h -> let w = int(sqrt(float (8000000/(h*(h+1))))) let solution = if rectangles w h > 2000000 then (w - 1,h) else (w,h) if fst solution <= h then None else Some(solution, h + 1)) 1 let problem085() = solutions |> Seq.toList |> List.map (fun (w,h) -> (2000000 - (rectangles w h), w*h)) |> List.sortBy (fun (diff,area) -> diff) |> List.head |> snd