터보에게 불리하도록 괴물이 greedy하게 움직이기에 가능하면 최악인 상황으로 대각선 쫘라락 떠올렸고 구멍을 찾기 위해 한 쪽 끝부터 뻗어 내려오는 대각선 괴물 장벽이 있다고 치고 지그재그로 하향하는 방법을 떠올렸는데 여기서 사용된 greedy는 전체적 최악을 고려했다고 볼 수 없을까요?
머리 아프게 공부해서 이뤄낸 좋은 학력으로 강사를 하는 건 좋다고 생각합니다. 누군가를 가르칠 때 아마도 큰 보람을 얻겠죠. 근데, 유튜브가 돈이 잘 되긴 하나보네요? 저였으면 영재/과학고 입시나 대치동 수능 강사 쪽으로 했을텐데, 그리고 특히 수포자를 가르치면서 엄청난 스트레스 받을테고, 억까도 엄청 많을 거고…, 또 자기 자신의 우월함, 뛰어남을 알아주는 사람들도 많이 없을 거고… 아무튼 스스로 만족하시고 계시니까 계속 유튜브를 하시는 거 같네요.. 아마 수포자들도 이해할 만한, 흥미를 돋굴 수 있는 그런 영상 소재를 찾는 것도 힘들 거 같습니다.. 화이팅입니다!
애매한 어떤 문제에 대해 해답을 찾는 방법중 하나는 시작이 필요하고 그시점부터 절차를 밟아가는 과정속에 거짓이 없다면 문제는 풀리게 될것이다 그것이 상식중에 하나이다 그런 희망을 주는 좋은 내용이었습니다. 파란눈들이 마을에서 떠나야한다는 가정이 슬펏지만 가정을바꿔 더좋은 마을로 이사한다고 생각하면 될꺼같습니다^^
평균이 실수 r인 모집단에 대하여 각각을 a1,a2,a3,...인 수열 {an}로 나타내면 r=Sn/n이다 (단 Sn=sigma k=1 to n ak) 이때 S(n-1)=Sn-an이므로 Sn=S(n-1)+an이므로 r={S(n-1)+an}/n이다 그렇다면 an<r이라고 가정하자 an은 r보다 작으므로 an=r-k(단, k>0)이다 따라서 S(n-1)=n*r-r+k=(n-1)r+k이다 이때 S(n-1)/(n-1)은 {an-1}의 평균인데, an<r이므로 r보다 커야한다 그런데 {an}은 수열이므로 n은 자연수이고 k은 양의 실수이다 따라서 n>=2인 모든 자연수에 대하여 모순이 일어나며 n=1일 경우에는 S(n-1)이 성립하지 않으므로 역시 모순이다 즉, 귀류법에 의해 an>=r이고, 평균 r보다 크거나 같은 an이 반드시 존재하므로 제목의 명제는 항상 성립한다 Q.E.D. +정정) 단, {an}은 임의의 n에 대하여 an-1<=an을 만족하도록 정렬한 수열이다. S(n-1)/(n-1)을 r'이라고 하자 위의 식에 따라서 r'*(n-1)=(n-1)r+k이다 따라서 r'=r+k/(n-1)이다 그런데 a1,a2,a3,...,an-1은 모두 an보다 작거나 같다 따라서 그것들의 평균인 r'은 크거나 같은 an을 포함해 얻은 평균인 r보다 작거나 같아야만 한다 그런데 k는 양의 실수이고 평균은 두 수 이상에서만 구할 수 있으므로 n>=2이다 따라서 k/(n-1) 역시 양의 실수이고 r'은 r보다 크므로 모순이다 따라서 귀류법에 의해 an>=r이고 이하 내용은 동일하다
@@지오5 정정해야겠네요 단, {an}은 임의의 n에 대하여 an-1<=an을 만족하도록 정렬한 수열이다. S(n-1)/(n-1)을 r'이라고 하자 위의 식에 따라서 r'*(n-1)=(n-1)r+k이다 따라서 r'=r+k/(n-1)이다 그런데 a1,a2,a3,...,an-1은 모두 an보다 작거나 같다 따라서 그것들의 평균인 r'은 크거나 같은 an을 포함해 얻은 평균인 r보다 작거나 같아야만 한다 그런데 k는 양의 실수이고 평균은 두 수 이상에서만 구할 수 있으므로 n>=2이다 따라서 k/(n-1) 역시 양의 실수이고 r'은 r보다 크므로 모순이다 따라서 귀류법에 의해 an>=r이고 이하 내용은 동일하다
추가 설명(추가적인 조건)이 필요할 것 같아요. 왜냐하면 누구도 싫어하는 사람과 팀을 이루지 않을 수 있는 최소의 팀의 수는 결국 모든 사람이 팀을 안 이루면 누구도 싫어하는 사람과 팀을 이루지 않으니까 0이 될 꺼 같아서, 좀 더 조건을 부여하는게 맞을 것 같아요 누구도 싫어하는 사람과 팀을 이루지 않는다는게 (1) "누구도 싫어하는 사람과 팀을 이루지 않도록해서 모든 사람들이 팀을 이룬다." 인지, (2) "누구도 싫어하는 사람과 팀을 이루지 않지만 꼭 팀을 이룰 필요는 없다." (앞서 설명했던 것) 인지, (3) "어떤 사람이 팀을 이룰 수 없는 상황이라면, 팀을 굳이 이루지 않아도 되지만, 그렇지 않다면 그 사람은 무조건 팀을 이루어야한다." 인지, 만약 이것이라면 그 상황은 무엇을 말하는 건지 (1)의 경우라면 싫어하는 관계의 개수랑 무관하게 ⌈n/2⌉일 것 같아요. (맞는진 모름) 증명) 모든 사람들은 팀을 이루어야 하니, 싫어하는 관계의 개수랑 무관하게 그래프에 있는 모든 점 v에 대하여 deg(v)>=1임. 최소한의 팀의 수를 l(n,m)이라고 하면, 일단 {v1,v2,....,vn}을 그래프의 점의 집합이라고 하자. 만약, v1과 v2가 선으로 이어진다면 v1~v2라 하자. ㅁ만약 점의 개수가 짝수라면, v1~v(n/2+1), v2~v(n/2+2), ... , v(n/2)~v(n)은 모든 점에 대하여 deg(v)>=1이고 e(G)=n/2인 그래프가 된다. 따라서 l(n,m)은 그러한 edge의 최소이므로 l(n,m)<=n/2=⌈n/2⌉가 된다. ㅁ만약 점의 개수가 홀수라면, v1~v(⌈n/2⌉+1), v2~v(⌈n/2⌉+2), .... , v(⌊n/2⌋)~v(⌈n/2⌉+⌊n/2⌋=n), v(⌈n/2⌉)~v1은 모든 점에 대하여 deg(v)>=1이고 e(G)=⌈n/2⌉인 그래프가 된다. 따라서 l(n,m)은 그러한 edge의 최소이므로 l(n,m)<=⌈n/2⌉가 된다. l(n,m)>=⌈n/2⌉은 귀류법으로 풀면 될 것 같아요. 즉, e(G)<⌈n/2⌉인 G가 존재해서 G의 모든 점(v)의 deg(v)>=1이라고 가정하자. 그러면, n이 짝수라면, e(G)<⌈n/2⌉=n/2 , n이 홀수라면 e(G)<=⌊n/2⌋<n/2 즉, 모든 n에 대하여 e(G)<n/2 그러면, n/2 > e(G)=sum(deg(v))/2 >= n/2 ( n/2 > n/2이므로, 모순) 따라서, 모든 점(v)의 deg(v)가 1 이상인 e(G)<⌈n/2⌉의 G는 존재하지 않으므로, l(n,m)>=⌈n/2⌉이다. l(n,m)<=⌈n/2⌉이고, l(n,m)>=⌈n/2⌉이므로, l(n,m)=⌈n/2⌉이다. (2)의 경우라면 당연히 모든 사람이 참여하지 않은 0이 최소의 팀의 수가 될 것 같아요. (3)의 경우라면, 해당 경우가 뭘 말하는건지 좀 명확히해야될 것 같은데, 제가 떠오르는 팀을 이룰 수 없는 상황은 한 사람이 나머지 모든 사람을 싫어할 때인 것 같아요. 이런 경우가 아니면 해당 사람은 팀을 이룰 순 있으니까 무조건 이뤄야 돼죠. (3)이 제가 생각하는 상황이라면, 좀 복잡하게 될 것 같아요. ㅁ0<=m<(n-1)이면, n개의 점을 가진 완전그래프에서 m개의 선분을 어떻게 지우더라도, 모든 점의 degree는 1이상임. 따라서 (1)과 동일 (⌈n/2⌉) ㅁ(n-1)<=m<(n-1)+(n-2)이면, n개의 점을 가진 완전그래프에서 m개의 선분을 적절히 제거하면, 최대 1개의 점의 degree를 0으로 만들 수 있으니, ⌈n/2⌉ (만약 한 사람이 여러 팀을 가질 수 있다면) or ⌈n/2⌉-1 (만약 한 사람이 한개의 팀만 가질 수 있다면) 왜냐면, 한 사람이 여러 팀을 가지는 경우, v1~v2에서 v1에 인접합 모든 선을 지울 때, v2는 나머지 다른 점과 연결될 수 있음. 따라서, (3)조건에 의하여 연결되면 선이 보존되므로 ⌈n/2⌉ (그러면 deg(v)>1인 v가 생김) 한 사람이 한개의 팀만 가질 수 있다면, v1~v2에서 v1에 인접한 모든 선을 지우면, v2는 연결될 수 있는 점이 없음 (나머지 모든 점들은 연결되어있으므로) 따라서, 선의 개수가 보존되지 않고 ⌈n/2⌉-1 ㅁ(n-1)+(n-2)<=m<(n-1)+(n-2)+(n-3)이면, m개의 선분을 적절히 제거하여 최대 2개의 점의 degree를 0으로 만들 수 있으니, ⌈n/2⌉-1 (만약 한 사람이 여러 팀을 가질 수 있고, v1~v2 & deg(v2)>1에서 v1에 인접한 모든 선을 지울 때) ⌈n/2⌉ (만약 한 사람이 여러 팀을 가질 수 있고, v1~v2 & deg(v2)=1에서 v1에 인접한 모든 선을 지울 때) 왜냐면 , deg(v2)>1이면, v1~v2의 이 선을 제거해도 deg(v2)>=1이므로 굳이 선분을 추가할 필요가 없음 deg(v2)=1이면, v1~v2의 선을 제거하면 deg(v2)=0이므로 다른 점이랑 이어져야됨. 그러면 선이 보존됨. =>최소 팀의 수 = ⌈n/2⌉-1 만약 한 사람이 여러 팀을 가질 수 있다면 or ⌈n/2⌉-1 (만약 한 사람이 한개의 팀만 가질 수 있다면) 왜냐면, ⌈n/2⌉의 선에서 만약 2개의 점에 대한 선이 제거되면 반대쪽 두개의 점은 서로 이어질 수 있으므로 그 둘은 (3)조건에 의해 무조건 만나야 함. 따라서, 선 하나가 보존되므로 ⌈n/2⌉-1) 2번째에 의하여 deg(v)=0인 점의 모든 인접합 선을 제거할 수 도 있으나, 이건 머리 아파서 생략 이 과정을 계속 이어나가서 m이 커질수록 해당 상황과 조건들을 고려해서 ⌈n/2⌉에서 -1씩 줄어드는 값이 될 꺼 같아요. 물론, 당연히 개인적인 의견이라 틀렸을 확률이 매우 높습니다. (3)을 너무 복잡하게 했는데 좀 획기적인 아이디어 없을까요
@@이준원-g7r 저는 (4) 1명이 독립적으로 있는 것 또한 하나의 팀으로 본다는 쪽이 재밌을 것 같아요. 즉 어떠한 둘도 팀을 이루지 않는 건 n개의 팀이 생긴다는 것이고 이러면 당연히 팀 수는 최대가 되니 답이 아니겠죠. 이렇게 보면 soTiu님이 말하신 그래프를 색칠할 수 있는 최소 색의 수 비슷한 느낌이 되겠네요.
