[중고딩문제] 평행 타일링의 최대 증명이 궁금해

[익명(121.143)]

- dc official App

[익명(39.7)]

(i) 아무렇게나 배치된 겹치지 않는 작은 두 정사각형이 있고, 그 둘을 둘러싼 최소 직사각형 영역 X가 있다면 그 두 정사각형을 붙일 때 X에 더 많은 정사각형을 쌓을 수 있거나 같음을 증명해서 최적 구조가 빈틈없이 이어붙인 걸 먼저 증명함

[익명(39.7)]

(ii) 그런 다음 (i)에 의해 평면 영역을 1/(2n-1) 간격의 격자로 나눌 때, R 영역을 격자에 배치하는 문제로 바꿀 수 있음. 이때 정사각형 A의 한 귀퉁이 좌표를 잡을 때 문제에서 배치된 구조말고는 전부 바깥 외곽에서 손실이 남을 증명함으로서 최적구조 증명 가능

[익명(39.7)]

대충 이런식으로 증명 스케치 그릴 수 있을듯

[익명(121.143)]

자세하게 모든과정 밟으면서 보이려면 증명길이가 엄청길거같아? - dc App

[익명(39.7)]

A4 2쪽 분량은 나올듯

[익명(121.143)]

시험장에선그럼 저문제증명절대못하겟네 문제그림도 증명할생각하지마 정사각형그려준거봐 이게최대맞아 알려주는거처럼 그려져잇고 - dc App

[익명(121.143)]

근데 시험과는 별개로 이런건 어떤논리로 차근차근 밟아져서 딱 증명되는지가궁금하네 증명디테일이어케될지 - dc App

[익명(121.143)]

근데 저 스케치는 임의의 정사각형이 어떤 한직사각형에만 포함되어야 가능할거같은데 두직사각형영역을 모두 포함하게 걸치게배열되면 최대가아니란건어떻게해? - dc App

[익명(39.7)]

(i)의 증명은 그저 빈틈없이 이어붙여야 공간을 더 확보할 수 있다라는 부분 최적구조를 증명하기 위해 쓴 것임. 즉 최적구조는 정사각형을 "옮길 수만 있다면" 둘 사이의 빈 공간이 없다 정도

[익명(39.7)]

(i)에서 (ii)로 갈 때의 비약은 꼭 제대로 배열된 격자만이 빈틈없이 배치된 게 아니라 벽돌쌓기마냥 1/2씩 밀려난 형태도 격자로서 볼 수 있어서 좀 더 확인해봐야 하지만.. A, B가 모두 정사각형이라는 구조가 가능케 할 거 같음

[익명(121.143)]

하나더궁금한거있음. 이문제가 a_n과 관련된 극한을다루고있잖아, 혹시 평행타일링이아니라 그냥이어도 극한값은 그대로유지될까?? 평행타일링의 최대개수를 a_n라 하고 그냥 타일링최대개수를 b_n라 하면 lim n->inf b_n-a_n가 무한대로발산을 안할거같아서 (그냥타일링을 한다해도 유의미하게 증가할거같지않아서) - dc App

[익명(39.7)]

정사각형이라 그러하겠지만 일반적인 다각형이나 곡면같은 경우는 그렇지 않겠지 그쯤되면 어려워서 일반화하는 것도 힘들겠지만..

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(121.143)]

문제에서 작은정사각형배열하는모양부터 그렇게줘서 저렇게하라는걸알려주는거같긴한데 시험장에서 저게최대인지증명까지하는건불가능하려나 - dc App

[익명(223.38)]

이거 쉽게 증명되는거 아니고 정수론 문제임

[익명(121.143)]

고딩내용으로 증명못함?ㄷㄷ - dc App

[익명(223.38)]

시작하기전에 일렬로 배치하는거가 최선이라는거 부터 증명해야지 라고 적을려고했는데 조건보니까 정사각형 한정이고 평행이라고 제한을 했으니 막 그렇지는 않아보이네 이미 정사각형 말고 임의의 m×n에서 증명되어있긴한데 증명과정에 정수론 내용들 좀 쓰여서