Problem 15

Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20x20 grid?

Conceito

Em um grid 2x2 temos que mover 2 pra direita e 2 para baixo

Tentar abstrair do conceito geometrico

Talvez seja uma questão de combinação?

$nCr = \frac{n!}{r!(n-r)!}$

Onde, $nCr$ é a combinação de $n$ elementos em $r$ opções

Tentativa 1 - 26/12/2025

Errei: permutação com repetição

Conjunto é quando a ordem não importa.

Arranjo é quando a ordem importa, aqui importa D, D, B, B é diferente de B, B, D, D

No caso vamos tentar uma permutação com repetição

$P_r(n) = \frac{n!}{(n-r)!}$

Tentativa 2 - 26/12/2025

Ainda dando errado

tenho 20 d e 20 b

Quantas opções tenho?

Tenho que dar 40 passos, 20 deles para baixo e 20 para direita

O maximo seria 2^40 mas isso não considera que eu tenho 20 passos limitados

Vamos voltar para 2x2

Tenho 4 passos, 2 para baixo e 2 para direita

Opções = 4! / (2! * 2!) = 6

Será que posso extrapolar isso para 3x3 e outros?

Opções 3x3 = 6! / (3! * 3!) = 20

E para 20x20

Tentativa 3 - 26/12/2025

Putz, 137846528820 deu certo

A primeira fórmula estava certa mas eu coloquei como se tivesse $20.20 = 400$ opções, mas eram na verdade $20+20 = 40$ opções