[일반] 요즘 생각중인 문제

[익명(39.7)]

원소의 개수가 n개인 자연수의 부분집합이 있는데 이 집합의 부분집합들의 원소의 합이 모두 다르다면, 이 집합의 원소의 최댓값의 최솟값은 얼마일까?


n=1~6까진 얼추 답을 구했는데 OEIS 돌려봐도 딱히 조건에 맞는듯한 수열이 안보임..ㅜㅜ

[익명(124.53)]

2^(n-1) 아닐까

[익명(39.7)]

n=4일때만해도 3 5 6 7이 되더라고요

[유사수학자(lonelymath)]

그런 부분집합의 원소를 a_1 < a_2 < ... < a_n이라 할때, a_n의 최솟값에 대한 일반항은 알려져있지 않고, asymptotic한 값조차 알려져있지 않음. Erdos가 어떤 absolute constant c>0이 존재하여 a_n > c * 2^n이 성립할거라고 추측했는데 아직도 미해결이네.

[유사수학자(lonelymath)]

Erdos와 Moser가 a_n ≥ 1/4 * n^{-1/2} * 2^n임을 보였고, 현재까지 나온 결과들 중 가장 좋은 bound는 이 1/4를 다른 constant로 대체한것 뿐임.
자세한건
https://arxiv.org/abs/2006.12988

[유사수학자(lonelymath)]

반대로 충분히 큰 n에 대해서 a_n < 0.22 * 2^n을 만족하는 a_1 < a_2 < ... < a_n의 construction이 여태까지 알려진 최선의 construction이라 하네.
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r3

[익명(39.7)]

오.. 감사합니다

[ㅇㅇㅇ(223.39)]

이런 거 대체 어떻게 아는 거임? 개쩌네

[유사수학자(lonelymath)]

그냥 구글에 maximum element, distinct subset sums 키워드 검색하니 바로 나오던데