problem
정수들의 다음과 같은 정삼각형 모양의 나열을 역파스칼삼각형이라 하자. 가장 밑줄에 있는 수들을 제외하고, 나머지 각 수들은 바로 밑에 있는 두 수의 차(의 절대값)이다. 예를 들어, 다음 나열은 네 개의 가로줄로 이루어지고 1부터 10까지의 모든 수가 등장하는 역파스칼삼각형이다.
4
2 6
5 7 1
8 3 10 9
2018개의 가로줄로 이루어지고 1부터 1+2+...+2018 까지의 모든수가 등장하는 역파스칼삼각형이 존재하겠는가?
hint)
n=1,2,3,4,5열의 경우 가능하고 n>=6 일때 존재하지 않습니다.
n=3,4,5의 경우를 첨부합니다. 아마 이 경우외에는 존재하지 않을 것 같습니다. 수작업을 하였지만 틀리지 않았다면 다른 경우가 없을 것 같습니다. 있다면 feedback 부탁드립니다.
sol
1) 역파스칼 삼각형의 1<=ai<=n for i =1,2,...,n
n개의 가로줄로 이루어진 역파스칼삼각형이 존재한다고 가정합니다. 이 역파스칼삼각형을 구성하는 수는 1부터 n(n+1)/2 까지입니다. n번째줄을 제외한 i번째 줄의 이웃한 두수의 차(절대값)가 (i-1)번째 줄의 값이 됨으로 max값인 n(n+1)/2라는 수는 역파스칼삼각형을 구성하는 2개의 수의 차로 만들어질 수 없으므로 마지막 줄인 n번째 줄의 수 입니다. 그리고 n번째열을 제외한 i번째 열에 대해서 역스파스칼 삼각형의 구성이 다음과 같습니다.
(ai: i번째 열의 수, b(i+1)=ai + a(i+1):i+1 번째열의 수)
즉 이웃한 두 수중 작은 것(a(i+1)과 윗줄의 수(ai)를 합하면 이웃한 두 수중 큰값(bi+1) 이 나오게 되고 1번째열부터 n번째열까지 계속해서 더 해나가면 bn= a1+a2+...+an이 됩니다. a1,a2,...an은 서로 다른 n개의 수임으로 bn >= 1+2+...+n = n(n+1)/2 이되고 역파스칼 삼각형의 수의 max값은 n(n+1)/2임으로 bn = n(n+1)/2가 되고 이를 만족하는 a1,a2,...,an은 1부터 n까지의 수가 됩니다. 즉 역파스칼 삼가형안에 각 줄마다 1부터n사이의 서로 다른 수가 존재하고 그 수들이 더해져서
bn = n(n+1)/2가 됩니다. 즉 다음 그림과 같은 역스파칼 삼각형이 존재하게 됩니다.(bn = n(n+1)/2, a1,...,an는 1부터 n사이의 서로 다른 수)
그리고 i번째열에서 ai는 min값, bi는 max값임을 알 수 있습니다. 먼저 ai가 min값인 이유는 각 열다마 1에서 n까지의 수가 한개씩들어감으로 i번째 열에서 ai를 제외하고 n+1이상의 수임으로 ai는 min값이 됩니다. bi가 max값인 이유는 bi보다 큰 수가 있다고 가정하면 이 수도 bn값을 구하듯이 i+1,...n번째까지 더해서 내려가 n번째 열에 수가 존재하게 되는데 bn =bi+a(i+1)+...+an으로 a(i+1)+...+an은 i+1번째열 부터 n열까지 더할수 있는 가장 작은 값입니다. bn보다 큰 수는 a(i+1)+...+an을 더하면 max인 bn=n(n+1)/2보다 큰 수가 n열에 존재함으로 모순이 생깁니다.
2) 역파스칼 삼각형의 n(n+1)/2 - c for c=1,2,...,,n
n(n+1)/2 - c for c=1,2,...,,n 즉 max값 n(n+1)/2에서 1뺀수 부터 n뺀수까지의 수들도 역파스칼 삼각형안에 있고 n>=4에서 1,2,..,n과 n(n+1)/2 - c for c=1,2,...,,n은 겹치는 수가 없음으로 n은 4이상의 자연수로 가정합니다. ex) for n=4, (1,...,n)=(1,2,3,4), n(n+1)/2 - c for c=1,...,n=(9,8,7,6)
n(n+1)/2 - c꼴의 수가 n이아니 i번째열에 있다면 바로 밑의 i+1번째열의 두 수중 작은값은 1이상 n이하의 수일 것 입니다. 만약 n+1이상의 수라면 i+1번째열에 n(n+1)/2보다 큰 수가 생겨 모순이 생깁니다. 즉, n(n+1)/2 - c의 위치는 ai값 위에 있다는 뜻이 됩니다. 그리고 n,n-1이 아닌 i번째 열에 n(n+1)/2 - c꼴의 수가 2개 이상 존재할 수 가 없습니다. 먼저, n(n+1)/2-c pi n(n+1)/2-d순으로 배치되어 있다 가정합니다.(pi는 i번째 열의 수) 그러면 n(n+1)/2-c와 n(n+1)/2-d 밑에 ai+1이 무조건 생겨 ai꼴의 수가 2개가 생깁니다. 각 줄마다 1부터 n사이의 수가 1개씩 들어가므로 이는 모순입니다. 두번째로 n(n+1)/2-c n(n+1)/2-d 이렇게 붙어있는 경우 다음 그림과 같이 ai꼴의 수가 2개가 생겨 모순이 됩니다.
즉 이를 통해 1부터 n-2열의 각열마다 n(n+1)/2-c꼴의 수는 최대 1개까지만 들어갑니다. n-1열은 n+1열이 나오지 않음으로 이 열에는 an위에 n(n+1)/2-c꼴의 수가 최대 2개가 들어갈 수있고, 마지막열인 n열에는 개수는 2개이상들어갈 수 있으나 적어도 n(n+1)/2-c n(n+1)/2-d 이렇게 붙어있게 들어가면 안됩니다. 붙어 있게 들어가면 바로 위에 ai이 생겨 n(n+1)/2과 an사이의 위에 생긴 an-1과 겹쳐 모순이 생깁니다. n(n+1)/2-c꼴과 ai, bi그리고 위에서의 성질을 고려하여 다음과 같은 역파스칼 삼각형을 생각해 볼 수 있습니다.
여기서 f(n)=k such that 1+2+...+k = k(k+1)/2<= n<1+2+...+k+1 = (k+1)(k+2)/2 for k>=3(n은 6이상의 자연수)입니다.( ex)1+2+3<= 6,7,8,9 & f(6)=f(7)=f(8)=f(9) )
f(n)함수를 사용한 이유는 n(n+1)/2 과 an 사이의 위에 n(n+1)/2-c꼴의 수가 자리 잡을 것이고 계속 위로 올라가다 보면 즉 빼다보면 n(n+1)/2-n>b(n-k-1)가 나오게 될 것이고, 이때 k값은 an부터 an-k+1까지의 합을 최소로하여 즉 1부터 k까지 값으로 구성함으로써 제일 크게 나올 수 있는 수 입니다. 왜 k값이 최대가 나오도록 구성했냐면 k+1개의 n(n+1)/2-c꼴의 수를 최대한 n열을 제외하여 배치함에도 불구하고도 남은 n-(k+1)개의 n(n+1)/2-c꼴의 수를 n열에 배치함에 있어서 모순이 생긴다면 k값보다 작게 배치 된 것들은 당연히 모순이 생기게 되고 따라서 역파스칼삼각형이 존재하지 않기 때문입니다. 역파스칼삼각형을 구성하는데 있어서 빨간색 동그라미 원이 n-k열 위인 n-k-1열에도 생길 수 있다는 생각을 할 수 있는데 n(n+1)/2-n>b(n-k-1)으로 b(n-k-1)값이 n-k-1열의 max값으로 이 열에는 n(n+1)/2-c값이 존재할 수 없고 그 위에열도 bi꼴의 값이 n(n+1)/2-n보다 작게 되어 n(n+1)2-c값이 존재할 수 없습니다. k(k+1)/2<=n<(k+1)(k+2)/2에서 k(k+1)/2-(k+1) <= n-(k+1)<(k+1)(k+2)/2-(k+1)가 나오고 계산하면 (k-2)(k+1)/2<=n-(k+1)<k(k+1)/2가 나옵니다. n-(k+1)개의 n(n+1)/2-c꼴의 수를 n열에 배열하는데 있어서 무조건 한칸 이상씩 띄어서 배치를 해야 됩니다. 붙어있으면 위에 ai꼴이 1개가 더 생기어 모순이 됩니다. 따라서 다음 배치일때 최소로 필요로 하는 칸입니다.
즉 n-(k+1)개의 n(n+1)/2-c꼴의 수를 n열에 배열하는데 있어서 최소 2*(n-(k+1))필요함으로 n은 이 값 이상이어야 합니다.(k-2)(k+1)/2<= n-(k+1)<k(k+1)/2를 이용하여 2*(n-(k+1))+1의 범위를 구하면 k^2-k-2<= 2*(n-(k+1))<k^2+k이 되고 for k>=4, n= k(k+1)/2 <= k^2-k가 되어 모순이 생깁니다. 또 k=3의 경우는 가능한 n의 경우는 6,7,8,9로 n열에 배치하는 n(n+1)/2-c꼴의 개수의 min값은 각각 2,3,4,5=n-(k+1)개이고 필요한 최소칸수는 각각 4,6,8,10=2*(n-(k+1))로 n=9의 경우 필요한 최소칸수가 n=9칸 보다 크게 되어 모순이 생깁니다.
n=6,7,8의 경우는 증명하지 못하여 밑에 것은 나중에 수정하겠습니다. 오류가 많을 것 같고 있다면 feedback 부탁드리겠습니다. 다른 쉬운 방법이 있을 것 같습니다.
감사합니다.
n=6,7,8의 경우를 살펴 보겠습니다.
n=8의 경우
n=7의 경우
먼저 n열의 an과 n(n+1)/2는 <figure 1>과 같은 형태로 나타납니다.
<figure 1>
n(n+1)/2-c꼴의 수가 1칸 떨어진 경우는 다음 <figure 2>와 같이 n-2열에 c-d(절댓값)값으로 ai꼴이 나옵니다.(p값이 n(n+1)-c꼴이 아님으로 양옆보다 작습니다.)
<figure 2>
n=7일때 n열에 배치되는 n(n+1)/2-c꼴의 갯수는 3=(n-(k+1))임으로 an,n(n+1)/2 왼쪽이나 오른쪽에 적어도 2개 이상의 수가 배치됩니다. 따라서 <figure1>의 왼쪽의 경우 다음과 같이 an-2'꼴이 하나 더 생기게 되어 모순이 생깁니다.
그러므로 n(n+1)/2-c 꼴이 1칸 떨어진 꼴은 불가능함으로 최소2칸은 떨어져있어야 합니다. 따라서 n= 7일때 필요한 최소칸수는 8으로
n=7칸에 비하여 많음으로 모순이 생깁니다.
<figure1>의 오른쪽의 경우 an 왼쪽 위의 확정된 n(n+1)/2-c꼴의 수가 사라지게 되어 n열에 최소 4=n-k가 배치되고 필요칸 수는 9=2*(n-k)+1임으로 n=7칸보더 커 모순이 생깁니다. 최종적으로 n=7의 경우 모순이 생깁니다.
n=6의 경우 n=7의 경우와 마찬가지로 <figure1>처럼 나오며 왼쪽의 경우
밑에 글은 원하시면 지워도 될까요?
네네 감사합니다... 사실 지금글도 비번을 잘못쳐진 것 같애서 수정이 안되는 것 같습니다. 정말 죄송합니다.
여기서 수정하지 않고 n=6,7,8에 대해서만 따로 올리도록 해보겠습니다.
맨 밑변에서 a_n 왼쪽 수가 k개, 오른쪽 수가 n-2-k개일 때 왼쪽 k개 수들을 밑변으로 하는 크기 k 정삼각형, 오른쪽 n-2-k개 수들을 밑변으로 하는 크기 n-2-k 정삼각형 고려해도 쉽게 풀립니다. 왼쪽 삼각형의 맨 위 수를 x_1, 오른쪽 삼각형의 맨 위 수를 y_1이라 하면 {a_i}와 같은 식으로 {x_i}, {y_i}를 정의 가능하고
삼각형의 밑변엔 각각 x_1+...+x_k, y_1+...+y_(n-2-k)가 있습니다. 그런데 두 수 모두 n(n+1)/2보다 고, 두 삼각형엔 1, ..., n이 포함되지 않으니 n(n+1)-3=>x_1+...+x_k+y_1+...+y_(n-2-k)=>(n+1)+...+(2n-2)=n*(n-2)+(n-2)*(n-1)/2=(n-2)*(3n-1)/2입니다.
정리 시 n^2-9n+8<=0이라 n=>9에서 모순임을 알 수 있습니다.
와 맞는것 같습니다. 정말 쉽게 풀리는 군요