옛날옛날 와인을 너무나도 사랑햇던 임금님이 잇엇어요
임금님은 30일 후에 와인 1000통으로 축제를 열기로 햇어요
그런데 세상에 스파이가 들어와 1000통중 단 한통에만 독을 섞엇네요
이 독은 마신뒤 30일 후에 죽는 신기한 독이에요
임금님은 오늘 쥐에게 와인을 먹여 축제날 독이 든 와인통을 찾아내려고 해요
동물을 사랑하는 임금님은 조건을 내걸엇어요
1. 사용하는 쥐의 수가 최소일 것
2. 그중에서 죽는 쥐의 최대 마릿수가 최소인 방법을 사용할 것
(1이 2보다 우선됨)
어떤 방법으로 쥐에게 와인을 먹여야 하며
그때 죽는 쥐의 최대 마릿수는 몇마리일가요???
안냐세요 이창무선새님다 어.. 최대 마릿수? 최댓값 구하는거면 이참수랑 관련이 이찌 아느까? 삼참수 미분하면 이참수 되는거쯤은 알지 않나? 일단 해보지 뭐. 삼참수 최고차항이 양수라 하면 대충 이케 그려지지 아느까? 이걸 에치엑스라 두고 에이치프라임엑스를 구해봐요오 구해보면~
999마리 사용하고 최대 마릿수는 1 이게 최선임
더줄일수잇삼
답 열마리임? 최대 마릿수도 열마리
사용하는 수는 맞는데 죽는 최대마릿수는 아니용
8
굿
근데 이게 최소인지는 증명 어케함
감각적직관?
통의 개수가 968~1013개 사이일때 8마리 나올거에요
섹션을 어케 나누냐가 핵심인거같은디 음..
일단은 10마리로 100통씩 섹션나뉘어서 먹고 한 섹션당 5마리 추가해서 20통으로 또 나누고 20통에서 5마리해서 4통나누고 나머지는 4마리로 1통씩 먹이면 24마리정도로 끝나긴 하는ㄴ데 더 줄이는건 모르겟음.. 소인수분해 문제인건가
쥐를 비트처럼 사용해서 삶/죽음을 0과 1로 쓴다고 생각해보세용
아 십진법말고 이진법으로
섹션으로 따지면 한마리가 500/500 다음한마리는 250/250/250/250 일케
아 이해함
빡대가리엿네
한마리 한마리 아님? 시간제약은 없으니까 먹이고 30일 기다리고 먹이고 30일 기다리고 ㅋㅋㅋㅋ
30일후에축제에용
최악의 경우에도 30000일이면 해결!
아하
와인통의 개수가 너무 많아서 줄여서 생각해봄 통이 2개면 필요한 쥐는 1마리 통이 3,4 면 필요한 쥐는 2마리 통이 5면 필요한 쥐는 3마리 임 여기서 적당히 관찰해보면 통의 개수가 2^k-1보다 많고 2^k보다 같거나 적으면 쥐는 k마리 필요함을 발견적으로 알 수 있음 따라서 필요한 쥐는 10마리
이와 비슷하게 발견적으로 죽는 쥐의 최대마리수의 최솟값은 8임을 얻음