Particionar produtos cartesianos do formulário $[0,n]\times[0,m]$ ( $n,m\in\mathbf{N}$) “Diagonalmente”

Aug 15 2020

Considere o produto cartesiano $[0,2]\times[0,3]$. Os elementos deste conjunto são$$\begin{align*} & (0,0) & (1,0) & &(2,0) \\ & (0,1) & (1,1) && (2,1)\\ &(0,2) & (1,2) && (2,2)\\ &(0,3) & (1,3) && (2,3)\end{align*}$$ Os conjuntos a seguir particionam este produto cartesiano "diagonalmente": $$\{(0,0)\},\{(1,0),(0,1)\},\{(0,2),(1,1),(2,0)\},\{(0,3),(1,2),(2,1)\},\{(1,3),(2,2)\},\{(2,3)\}.$$ Existe uma maneira de fazer isso por $n,m\geq 0$? Inicialmente, pensei na seguinte maneira. Para cada$k\in[0,m+n]$, deixei $$J_k=\{(i,j)\ |\ 0\leq i\leq n\ \land\ 0\leq j\leq m\ \land\ i+j=k\}.$$ Mas estes $J_k$contém mais elementos do que eu preciso. Alguma sugestão para alterar isso?

Respostas

1 AirMike Aug 15 2020 at 22:31

Eu estava verificando sua definição do conjunto $J_k$ para o seu exemplo acima e funcionou muito bem.

Considere, por exemplo, $k=2$. Então

$$J_2 = \{(i,j) \mid 0 \leq i \leq 2 \wedge 0 \leq j \leq 3 \wedge i + j = 2\}$$

Então você quer esses pares ordenados no retângulo $[0,2] \times [0,3]$ que estão na linha $j = -i + 2$. E você pode ver, resolvendo essa equação (sabendo que$i, j \in \mathbb{N}$), você obterá as soluções exatas que escreveu em sua pergunta.

Agora, em geral, é isso que você está fazendo nesses conjuntos

$$J_k = \{(i,j) \mid 0 \leq i \leq n \wedge 0 \leq j \leq m \wedge i + j = k \}$$

Aqui você está listando todos os pares que estão no retângulo $[0,n] \times [0,m]$ e na linha $i + j = k$.

Portanto, uma coleção desses conjuntos $J_k$ lhe dará a partição desse retângulo “diagonalmente”.