Powers of Two


작성일 : 2018-06-03 00:20:10
조회수 : 283


본문

임의의 정수 집합  $$S = {a_1, a_2, a_3, ... , a_n}$$ 에서, 모든 원소의 차이가 $2^k$ 꼴인 형태가 되는 부분집합을 만들고자 할 때, 부분집합의 원소의 개수는 3개를 넘을 수 없다.


증명


4개 이상의 원소를 가진 부분집합이 있다고 가정하자.


원소가 a,b,c,d 이고, a<b<c<d 라고 하면


$$b-a = 2^x, c-b = 2^y, d-c = 2^z$$가 된다.


모든 차이가 2의 거듭제곱꼴로 나오기 위해서는 $x=y, y=z$ 형태가 되어야 하며 이를 거리 형태로 다시 표현하면


$$dist(d-a) = 3*dist(b-a)$$ 형태가 된다.


그런데 3은 2의 거듭제곱이 아니므로 모순이 된다.


따라서 4개 이상의 원소를 가진 부분집합을 만들 수 없으며, 모든 부분집합은 최대 3개까지만 원소를 가지게 된다.

Powers of Two - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.