총합과 제품 퍼즐

Sum and Product Puzzle

해답에 대한 충분한 정보가 없어 보여서 불가능 퍼즐이라고도 불리는 합과 곱 퍼즐은 논리 퍼즐이다.1969년 한스 프로이덴탈에 [1][2]의해 처음 출판되었고, '임파서블 퍼즐'이라는 이름은 마틴 [3]가드너에 의해 만들어졌다.그 퍼즐은 쉽지는 않지만 풀 수 있다.비슷한 버전의 퍼즐이 많이 있습니다.

퍼즐

X와 Y는 1보다 큰 두 개의 서로 다른 정수입니다.합계는 100 이하이고 Y는 X보다 크다. S와 P는 두 명의 수학자(따라서 완벽한 논리학자)이다. S는 X + Y, P는 X × Y 곱을 안다. S와 P는 이 항의 모든 정보를 알고 있다.

다음과 같은 대화가 이루어집니다(참가자 모두 사실을 말하고 있습니다).

  • S는 "P는 X와 Y를 모른다"고 말한다.
  • P가 'X와 Y를 알 수 있게 됐다'고 합니다.
  • S는 "X와 Y도 알게 되었다"고 말한다.

X와 Y가 뭐죠?

설명.

개념과 관점이 명확해지면 문제는 오히려 쉽게 해결된다.S, P, O는 X+Y, P는 X+Y, 옵서버 O는 X·Y의 합을 알고 있습니다.3자 모두 같은 정보를 유지하면서도 다르게 해석한다.그리고 그것은 정보의 게임이 된다.

A를 A=B+C의 두 항으로 나눈 것을 2-소수라고 하자.Goldbach의 추측이나 이러한 2-split의 제품 B·C가 유일하다는 사실 같은 고급 지식이 필요하지 않다(즉, 곱해도 동일한 결과를 얻을 수 있는 다른 두 개의 숫자는 없다).그러나 골드바흐의 추측에 따르면, P는 반소수라면 X와 Y를 즉시 알 수 있다는 사실과 함께, 모든 짝수를 두 소수의 합으로 쓸 수 있기 때문에 x+y의 합은 짝수일 수 없다는 것을 추론할 수 있다.그 두 숫자의 곱은 반소수일 것이다.

스텝 1. S(Sue), P(Pete), O(Otto)는 5에서 100(X > 1, Y > X는 5부터 시작해야 함) 범위의 2분할로 구성할 수 있는 모든 제품의 표를 만듭니다.예를 들어 11은 2+9, 3+8, 4+7 및 5+6으로 2분할할 수 있습니다.각 제품은 18, 24, 28, 30이며 플레이어는 테이블에서 각 제품 옆에 체크 표시를 합니다(표 1).완료되면 체크 마크가 없는 숫자도 있고 1개 또는 여러 개의 숫자가 있는 숫자도 있습니다.

2단계. Sue는 이제 자신의 합과 모든 2분할을 살펴봅니다.그녀는 모든 2분할이 고유하지 않은 제품을 가지고 있다는 것을 알게 되었습니다. 즉, 다른 가능한 합계의 2분할인 다른 인수분할이 존재합니다.Step 1의 표에서 모든 제품에 두 개 이상의 체크 마크가 표시되어 있는 것을 알 수 있습니다.그녀는 이 사실 때문에 Pete가 제품을 보고 X와 Y 요인을 고유하게 결정할 수 없다는 것을 깨달았습니다(적어도 후보 제품 중 하나에는 체크 표시가 하나만 있어야 했습니다).그래서 그녀는 "P는 X와 Y를 알 수 없다"고 외친다.Pete와 Otto가 이 말을 들었을 때, 그들은 Sue의 합계와 관련된 어떤 상품도 특별하지 않다는 정보를 얻는다.가능한 합계를 하나씩 살펴봄으로써, 이제 Sue, Pete, Otto는 각자 모든 합계의 목록을 작성할 수 있습니다(표 2).표에는 2분할에 고유하지 않은 제품이 있는 모든 합계가 포함되어 있습니다. 즉, 표 1에 두 개 이상의 체크 마크가 있는 것입니다.Sue, Pete 및 Otto는 후보 합계의 표를 만들었습니다(Sue는 이미 합계를 알고 있지만 Pete의 생각을 추적할 필요가 있습니다).

3단계. 표 2의 새로운 정보를 고려하여 Pete는 다시 한 번 자신의 제품을 살펴봅니다.처음부터 합계로 간주되었던 5와 100 사이의 모든 숫자와 비교하여 1개를 제외한 그의 제품의 가능한 2분할의 합계는 표 2에서 사라졌다.남은 것은 그가 제품 X·Y를 알고 있는 두 개의 숨겨진 숫자 X와 Y의 합뿐입니다.합계와 곱을 보면 개개의 숫자를 알 수 있기 때문에 그는 Sue에게 "X와 Y를 알 수 있다"고 말한다.피트는 이제 끝났고 게임을 종료합니다.

4단계. Sue와 Otto는 표 1을 다시 계산한다. 이번에는 표 1과 같이 5에서 100 사이의 모든 숫자 대신 표 2에 있는 합계에서 2분할의 곱만 계산한다.이 업데이트된 테이블을 표 1B라고 합니다.Sue는 자신의 2분할의 모든 곱을 살펴본 결과, 표 1B에 딱 한 개만 표시됩니다.이것은 피트가 가지고 있는 제품임에 틀림없고, 그녀는 그들의 합과 곱에서 피트만큼 쉽게 두 숫자를 추론할 수 있다.그래서 그녀는 오토에게 "이제 나도 X와 Y를 안다"고 말한다.Sue도 이제 끝났고 Otto만 남았다.

5단계. 4단계의 정보에서 오토는 표 2의 모든 합계를 스캔하여 표 1B의 단일 2분할 중 하나의 눈금 마크가 있는 것을 찾습니다.원하는 것은 하나의 체크 마크만 가질 수 있습니다.그렇지 않으면 Sue는 X와 Y를 확실히 알 수 없습니다.마지막으로, 오토는 원하는 합계에 도달하게 되는데, 이 합계는 공교롭게도 유일하게 이러한 성질을 가지고 있기 때문에 원래의 문제를 독특한 해결책으로 해결할 수 있게 됩니다.오토의 임무도 이제 끝났다.

솔루션

솔루션에는 X와 Y가 4와 13으로 되어 있으며, P는 처음에 제품이 52인 것을 알고 S는 합계가 17인 것을 알고 있습니다.

처음에 P는 해결책을 모른다. 왜냐하면

52 = 4 × 13 = 2 × 26

그리고 S는 제약조건 내에서 17에 대한 모든 가능한 합계가 비슷하게 모호한 산물을 생성하기 때문에 P가 해를 모른다는 것을 알고 있다.그러나, 각자가 상대방의 진술에 따라 다른 가능성을 배제함으로써 해결책을 도출할 수 있으며, 이는 독자가 제약조건에 따라 해결책을 찾기에 충분합니다.

기타 솔루션

이 문제는 [2]일반화할 수 있습니다.바인딩된 X + Y 100 100은 다소 의도적으로 선택됩니다.X + Y의 한계가 변경되면 솔루션의 개수가 변경될 수 있습니다.X + Y < 62 의 경우는, 해결 방법이 없습니다.솔루션 X = 4, Y = 13이 경계 내에 적합되므로 처음에는 직관에 반하는 것처럼 보일 수 있습니다.그러나 이러한 경계 사이의 숫자를 합한 요소를 갖는 제품을 제외함으로써, 모든 비해결책을 더 이상 여러 가지 방법으로 인수할 수 없게 되어, 그 정보는 문제에 대한 해결책을 전혀 산출하지 못하게 됩니다.예를 들어 X = 2, Y = 62, X + Y = 64, X·Y = 124의 곱 viz. 4·31은 35가 된다.그 후, S가 P가 제품의 요인을 알 수 없다고 선언하면 35는 제외된다. 64의 합이 허용되었다면 알 수 없었을 것이다.

한편 한계값이 X + Y 85 1685 이상일 경우 두 번째 용액 X = 4, Y = 61이 나타난다.따라서 그 이후로는 더 이상 고유한 해결책이 없다는 의미에서 문제를 해결할 수 없습니다.마찬가지로 X + Y 1970 1970 이상이면 세 번째 솔루션(X = 16, Y = 73)이 나타납니다.이 세 가지 솔루션 모두 하나의 소수가 포함되어 있습니다.소수가 없는 첫 번째 용액은 X + Y 25 2522 이상에서 나타나는 네 번째 용액이며, X = 16 = 2·2·2·2, Y = 111 = 3·37이다.

조건 Y > X > 1이 Y > X > 2로 변경되면 124 < t < 5045 의 임계값 X + Y µ t 에 대해 하나의 솔루션이 존재하며, 그 후 여러 솔루션이 존재합니다.124 이하에서는 솔루션이 없습니다.해결책의 임계값이 상승한 것은 놀라운 일이 아닙니다.직감적으로 소수 2를 계수 X로 사용할 수 없게 되면 문제 공간이 "확대"되어 주어진 합계 A에서 가능한 곱 X·Y가 적어진다.솔루션이 많은 경우, 즉 t가 높을 경우 일부 솔루션은 Y > X > 1의 원래 문제와 일치합니다(예: X = 16, Y = 163).

대신 어떤 임계값 t의 조건 X + Y tt가 X·Y u로 교환되면 문제의 외관이 바뀝니다.더 적은 계산으로 더 쉽게 해결할 수 있습니다.합계가 (t/2)·(t/2)·(t/2)인 두 인자의 최대 곱에 근거하여 u에 대한 적절한 값은 대응하는 t에 대해 u = t·t/4가 될 수 있다.이 문제의 해결 방법은 47 < t < 60, 71 < t < 80, 107 < t < 128, 131 < t < 144 의 범위로, 이 문턱치를 밑도는 해결 방법은 없습니다.대체 제제의 결과는 해법의 수나 내용 모두 원래 제제의 결과와 일치하지 않는다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Hans Proudenthal, Nieuw Archief Voor Wiskunde, 시리즈3, 제17권, 1969, 152쪽
  2. ^ a b Born, A.; Hurkens, C. A. J.; Woeginger, G. J. (2006). "The Freudenthal problem and its ramifications (Part I)" (PDF). Bulletin of the European Association for Theoretical Computer Science, EATCS. 90: 175–191.
  3. ^ 를 클릭합니다Gardner, Martin (December 1979), "Mathematical Games: A Pride of Problems, Including One That Is Virtually Impossible", Scientific American, 241: 22–30, doi:10.1038/scientificamerican0979-22.

외부 링크