[일반] 물2갤 올렸던문제 여기도 올려볼까

[익명(14.49)]

ㄱㄱ혓

[익명(175.223)]

최소 10마리랑 최대 8마리? 먹고 안먹고로 구분하려 할 때 2^n>=1000인 n은 최소 10이라서 10마리는 필요하고 10C0 + 10C1 + ... + 10Ck >=1000인 최소의 k는 8이니까 어떤 경우든 상관없이 많아야 k마리를 죽게하려면 k는 8은돼야하니까?

[익명(14.49)]

정답!

[g*cm/s^2(physics0907)]

명시적으로 경우를 구축하면 모든 통에 0~1000의 번호를 붙이고 번호를 2진법으로 표현. 단 번호 511=111111111_2는 붙이지 않음.. 1번 쥐에게는 2^0의 자리가 1인 통들 전부, 2번 쥐에게는 2^1의 자리가 1인 통들 전부,... n번 쥐에게는 2^{n-1}의 자리가 1인 통들 전부를 마시게 함 (n\le 10) 0~1000에서 자리수 중 1인 것이 총 9개인 것은 511뿐이며 이 번호를 가진 통은 없음. 따라서 독이 든 통의 번호가 몇이든 상관없이 죽는 쥐는 8 이하임.