시에르핀스키 삼각형 위의 두 점의 평균 거리

짧은 수학 트리비아. 한 변의 길이가 1인 시에르핀스키 삼각형에서 두 점을 균일하게 선택했을 때 두 점 사이를 연결하는 시에르핀스키 삼각형 위의 경로를 잡아 그 거리를 생각할 수 있다. 그 거리의 평균은 466/885이라고.[1]

이 시에르핀스키 삼각형은 하노이의 탑과 연관이 있다는게 잘 알려져 있는데, 개의 링을 이용한 configuration들로 이루어진 그래프는 번째 시에르핀스키 중간 도형 모양으로 나온다. 즉 위 결과는 달리 말하자면 임의의 두 configuration에 대해 한 상태에서 다른 상태로 바꾸는데 필요한 최소 턴 수의 평균이 asymptotically 이 된다는 것. 이 해석을 이용해서 finite automata를 만들어 증명하는 방법도 있다.[2]

트윗 타래를 정리. (2019/03/01)

https://t.co/LgAuerzff4 한 변 길이 1인 시에르핀스키 삼각형에서 두 점을 유니폼하게 선택할 때 두 점 사이의 시에르핀스키 삼각형 위의 거리는 평균이 466/885라고 하네

— 유닼 (@udaqueness) March 1, 2019

References

[1] A. M. Hinz and A. Schief, “The average distance on the Sierpinski gasket” Probability Theory and Related Fields, March 1990, 87(1), pp 129-138. DOI: 10.1007/BF01217750

[2] D. Romik, “Shortest Paths in the Tower of Hanoi Graph and Finite Automata” SIAM J. Discrete Math., 20(3), 610-622. DOI: 10.1137/050628660