칠판에 $1$이 $n$개 적혀있다. 매번 적당한 두 수를 골라 그 두 수를 지우고 대신 그 두 수의 합을 두 번 적는 작업을 한다. 우연히도 $h$번 작업을 하고 났더니 모든 $n$개의 수가 다 $m$이 되었다고 한다. 이때, $h\le \frac12 n \log_2 m$임을 보여라.
GD Star Rating
loading...
loading...
칠판에 $1$이 $n$개 적혀있다. 매번 적당한 두 수를 골라 그 두 수를 지우고 대신 그 두 수의 합을 두 번 적는 작업을 한다. 우연히도 $h$번 작업을 하고 났더니 모든 $n$개의 수가 다 $m$이 되었다고 한다. 이때, $h\le \frac12 n \log_2 m$임을 보여라.