당사의 최근 퍼즐 모음 역사적으로 상업과 정부, 예술과 과학의 상징인 겸손한 이중 팬 저울을 특징으로 합니다. 균형 저울은 레크리에이션 수학에서도 인기가 있습니다. 균형 퍼즐은 명확하고 논리적인 추론이 필요하며 수학적 일반화에 적합합니다. 방법을 보자 콴타 독자들은 아래 퍼즐에서 이러한 특성의 균형을 맞추었습니다.
퍼즐 1
똑같은 모양의 동전 XNUMX개가 있습니다. 하나는 위조품이며 무게가 동일한 다른 것보다 가볍습니다. 두 개의 무게에서 나쁜 동전을 찾으십시오. 위조 동전을 찾을 수 있는 최대 동전 수에 대한 일반 공식을 찾으십시오. x 무게.
간단한 버전의 문제를 해결하면 종종 솔루션의 열쇠가 드러납니다. 이 경우 동전이 세 개뿐이고 하나는 다른 두 개보다 가볍다고 상상해 보십시오. 그들 중 하나를 다른 둘 중 하나에 대해 무게를 잰다면 균형을 잡을 수도 있고 그렇지 않을 수도 있습니다. 그렇지 않은 경우 어느 것이 더 가벼운지 알 수 있습니다. 그들이 균형을 이루면 세 번째 것은 가벼운 것입니다. 단일 계량만 필요합니다.
따라서 이 퍼즐에서 첫 번째 계량에서 가벼운 동전을 포함하는 세 개(또는 그 이하) 그룹을 분리할 수 있다면 한 번만 더 계량하면 됩니다. XNUMX개를 다른 XNUMX개와 균형을 맞춰 수행할 수 있습니다. 두 그룹이 불균형한 경우 가벼운 그룹을 포함하는 그룹을 찾았고 두 번째 무게 측정을 위해 위와 같이 진행할 수 있습니다. 균형이 맞으면 나머지 두 개의 동전을 서로 비교하여 무게를 측정하면 가벼운 동전을 찾을 수 있습니다.
이것은 무게가 측정되지 않은 그룹에 XNUMX개가 있는 경우에도 작동하므로 XNUMX개의 동전으로 시작할 수 있습니다. 이 논리에 따라 세 개의 동전으로 시작하여 각 추가 무게에 대해 이전에 가지고 있던 동전 수의 세 배에서 가벼운 동전을 찾을 수 있습니다. 최대 동전 수를 알려주는 공식 n in w 따라서 칭량은 n = 3w.
퍼즐 2
똑같은 모양의 동전이 12개 있습니다. 하나는 동일한 무게를 가진 다른 것보다 무겁거나 가볍습니다.
-
세 가지 무게로 나쁜 동전을 찾으십시오.
-
XNUMX번의 저울에서 나쁜 동전을 찾을 수 있는 최대 동전 수는 몇 개입니까? 가짜 동전을 찾는 방법을 설명하십시오.
이 퍼즐에 대한 해결책은 다음과 같이 잘 설명되어 있습니다. 널 어서 말리다, 그는 또한 세 번의 무게로 13개의 동전 중에서 불량 동전을 실제로 감지할 수 있음을 보여주었습니다. 다음은 Ted의 솔루션입니다(각 경우에 세 가지 무게를 구분하기 위한 들여쓰기 포함).
4개의 동전 대 4개의 동전의 무게를 측정하여 시작합니다.
사례 1: 균형이 맞지 않는 경우 두 번째 계량을 위해 저울의 양쪽에 무거운 쪽을 각각 2개씩 놓고 가벼운 쪽을 각각 1개씩 놓습니다.
1a: 균형이 맞지 않으면 나쁜 동전은 여전히 무거운 쪽에 있는 2개의 동전이거나 여전히 밝은 쪽에 있는 단일 동전입니다.
두 개의 가능한 무거운 동전의 무게를 잰 다음 나쁜 동전은 둘 중 더 무겁거나 균형이 잡힌 경우 하나의 가벼운 동전입니다.
1b: 두 번째 무게가 균형을 이루면 불량 주화는 첫 번째 무게의 가벼운 쪽에서 사용하지 않은 2개 중 하나입니다.
그것들을 서로 무게를 재면 더 가벼운 것이 나쁩니다.
사례 2: 균형이 맞으면 불량 동전은 남은 5개 중 하나입니다. 이미 칭량된 3개(좋은 것으로 알려진)에 대해 3개를 칭량합니다.
사례 2a: 균형이 맞지 않으면 나쁜 동전이 그 3개 중 하나이고 가벼운지 무거운지 알 수 있습니다.
세 번째 가중치는 서로에 대한 것 중 2개입니다. 균형이 맞지 않으면 나쁜 동전을 식별하고 균형이 맞으면 세 개 중 마지막입니다.
사례 2b: 두 번째 무게가 균형을 이루면 불량 동전이 나머지 2개 중 하나입니다.
알려진 좋은 동전에 대해 둘 중 하나의 무게를 잰다. 이 결과가 균형이 맞지 않으면 이 새 코인은 불량이며 무거운지 가벼운지 알 수 있습니다. 이 결과가 균형을 이루면 13번째 동전은 불량이지만 무거운지 가벼운지 알 수 없습니다(알 필요가 없으므로 끝냈습니다).
널 어서 말리다 또한 40개의 무게에 대한 최대 동전 수는 XNUMX개임을 보여주었습니다. 이 퍼즐의 공식은 다음과 같습니다. n = (3w - 1)/2.
나머지 퍼즐의 경우 일반화된 공식은 여전히 전문 수학자에 의해 조사 중이며 출판된 논문의 주제이며, 그 중 일부는 다음과 같이 인용되었습니다. Rainer aus dem 봄. 나는 우리가 퍼즐에서 고려하는 적은 수의 동전에 대한 솔루션으로 자신을 제한하고 이러한 경우에 사용된 방법에서 자연스럽게 따르는 일반화에 대해서만 언급할 것입니다.
퍼즐 3
이것은 퍼즐 1의 변형입니다. 다시 XNUMX개의 똑같이 생긴 동전이 있으며 그 중 하나는 다른 것보다 가볍습니다. 그러나 이제 세 개의 저울이 있습니다. 척도 중 두 개는 작동하지만 세 번째 척도는 깨져 무작위 결과를 제공합니다(때로는 맞고 때론 틀립니다). 어느 눈금이 깨졌는지 모릅니다. 가벼운 동전을 찾는 데 얼마나 많은 무게가 필요합니까?
문제 1에서 보았듯이 이것은 균형이 잘 잡혀 있는 두 번의 칭량만 있으면 됩니다. 우리는 또한 두 개의 좋은 저울이 항상 일치한다는 것을 알고 있으므로 세 개의 저울 모두에 대해 각각의 칭량을 반복하면 독자가 제안한 대로 XNUMX개의 칭량에 대한 답을 얻게 됩니다. 더 적은 수의 칭량으로 하려고 하면 약간 까다로워집니다. 두 저울에 같은 동전의 무게를 재는 것만으로는 좋은 저울을 식별할 수 없습니다. 서로 동의하더라도 둘 중 하나가 여전히 나쁜 저울일 수 있기 때문입니다. (이는 또한 잘못된 정보나 무작위 정보가 진실을 난독화할 수 있음을 보여줍니다.)
사실, 이 문제는 매우 영리하게 단 XNUMX번의 칭량으로 해결할 수 있습니다! Rainer aus dem 봄 이 퍼즐을 위해 만들어진 것으로 보이는 새로운 표기법을 사용하여 솔루션을 게시했습니다. 하지만 거기에 가기 전에 상황을 보다 직관적으로 만들 수 있는 시나리오를 상상해 보시기 바랍니다.
당신이 자동차에 0, 1, 2 숫자만 사용하는 두 자리 번호판이 있는 작은 나라에서 뺑소니를 수사하는 형사라고 상상해 보십시오. A, B, C 세 사람이 이 사건을 목격했습니다. 그 중 두 명은 항상 XNUMX지선다형 질문에 정확하게 답하고, 한 명은 완전히 무작위로 답합니다. 당신은 무작위 응답자가 누구인지 모릅니다. 더 많은 정보를 얻으려면 그들 각각에게 단 하나의 XNUMX가지 선택지 질문을 하고 진실을 말하는 사람을 선택해야 합니다.
방법은 다음과 같습니다. A에게 첫 번째 숫자가 0, 1 또는 2인지 묻습니다. A가 2라고 가정해 보겠습니다. B에게 두 번째 숫자가 0, 1 또는 2인지 묻습니다. B가 1이라고 가정해 보겠습니다. 그런 다음 C에게 다음 세 가지 진술 중에서 선택하도록 요청하세요.
- A만이 진실을 말하고 있다.
- B만이 진실을 말하고 있다.
- 둘 다 진실을 말하고 있습니다.
당신은 C가 당신에게 말하는 것을 믿고 그 사람에게 다른 숫자에 대해 질문할 수 있습니다. 그 이유를 알아보려면 A가 거짓말을 하고 있다면 C는 신뢰할 수 있고 B가 진실을 말하고 있다고 말할 것이라는 점을 고려하십시오. 두 번째 숫자는 실제로 1이고 첫 번째 숫자에 대해 B에게 질문할 수 있습니다. 마찬가지로 B가 거짓말을 하면 C는 다시 신뢰할 수 있으며 A가 진실을 말하고 있다고 말할 것입니다. 그러면 첫 번째 숫자는 실제로 2이고 두 번째 숫자에 대해 A에게 질문할 수 있습니다. 마지막으로 C가 거짓말을 하면 A와 B 모두 신뢰할 수 있으므로 C가 말하는 사람을 믿고 선택할 수 있습니다. (그리고 C가 A와 B 모두가 진실을 말하고 있다고 말하면 둘 다 진실이어야 합니다.) 여기서 핵심은 질문을 선택한다고 해서 C가 A와 B 모두에게 의심을 던지는 방식으로 거짓말을 하는 것을 허용하지 않는다는 것입니다. A와 B 중 적어도 하나는 신뢰할 수 있어야 하므로 임의의 답변일지라도 항상 C가 동의하는 것을 선택할 수 있습니다. XNUMX개 모두 동의하면 이미 두 자리 번호판을 모두 가지고 있는 것입니다.
이 이야기를 우리의 퍼즐로 다시 번역하는 방법은 다음과 같습니다. 저울은 A, B 및 C입니다. 번호판의 두 자리 숫자를 다음과 같이 동전으로 번역할 수 있습니다. 01은 동전 1, 02는 동전 2, 10은 동전 3, 11은 동전 4, 12는 동전 5, 20은 주화 6, 21은 주화 7, 22는 주화 8입니다. 예리한 독자는 이것이 기본 3(또는 삼항) 숫자 체계임을 인식할 것입니다. 또한 퍼즐 00에서와 같이 이 기술이 작동하는 1번째 동전에 사용할 수 있는 추가 가능한 숫자 XNUMX이 있습니다.
첫 번째 무게의 경우 동전을 첫 번째(기본 3) 숫자로 나누므로 세 그룹은 동전 [1, 2], [3, 4, 5] 및 [6, 7, 8]이 됩니다. 저울 A의 [3, 4, 5]에 대해 [6, 7, 8]의 무게를 쟀습니다. A가 잘 작동하면 퍼즐 1에서와 같이 올바른 첫 번째 숫자 그룹을 갖게 될 것입니다. 유사하게, 저울 B에서 두 번째 무게를 다는 그룹 두 번째 숫자가 동일한 [1, 4, 7], [2, 5, 8] 및 [3, 6]이 됩니다. B가 잘 작동하면 올바른 두 번째 숫자를 갖게 됩니다. 세 번째 무게 측정의 경우 저울 C에서 A가 식별한 그룹과 B가 수행한 그룹의 무게를 측정합니다. 이 예에 따라 21의 경우 그룹은 [6, 7, 8] 및 [1, 4, 7]이 됩니다. 동전 7은 동시에 양쪽에 놓을 수 없으므로 생략하고 [6, 8]과 [1, 4]를 서로 무게를 잰다. A와 B가 모두 신뢰할 수 있는 경우 7이 실제로 정답이며 C에서 어느 쪽이 더 가볍게 나오는지는 중요하지 않습니다. 우연히 C의 무게가 균형을 이루면 세 저울이 모두 일치하고 단 세 번의 무게 측정으로 답(동전 7)을 얻을 수 있습니다. A가 신뢰할 수 있고 B가 신뢰할 수 없는 경우 더 가벼운 동전은 [6, 8]에 있으며, 저울 C는 확인하고 B는 신뢰할 수 있고 A는 신뢰할 수 없으면 더 가벼운 주화는 [1, 4]에 있으며 저울 C 도 확인합니다.
그래서 우리는 세 번의 무게 측정에서 가벼운 동전을 확인하거나 두 그룹으로 좁혔고 작동하는 저울도 확인했습니다. 저울 A 또는 저울 B(둘 중 하나의 저울 C가 동의한 것)에서 네 번째 계량이 나머지를 수행합니다.
이 솔루션은 놀랍도록 아름답다고 생각합니다!
이 방법을 일반화하여 3가지 중 라이트코인을 찾을 수 있습니다.2x 3의 동전x + 주어진 저울 세트로 1개의 칭량. 따라서 81개의 주화에 대해 1,000개의 무게가 필요합니다. 더 많은 수의 코인(>~XNUMX)의 경우 더 강력한 솔루션 존재.
퍼즐 4
당신은 16개의 동전을 가지고 있으며 그 중 XNUMX개는 무겁고 무게가 같습니다. 나머지 XNUMX개는 가볍고 같은 무게입니다. 어떤 동전이 무겁고 가벼운지 모릅니다. 동전은 특별한 표시가 있는 것을 제외하고는 동일하게 보입니다. 좋은 저울 하나로 스페셜 코인이 가벼운지 무거운지 세 번의 무게로 알 수 있습니까? XNUMX개의 계량으로 시작하여 이 문제를 성공적으로 해결할 수 있는 최대 동전 수는 얼마입니까?
독자 중 한 명이 결론을 내렸듯이, 언뜻 보기에 이 퍼즐은 세 가지 무게로 수행하는 것이 거의 불가능해 보입니다. 그럼에도 불구하고, 약간의 영리함으로 그것은 할 수 있고, 둘 다 널 어서 말리다 와 Rainer aus dem 봄 올바른 솔루션을 제공했습니다. Ted는 주의를 기울일 가치가 있는 몇 가지 귀중한 일반 원칙을 제공했습니다.
첫째, 칭량에서 균형이 맞지 않는 결과를 얻을 때까지 특수 동전이 무거운지 가벼운지 판단하기에 충분한 정보가 없습니다. 따라서 불균형한 결과를 시도하고 강제해야 합니다.
둘째, 균형 잡힌 결과를 얻으면(특수 주화 A가 주화 B와 균형을 이룬다고 가정) 균형이 맞춰진 주화를 결합하고 두 개의 주화 C와 D에 대해 무게를 측정할 수 있습니다. 균형이 맞지 않으면 답이 있습니다. 그렇지 않으면 유사한 동전의 수가 두 배로 늘어나 다음 계량에서 균형이 맞지 않는 답을 얻는 데 도움이 될 수 있습니다. 다음 솔루션과 같이 초기 불균형 결과가 있는 경우 4의 거듭제곱(8, XNUMX 등)인 동전 수를 사용하여 이 프로세스를 역으로 수행할 수도 있습니다.
다음은 세 가지 칭량에서 모든 경우에 특수 주화 A의 유형을 식별할 수 있는 전체 절차입니다. (B, C, D는 무게 1(W1)에서 A와 같은 쪽에 놓인 세 개의 동전이고, X와 Y는 W1에서 사용되지 않은 두 개의 동전입니다.)
이 퍼즐은 러시아 수학자에 의해 발명되었습니다. 콘스탄틴 노프, 동전 무게 퍼즐의 세계 권위자. 그의 논문 중 많은 부분이 러시아어로 되어 있지만, 여러 개의 동전 퍼즐(다른 흥미로운 퍼즐 중에서)을 찾을 수 있습니다. 블로그 그의 협력자 Tanya Khovanova의.
일반화를 하자면 32개의 코인 중 16개는 무겁고 16개는 가벼운 코인 중 특수주화의 종류를 찾는데 이와 같은 방법이 적용되는지는 여러분에게 맡기겠습니다.
퍼즐 5
현재 n 동일하게 보이는 동전, 그 중 일부는 위조이며 다른 것보다 가볍습니다. 당신이 아는 전부는 적어도 하나의 위조 동전이 있고 위조 동전보다 정상적인 동전이 더 많다는 것입니다. 당신의 임무는 모든 위조 동전을 감지하는 것입니다.
적어도 하나의 가벼운 동전이 있고 가벼운 것보다 더 많은 일반 동전이 있다는 사실은 이 퍼즐을 처음 나타나는 것보다 덜 복잡하게 만듭니다. 동전 XNUMX개에서 XNUMX개까지의 무게 수를 살펴보겠습니다.
하나와 두 개의 동전의 경우 두 번째 조건에 가벼운 동전이 없을 수 있으므로 무게가 필요하지 않습니다.
세 개의 동전: 단 하나의 가벼운 동전. 퍼즐 1당 하나의 무게가 필요합니다.
네 개의 동전: 단 하나의 가벼운 동전. XNUMX회 추가 계량이 필요하므로 w = 2.
다섯 개의 동전: 하나에서 두 개의 가벼운 동전. 이것은 첫 번째 흥미로운 사례입니다. 문제는 하나의 동전을 하나에 대해 무게를 측정해야 합니까, 아니면 두 개의 동전에 대해 두 개의 무게를 비교해야 하는지입니다.
우리가 일대일로 무게를 잰다면 우리는 다음을 가질 수 있습니다:
- 두 개의 균형이 맞지 않는 무게: 두 개의 동전이 발견되었습니다. 우리는 끝났습니다.
- 두 개 중 하나의 균형 잡힌 무게: 균형 잡힌 동전은 정상이어야 하므로 마지막 동전은 다른 무게가 필요합니다. w = 3.
- 두 가지 균형 잡힌 칭량: 세 번째 칭량에서는 이전에 칭량한 동전 하나를 다른 동전과 비교하여 칭량합니다. 균형이 맞으면 5개 모두 정상이고 동전 XNUMX가 가벼운 것입니다. 우리는 끝났습니다. w = 다시 3. 균형이 맞지 않으면 두 개의 가벼운 동전을 찾았고 세 번 칭량했습니다.
대신에 XNUMX 대 XNUMX의 무게를 잰다면 동전이 양쪽에서 비슷하거나 다를 수 있는 가능성을 구별해야 하기 때문에 여전히 XNUMX개의 무게가 필요합니다. 소수의 주화를 함께 그룹화하여 무게를 다는 것은 단일 주화를 사용하는 무게에 비해 이점이 없는 것으로 보입니다.
이것은 다음을 위해 입증됩니다.
XNUMX개의 동전: XNUMX~XNUMX개의 가벼운 동전; w = 4.
XNUMX개의 동전: XNUMX-XNUMX개의 가벼운 동전; w = 5.
XNUMX개의 동전: XNUMX-XNUMX개의 가벼운 동전; w = 6. 이 솔루션의 구조는 다음과 같습니다.
- 먼저 한 동전을 다음 동전에 대해 네 번 무게를 잰다. 모든 동전이 사용됩니다.
- 최악의 경우: 네 가지 무게가 모두 균형을 이룹니다(서로 균형을 맞추는 두 개의 가벼운 동전이 있습니다).
- 다음 두 개의 무게 측정: 무게 1의 동전과 무게 2의 동전의 무게를 잰다. 마찬가지로 무게가 3인 동전과 무게가 4인 동전의 무게를 잰다.
- 이 무게 중 하나는 균형이 맞지 않아 두 개의 가벼운 동전을 식별합니다. 우리는 XNUMX번의 칭량을 마쳤습니다.
죄송합니다. 0, 0, 1, 2, 3, 4, 5, 6의 순서는 확실히 흥미롭지 않습니다. 정수 시퀀스의 온라인 백과사전!
As 요나스 퇴게르센 셸스타들리 지적해, 해결책은 다음과 같다. w = n - 작은 수의 경우 2이지만 큰 수의 경우 이것이 변경되지 않는다는 것을 증명하지 않았습니다. 일부에서 n, 여러 동전 계량을 사용하면 n - 2개가 필요할 수 있습니다. 2개의 동전에 대한 해를 XNUMX의 모든 거듭제곱으로 간단히 일반화할 수 있습니다. n − 2는 2의 모든 거듭제곱에 대한 가중치 수의 상한입니다.
Mark Pearson은 이 문제와 오류 수정 코드의 유사성에 대해 논의했으며 가능한 결과의 수에 기반한 정보 이론 접근 방식을 사용할 것을 제안했습니다. 그러한 접근 방식을 사용하여, 마이크 로버츠 보다 일반적인 경우에 대한 하한을 게시했으며, Rainer aus dem 봄 에 대한 근사치를 도출했습니다. Rainer 님도 게시했습니다. 상한 출판된 논문에서 그러나 경계가 낮은 n 따라서 위에서 고려한 작은 숫자에는 도움이 되지 않습니다. 따라서 4개의 동전에 대해 인용된 범위는 16에서 5까지의 범위를 제공하며, 우리의 답은 XNUMX입니다. J. 파예트 모든 퍼즐에 대한 추가 수학적 참조 및 범위를 제공합니다.
참여해주신 모든 분들께 감사드립니다. 이번 달의 Insights 상은 Ted와 Rainer aus dem Spring에게 공동으로 돌아갑니다. 축하합니다!
다음에 새로운 소식으로 만나요 인사이트.
