Solução:
a) Analisando os caminhos a partir de A em relação a quadras caminhadas, temos:
• Para os pontos (1, 0) e (0, 1), só existe 1 caminho para chegar a eles.
• Para os 3 pontos da próxima diagonal (2, 0), (1, 1) e (0, 2), existem, respectivamente,
1, 2, e 1 caminhos para se chegar a eles. Para o ponto (1, 1), por exemplo, existe um caminho passando por (0,1)
e outro caminho passando por (1, 0).
Ao continuar preenchendo as possibilidades, notamos que um Triangulo de Pascal vai se formando a partir do vértice A, como abaixo, onde cada número dele representa a quantidade de caminhos de A até aquele ponto realizando apenas movimentos vermelhos.
Como caminhos de cada vértice são formados por um caminho que chegue da esquerda ou um caminho de baixo, o número de um vértice será igual a soma do número do vértice da esquerda com o número do vértice de baixo:
Dessa maneira, analisando a figura, vemos que de A a C temos
caminhos possíveis, utilizando
apenas movimentos
vermelhos.
b) Fazendo uma análise análoga para o ponto B temos:
Assim, analisando a figura, vemos que de B a C temos
caminhos
possíveis utilizando apenas movimentos
azuis.
c) Analisando o Triângulo de Pascal a partir de A para todo o tabuleiro, .
Analisando o Triângulo de Pascal a partir de B para todo o tabuleiro, .
Assim, para satisfazer as 2 propriedades, o Shopping (S) deve se situar nas coordenadas .
Solução alternativa:
A Distância Manhattan entre 2 pontos A e B em uma grade retangular é definida pela soma da quantidade de segmentos na direção x com a quantidade de segmentos na direção y necessários para se chegar de A a B, que é o menor caminho necessário para ir de A a B através da grade.
Por exemplo, a Distância Manhattan de para é igual a , pois para se
chegar de A a C pode se andar segmentos na direção x e na direção y.
Já, a Distância Manhattan de para é igual a , pois para se chegar de B a C
pode se andar segmentos na direção x e na direção y.
A Distância Manhattan de 2 pontos da grade retangular `A (x_a, y_a)` e `B (x_b, y_b)` é dada matematicamente por: `d(A,B) = |x_a -x_b| + |y_a - y_b|`.
Essa propriedade é interessante, pois todos os caminhos mínimos que vão de A para C têm comprimento igual à distância Manhattan entre A e C, que é . Dos segmentos que temos que caminhar de A a C, temos que
escolher em que momentos nos deslocaremos os segmentos verticais.
a) Assim, para saber a quantidade de caminhos de A a C, basta que façamos .
b) Da mesma forma, podemos calcular a quantidade de caminhos de B a C, que seria .
c) Para esse item, poderíamos fazer o Triangulo de Pascal a partir de A, e analisar quais pontos da grade possuem caminhos possíveis partindo de A, .
Mas não precisaríamos montar o Triângulo de Pascal a partir de B, pois poderíamos apenas verificar as Distâncias Manhattan de a , e, consequentemente, a quantidade de caminhos.
Sendo assim, o ponto é a localização desejada do Shopping (S).