Não é apenas uma brincadeira para crianças

Organizar o quebra-cabeça não é uma tarefa trivial para os menos habilidosos, e a mesma dificuldade é determinar quantos movimentos são necessários para transformar um quebra-cabeça ordenado em aleatório.
Persi Diaconis, um matemático da Universidade de Stanford, propôs em 1988 a versão aleatória do quebra-cabeça dos 15 e determinou que seriam necessários $n^3$ movimentos para embaralhar qualquer quebra-cabeças independente da quantidade de peças móveis. Assim, seriam necessários 43 ou 64 movimentos para um quadro de 4 por 4 e $10^3$, ou 1.000, movimentos para um quadro de 10 por 10. (Embora ainda sejam referidos como "o quebra-cabeça dos 15", os tabuleiros podem ter vários espaços que compõem um quadrado perfeito).
O que aparentemente representa um passatempo, na realidade é uma classe de questões semelhantes de randomização. Muitos desses problemas têm a ver com características fundamentais do mundo natural, como a maneira como os pares de bases no DNA trocam de lugar para causar uma mutação genética e como as moléculas se separam e se tornam desordenadas, como o derretimento do gelo. O entendimento da aleatoriedade do quebra-cabeça dos 15, é possível prever como os sistemas ordenados geralmente se desdobram em um estado uniformemente confuso. Cada etapa depende de uma etapa anterior.
Os matemáticos estudam esse fenômeno usando modelos chamados cadeias de Markov. As cadeias de Markov são uma maneira formal de estudar qualquer processo de randomização no qual a configuração subsequente de um sistema depende apenas de sua configuração atual. Eles estão na vanguarda da compreensão matemática da aleatoriedade.
"Eles estão neste ponto ideal onde ainda podemos analisá-los, mas descrevem muitos fenômenos de interesse", disse Yuval Peres, um matemático que fez um trabalho importante na teoria das probabilidades.
Em uma nova abordagem para o mesmo problema, Chu e Hough trataram a randomização do quebra-cabeça dos 15 (vendido no Brasil como esquenta cuca) como uma cadeia de Markov. Em particular, eles analisaram uma coleção de números chamada “matriz de transição” da cadeia de Markov. A matriz de transição é um vasto conjunto de números que especifica a probabilidade de o quebra-cabeça dos 15 passar de uma configuração para a seguinte, se você decidir aleatoriamente como mover o espaço vazio.

Compreendendo  a matriz de transição, será possível descobrir o número de movimentos necessários para randomizar ou misturar um quadro ordenado. Mais especificamente, Chu e Hough se concentraram na identificação de um conjunto de números que caracterizam a matriz de transição - números chamados "autovalores" e suas descobertas foram interessantes. Foi constatado que são necessárias cerca de $n^4$ etapas para randomizar uma quadro n por n (portanto, 256 etapas para um quadro 4 por 4 e 10.000 etapas para uma quadro 10 por 10). São mais etapas do que Diaconis previu. Sendo ainda mais rigoroso, Chu ainda determinou que o número de movimentos necessários é maior do que $n^4 log n$ .
Hough e Peres trabalham em conjunto para estender a prova e tentar verificar se ao aumentando o tamanho do quadro, a aleatoriedade aumenta abruptamente. 

Fonte: CHU, Yang; HOUGH, Robert. Solution of the 15 puzzle problem. arXiv preprint arXiv:1908.07106, 2019.