서로다른 네 실수 A,B,C,D가 있다.
이 네 실수중 두개의실수를 뽑아 대소를비교하는 시행을
최소 몇 번해야 최악의상황에서도 네 실수의 대소관계를
전부 알 수 있을까?
같은 문제에서 누가 3회로충분하다고 할때,
3회로 안되는 반례 하나를 보여주는거로는 적절한반박이아니지?
니가 이상한방법으로3번해서그래.
라는 소리가나올수잇으니..
나올수잇는 모든 3회의시행에대해서 안되는경우가 1개이상 존재한다.
를보여줘야 적절한 반박이지?
지금은 수가 작아서일일히할수잇지만
수가 만약 더커졋을때 누군가가 n회시행으로충분해.
라고하면 모든경우의 n회에 대해서 n회로는 안되는경우가1개이상 존재한다. 를 보여줘야되는거임?
- dc official App
어떠한 전략을 써도 분류가 안되는 경우가 있음을 보여야지. 이건 유명한 문제라서 풀이가 잘 알려져 있는데, 비교하고자 하는 사람의 전략을 고정하면 그 진행을 tree 형태로 쓸수있음. 첫 비교(어떤 비교든)를 하면 두 수중 어떤수가 큰지 2가지 경우가 있고, 각 경우마다 새로운 비교를 할텐데 그때마다 2가지 경우가 나오지.
즉 n번 비교하는 전략은 최대 2^n가지의 경우를 분류할수있는거임. 근데 m개를 실수의 대소관계는 (크기만 따졌을때) m!가지가 있으니까 m개의 수를 비교하려면 m!<=2^n이 되는 n번의 비교가 필요함
m=3일때는 정말로 3번으로 충분하고, n은 mlogm정도 되니까 m이 커지면 n>m도 증명은되겠지