퀴즈 하나

친구가 이메일로 다음의 문제를 보내왔습니다.
한번 풀어보실분? ^^

문이 100개가 있어. 모두 열려있다.
처음에는 2의 배수에 해당하는 문들을 반대 포지션 (즉, 닫음) 으로 바꾸었다. 2, 4, 6, 8 … 문들이 닫혔지.
그 다음에는 3의 배수에 해당하는 문들을 반대로 했다. 3번 닫히고, 6번은 열렸겠지.
이런식으로 4의 배수, 5의 배수 … 100의 배수까지 시행하면, 최종에는 몇 개의 문이 열려 있을까?

흠…. 잘모르겠네요. ^^

7 thoughts on “퀴즈 하나”

  1. 1부터 100까지 늘어놓습니다. 그리고 2부터 100까지 숫자들을 소인수분해를 합니다. 소인수분해를 한 다음 소인수 combination이 홀수개가 나오는가 아니면 짝수개가 나오는가를 살펴보면 그 숫자가 문이 닫히는가 아니면 열리느가를 판단할 수 있지요. 예를 들어 50의 경우 50=2*5^2이므로 소인수 2와 5 두개의 combination이 몇 개인지 보면 1*2에서 2는 두개 1*5*5에서 5는 세개 그래서 전체 여섯개의 combination이 생기고 여기서 1*1은 빼야하므로 6-1=5입니다. 그러니까 소인수의 승+1을 쭉 곱하고 여기서 1*1 하나만 빼주고 나오는 숫자가 홀수인가 짝수인가를 보고 그 숫자의 문이 열려있을까 닫혀있을까 판단해서 몇 개가 열려있나 세면 될 것같습니다. 예를 들어 50번째 문은 2의 배수 문을 닫고 5의 배수에서 다시 열고 10의 배수에서 닫고 25의 배수에서 열고 50에서 닫게 됩니다. 즉 소인수의 승의 갯수에서 나온 숫자 -1이 홀수일 경우 최종적으로 문을 닫게 됩니다. 반대로 100의 경우 2, 4, 5, 10, 20, 25, 50, 100에서 최종적으로 열게 됩니다. 100=2^2*5^2 (3*3-1=8) 그렇게 1에서 100까지 다 하면 되지 않을까 싶네요. 소인수의 경우 규칙이 없으니까 손으로 1부터 100까지 해야할 것같습니다. 규칙이 있을까요? 앞으로 재미있는 퀴즈 자주 올려주세요.

  2. 이거 은규가 야후 면접에서 봤던 문제네요. 맑은울림님이 거의 푸셨네요. 1부터 100까지 손으로 다 할 필요는 없구요. 약수의 개수가 짝수인 수의 특징을 찾으면 게임 오버.

  3. 제가 생각하기엔 이렇습니다.
    맑은울림의 설명처럼, 1을 제외한, 그리고 자신을 포함한, 약수가 짝수개이면 되거든요. (가령… 6은, 2,3,6 이렇게 세개가 약수이지요.)

    그런데,
    어떤 수의 약수는… A^m * B^n * C^p * D^q * …
    이렇게 표현이 될텐데요,

    어떤것의 ‘약수’라고 한다면…
    반드시 서로 다른 두 수를 곱해서 원래의 수를 이루어야 합니다. 따라서 원칙적으로 약수의 갯수는, 1을 빼고 자신을 포함시켜서 항상 홀수여야 하지요.

    그런데, 이게 짝수가 될 수 있는 방법은…
    ‘제곱수’인 경우입니다.

    즉,
    25 같은 경우에는…
    5*5 이니까… 1을 제외한 약수가 5와 25 두개밖에 없지요.

    따라서,
    1부터 100까지 중에서 제곱수를 다 찾으면 될 것 같습니다.

    1의 제곱, 2의 제곱, 3의 제곱… 해서 10의 제곱까지.

    그러므로 10개가 아닐까 싶습니다…만…
    맞나요?

  4. Bingo!

    중학교 때 배운 것 중에 약수의 개수는 (1+m)(1+n)(1+p)(1+q)… 라는 게 있기도 하구요.

  5. 생긴 것만 비슷한 이런 문제도 있네요. 관심있으시면 풀어보세요. 푸신 분께는 맛있는 밥 사드립니다.

    주어진 두 양의 정수 n과 k에 대하여 k>=n 이고 k-n은 짝수라고 하자. 이제 1번부터 2n번까지 번호가 붙은 2n개의 램프를 생각하자. 각각의 램프에는 켜짐/꺼짐 스위치가 부착되어 있고, 처음에는 모든 램프가 꺼진 상태이다. 하나의 램프를 택하여 스위치의 상태를 바꾸는 것을 ‘작동’이라 정의하고 k회의 연속한 작동을 ‘k-작동’이라 부르자.

    처음의 상태에서 시작하여, 1번부터 n번까지의 램프는 모두 켜지고 (n+1)번부터 2n번까지의 램프는 모두 꺼지도록 하는 k-작동의 수를 N이라 하고, 1번부터 n번까지의 램프는 모두 켜지고 (n+1)번부터 2n번까지의 램프는 모두 꺼져있는 상태는 같지만, (n+1)번부터 2n번까지의 램프가 중간과정에서도 단 한번도 켜진적이 없는 k-작동의 수를 M이라고 하자. N/M의 값은?

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.