Domino tiling
ರೇಖಾಗಣಿತದಲ್ಲಿ, ಯೂಕ್ಲಿಡಿಯನ್ ಸಮತಲದಲ್ಲಿರುವ ಪ್ರದೇಶದ ಡೊಮಿನೊ ಟೈಲಿಂಗ್ ಡೊಮಿನೊಗಳಿಂದ ಪ್ರದೇಶದ ಟೆಸೆಲ್ಲೇಷನ್ ಆಗಿದೆ, ಆಕಾರಗಳು ಅಂಚಿನಿಂದ ಅಂಚಿನವರೆಗಿನ ಎರಡು ಘಟಕ ಚೌಕಗಳ ಒಕ್ಕೂಟದಿಂದ ರೂಪುಗೊಳ್ಳುತ್ತವೆ. ಸಮಾನವಾಗಿ, ಇದು ಪ್ರದೇಶದ ಪ್ರತಿ ಚೌಕದ ಮಧ್ಯದಲ್ಲಿ ಶೃಂಗವನ್ನು ಇರಿಸುವ ಮೂಲಕ ಮತ್ತು ಪಕ್ಕದ ಚೌಕಗಳಿಗೆ ಹೊಂದಿಕೆಯಾಗುವಾಗ ಎರಡು ಶೃಂಗಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಗ್ರಿಡ್ ಗ್ರಾಫ್ನಲ್ಲಿ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಯಾಗಿದೆ. ಎತ್ತರದ ಕಾರ್ಯಗಳು ಎರಡು ಆಯಾಮಗಳಲ್ಲಿ ಸಾಮಾನ್ಯ ಗ್ರಿಡ್ನಲ್ಲಿ ಕೆಲವು ವರ್ಗದ ಟಿಲಿಂಗ್ಗಳಿಗೆ, ಗ್ರಿಡ್ನ ಶೃಂಗಗಳಿಗೆ ಪೂರ್ಣಾಂಕವನ್ನು ಸಂಯೋಜಿಸುವ ಎತ್ತರದ ಕಾರ್ಯವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲು ಸಾಧ್ಯವಿದೆ. ಉದಾಹರಣೆಗೆ, ಒಂದು ಚದುರಂಗ ಫಲಕವನ್ನು ಎಳೆಯಿರಿ, 0 ಎತ್ತರದ ನೋಡ್ ಅನ್ನು ಸರಿಪಡಿಸಿ, ನಂತರ ಯಾವುದೇ ನೋಡ್ಗೆ ಅಲ್ಲಿಂದ ಒಂದು ಮಾರ್ಗವಿದೆ. ಈ ಮಾರ್ಗದಲ್ಲಿ ಪ್ರತಿ ನೋಡ್ನ ಎತ್ತರವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿ (ಅಂದರೆ. ಚೌಕಗಳ ಮೂಲೆಗಳು) ಹಿಂದಿನ ನೋಡ್ನ ಎತ್ತರವಾಗಿರಬೇಕು ಮತ್ತು ಒಂದರಿಂದ ಇನ್ನುವರೆಗಿನ ಮಾರ್ಗದ ಬಲಭಾಗದಲ್ಲಿರುವ ಚೌಕವು ಕಪ್ಪು ಬಣ್ಣದ್ದಾಗಿದ್ದರೆ, ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಮೈನಸ್ ಒಂದಾಗಿರುತ್ತದೆ. ಹೆಚ್ಚಿನ ವಿವರಗಳನ್ನು ಇಲ್ಲಿ ಕಾಣಬಹುದು. ಥರ್ಸ್ಟನ್ನ ಎತ್ತರದ ಸ್ಥಿತಿಯು ಸಮತಲದಲ್ಲಿ ಘಟಕ ಚೌಕಗಳ ಒಕ್ಕೂಟವಾಗಿ ರೂಪುಗೊಂಡ ಸರಳ-ಸಂಪರ್ಕಿತ ಪ್ರದೇಶವು ಡೊಮಿನೊ ಟೈಲಿಂಗ್ ಅನ್ನು ಹೊಂದಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ಪರೀಕ್ಷೆಯನ್ನು ವಿವರಿಸುತ್ತದೆ. ಅವನು ಮೂರು ಆಯಾಮದ ಪೂರ್ಣಾಂಕ ಜಾಲರಿಯಲ್ಲಿನ ಬಿಂದುಗಳನ್ನು (x, y, z) ಅದರ ಶೃಂಗಗಳಾಗಿ ಹೊಂದಿರುವ ನಿರ್ದೇಶಿಸದ ರೇಖಾಚಿತ್ರವನ್ನು ರೂಪಿಸುತ್ತಾನೆ, ಅಲ್ಲಿ ಅಂತಹ ಪ್ರತಿಯೊಂದು ಬಿಂದುವು ನಾಲ್ಕು ನೆರೆಹೊರೆಯವರೊಂದಿಗೆ ಸಂಪರ್ಕ ಹೊಂದಿದೆಃ x + y ಸಮವಾಗಿದ್ದರೆ, (x, y, z) ಅನ್ನು (x + 1, y, z + 1), (x, y + 1, z-1), ಮತ್ತು (x, y-1, z-1) ಗೆ ಸಂಪರ್ಕಿಸಲಾಗಿದೆ, ಆದರೆ x + y ಬೆಸವಾಗಿದ್ದರೆ, (x, y, z) ಅನ್ನು (x + 1, y, z-1), (x-1, y, z-1), (x, y, z-1) ಗೆ ಸಂಪರ್ಕಿಸಲಾಗಿದೆ. (x, y) ಸಮತಲದಲ್ಲಿ ಪೂರ್ಣಾಂಕ ಬಿಂದುಗಳ ಅನುಕ್ರಮವಾಗಿ ನೋಡಲಾಗುವ ಪ್ರದೇಶದ ಗಡಿಯು, ಈ ಮೂರು ಆಯಾಮದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಒಂದು ಮಾರ್ಗಕ್ಕೆ ಅನನ್ಯವಾಗಿ (ಪ್ರಾರಂಭದ ಎತ್ತರವನ್ನು ಆಯ್ಕೆ ಮಾಡಿದ ನಂತರ) ಎತ್ತುತ್ತದೆ. ಈ ಪ್ರದೇಶವನ್ನು ಟೈಲ್ ಮಾಡಲು ಅಗತ್ಯವಾದ ಷರತ್ತು ಎಂದರೆ ಈ ಮಾರ್ಗವು ಮೂರು ಆಯಾಮಗಳಲ್ಲಿ ಸರಳವಾದ ಮುಚ್ಚಿದ ವಕ್ರರೇಖೆಯನ್ನು ರೂಪಿಸಲು ಮುಚ್ಚಬೇಕು, ಆದಾಗ್ಯೂ, ಈ ಸ್ಥಿತಿಯು ಸಾಕಾಗುವುದಿಲ್ಲ. ಗಡಿ ಮಾರ್ಗದ ಹೆಚ್ಚು ಎಚ್ಚರಿಕೆಯ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು, ಥರ್ಸ್ಟನ್ ಸಾಕಷ್ಟು ಮತ್ತು ಅಗತ್ಯವಾದ ಪ್ರದೇಶದ ಟೈಲೆಬಿಲಿಟಿಗೆ ಮಾನದಂಡವನ್ನು ನೀಡಿದರು. ಪ್ರದೇಶಗಳ ಎಣಿಕೆಯ ಟಿಲಿಂಗ್ಗಳು ಡೊಮಿನೊಗಳೊಂದಿಗೆ ಒಂದು ಆಯತವನ್ನು ಮುಚ್ಚುವ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸ್ವತಂತ್ರವಾಗಿ ಮತ್ತು ನಿಂದ ಲೆಕ್ಕ ಹಾಕಲಾಗುತ್ತದೆ, m ಮತ್ತು n ಎರಡೂ ಬೆಸವಾಗಿದ್ದಾಗ, ಸೂತ್ರವು ಸರಿಯಾಗಿ ಶೂನ್ಯ ಸಂಭವನೀಯ ಡೊಮಿನೊ ಟಿಲಿಂಗ್ಗಳಿಗೆ ಕಡಿಮೆಯಾಗುತ್ತದೆ. ಆಯತವನ್ನು n ಡೊಮಿನೊಗಳೊಂದಿಗೆ ಟೈಲ್ ಮಾಡುವಾಗ ಒಂದು ವಿಶೇಷ ಪ್ರಕರಣವು ಸಂಭವಿಸುತ್ತದೆಃ ಅನುಕ್ರಮವು ಫಿಬೊನಾಚಿ ಅನುಕ್ರಮಕ್ಕೆ ಕಡಿಮೆಯಾಗುತ್ತದೆ. m = n = 0,2,4,6,8,10,12, ಇರುವ ವರ್ಗಗಳಿಗೆ ಮತ್ತೊಂದು ವಿಶೇಷ ಪ್ರಕರಣವು ಸಂಭವಿಸುತ್ತದೆ. ಈ ಸಂಖ್ಯೆಗಳನ್ನು ವಕ್ರ-ಸಮಮಿತಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಪ್ಫಾಫಿಯನ್ ಎಂದು ಬರೆಯುವ ಮೂಲಕ ಕಂಡುಹಿಡಿಯಬಹುದು, ಅದರ ಐಗನ್ ಮೌಲ್ಯಗಳನ್ನು ಸ್ಪಷ್ಟವಾಗಿ ಕಾಣಬಹುದು. ಈ ತಂತ್ರವನ್ನು ಅನೇಕ ಗಣಿತ-ಸಂಬಂಧಿತ ವಿಷಯಗಳಲ್ಲಿ ಅನ್ವಯಿಸಬಹುದು, ಉದಾಹರಣೆಗೆ, ಸಂಖ್ಯಾಶಾಸ್ತ್ರದ ಯಂತ್ರಶಾಸ್ತ್ರದಲ್ಲಿ ಡೈಮರ್-ಡೈಮರ್ ಪರಸ್ಪರ ಕ್ರಿಯೆಯ ಶಾಸ್ತ್ರೀಯ, 2-ಆಯಾಮದ ಗಣನೆಯಲ್ಲಿ. ಒಂದು ಪ್ರದೇಶದ ಇಳಿಜಾರುಗಳ ಸಂಖ್ಯೆಯು ಗಡಿ ಪರಿಸ್ಥಿತಿಗಳಿಗೆ ಬಹಳ ಸೂಕ್ಷ್ಮವಾಗಿರುತ್ತದೆ ಮತ್ತು ಪ್ರದೇಶದ ಆಕಾರದಲ್ಲಿ ಗಮನಾರ್ಹವಲ್ಲದ ಬದಲಾವಣೆಗಳೊಂದಿಗೆ ನಾಟಕೀಯವಾಗಿ ಬದಲಾಗಬಹುದು. ಇದನ್ನು n ಕ್ರಮದ ಅಜ್ಟೆಕ್ ವಜ್ರದ ಟಿಲಿಂಗ್ಗಳ ಸಂಖ್ಯೆಯಿಂದ ವಿವರಿಸಲಾಗಿದೆ, ಅಲ್ಲಿ ಟಿಲಿಂಗ್ಗಳ ಸಂಖ್ಯೆ 2 (n + 1) n/2 ಆಗಿದೆ. ಇದನ್ನು 2ರ ಬದಲು ಮಧ್ಯದಲ್ಲಿ 3 ಉದ್ದದ ಸಾಲುಗಳನ್ನು ಹೊಂದಿರುವ n ಕ್ರಮದ "ವರ್ಧಿತ ಅಜ್ಟೆಕ್ ವಜ್ರ" ದಿಂದ ಬದಲಾಯಿಸಿದರೆ, ಟಿಲಿಂಗ್ಗಳ ಸಂಖ್ಯೆಯು ತುಂಬಾ ಸಣ್ಣ ಸಂಖ್ಯೆಯಾದ D (n, n) ಗೆ ಇಳಿಯುತ್ತದೆ, ಇದು ಡೆಲನ್ನಾಯ್ ಸಂಖ್ಯೆಯಾಗಿದ್ದು, ಇದು nನಲ್ಲಿ ಸೂಪರ್-ಎಕ್ಸ್ಪೋನ್ಷಿಯಲ್ ಬೆಳವಣಿಗೆಯ ಬದಲು ಕೇವಲ ಘಾತೀಯತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಕೇವಲ ಒಂದು ಉದ್ದದ ಮಧ್ಯದ ಸಾಲನ್ನು ಹೊಂದಿರುವ n ಕ್ರಮದ "ಕಡಿಮೆಯಾದ ಅಜ್ಟೆಕ್ ವಜ್ರ" ಕ್ಕೆ, ಕೇವಲ ಒಂದು ಟೈಲಿಂಗ್ ಇರುತ್ತದೆ. ಟಾಟಾಮಿ ಟಾಟಾಮಿಗಳು ಡೊಮಿನೊ (1x2 ಆಯತ) ಆಕಾರದಲ್ಲಿರುವ ಜಪಾನಿನ ನೆಲದ ಚಾಪೆಗಳಾಗಿವೆ. ಅವುಗಳನ್ನು ಕೊಠಡಿಗಳನ್ನು ಟೈಲ್ ಮಾಡಲು ಬಳಸಲಾಗುತ್ತದೆ, ಆದರೆ ಅವುಗಳನ್ನು ಹೇಗೆ ಇರಿಸಬಹುದು ಎಂಬುದರ ಕುರಿತು ಹೆಚ್ಚುವರಿ ನಿಯಮಗಳೊಂದಿಗೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಸಾಮಾನ್ಯವಾಗಿ, ಮೂರು ತತಾಮಿಗಳು ಸಂಧಿಸುವ ಜಂಕ್ಷನ್ಗಳನ್ನು ಶುಭವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ನಾಲ್ಕು ತತಾಮಿಗಳು ಸಂಧಿಸುವ ಜಂಕ್ಷನ್ಗಳು ಅಶುಭವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ಸರಿಯಾದ ತತಾಮಿ ಟೈಲಿಂಗ್ ಎಂದರೆ ಯಾವುದೇ ಮೂಲೆಯಲ್ಲಿ ಕೇವಲ ಮೂರು ತತಾಮಿಗಳು ಸಂಧಿಸುವ ಸ್ಥಳ. ಒಂದು ಮೂಲೆಯಲ್ಲಿ ಮೂರನ್ನು ಸೇರುವ ಟಾಟಾಮಿಯಿಂದ ಅನಿಯಮಿತ ಕೋಣೆಗೆ ಟೈಲಿಂಗ್ ಮಾಡುವ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದೆ. ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ಭೌತಶಾಸ್ತ್ರದಲ್ಲಿ ಅನ್ವಯಗಳು ನಿಯತಕಾಲಿಕ ಡೊಮಿನೊ ಟೈಲಿಂಗ್ ಮತ್ತು ಎರಡು ಆಯಾಮದ ನಿಯತಕಾಲಿಕ ಜಾಲರಿಯ ಮೇಲೆ ಸಂಪೂರ್ಣ ಫ್ರಸ್ಟ್ರೇಟೆಡ್ ಐಸಿಂಗ್ ಮಾದರಿಯ ಗ್ರೌಂಡ್ ಸ್ಟೇಟ್ ಕಾನ್ಫಿಗರೇಶನ್ ನಡುವೆ ಒಂದರಿಂದ ಒಂದು ಪತ್ರವ್ಯವಹಾರವಿದೆ. ಅದನ್ನು ನೋಡಲು, ನೆಲದ ಸ್ಥಿತಿಯಲ್ಲಿ, ಸ್ಪಿನ್ ಮಾದರಿಯ ಪ್ರತಿಯೊಂದು ಫಲಕವು ನಿಖರವಾಗಿ ಒಂದು ನಿರಾಶಾದಾಯಕ ಪರಸ್ಪರ ಕ್ರಿಯೆಯನ್ನು ಹೊಂದಿರಬೇಕು ಎಂಬುದನ್ನು ನಾವು ಗಮನಿಸುತ್ತೇವೆ. ಆದ್ದರಿಂದ, ಎರಡು ಜಾಲರಿಗಳಿಂದ ನೋಡಿದಾಗ, ಪ್ರತಿ ಹತಾಶ ಅಂಚನ್ನು 1x2 ಆಯತದಿಂದ "ಮುಚ್ಚಬೇಕು", ಅಂದರೆ ಆಯತಗಳು ಇಡೀ ಜಾಲರಿಯನ್ನು ವ್ಯಾಪಿಸುತ್ತವೆ ಮತ್ತು ಅತಿಕ್ರಮಿಸುವುದಿಲ್ಲ, ಅಥವಾ ಎರಡು ಜಾಲರಿಯ ಡೊಮಿನೊ ಟೈಲಿಂಗ್ ಆಗಿರುತ್ತದೆ. ಗೌಸಿಯನ್ ಫ್ರೀ ಫೀಲ್ಡ್ ಅನ್ನು ಸಹ ನೋಡಿ, ಸಾಮಾನ್ಯ ಪರಿಸ್ಥಿತಿಯಲ್ಲಿ ಎತ್ತರದ ಕಾರ್ಯದ ಸ್ಕೇಲಿಂಗ್ ಮಿತಿ (ಉದಾಹರಣೆಗೆ, ದೊಡ್ಡ ಅಜ್ಟೆಕ್ ವಜ್ರದ ಕೆತ್ತಿದ ಡಿಸ್ಕ್ ಒಳಗೆ) ಮ್ಯುಟಿಲೇಟೆಡ್ ಚೆಸ್ ಬೋರ್ಡ್ ಸಮಸ್ಯೆ, ಪ್ರಮಾಣಿತ 8x8 ಚೆಸ್ ಬೋರ್ಡ್ (ಅಥವಾ ಚೆಕರ್ಬೋರ್ಡ್ನ 62-ಚದರ ಪ್ರದೇಶದ ಡೊಮಿನೊ ಟೈಲಿಂಗ್ಗೆ ಸಂಬಂಧಿಸಿದ ಒಗಟು) ಸ್ಟ್ಯಾಟಿಸ್ಟಿಕಲ್ ಮೆಕ್ಯಾನಿಕ್ಸ್ ಟಿಪ್ಪಣಿಗಳು ಉಲ್ಲೇಖಗಳು ಮತ್ತಷ್ಟು ಓದುವಿಕೆ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ನಿಖರವಾಗಿ ಪರಿಹರಿಸಬಹುದಾದ ಮಾದರಿಗಳು ಲ್ಯಾಟಿಸ್ ಮಾದರಿಗಳು ಹೊಂದಾಣಿಕೆ (ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ) ಸ್ಟ್ಯಾಟಿಸ್ಟಿಕಲ್ ಮೆಕ್ಯಾನಿಕ್ಸ್ ಟೈಲಿಂಗ್ ಒಗಟುಗಳು