라인에서 소수 방문
최근에 저는 Dicast : Rules of Chaos 라는 멋진 모바일 게임을하고 있는데이 게임 을 통해이 퍼즐을 만들게되었습니다.
이 퍼즐은 각 정수가 셀로 표현되는 무한한 수선으로 진행됩니다. 0으로 표시된 셀에서 시작합니다. 다음 10 개의 카드를 사용할 수 있습니다.
- 하나 : 오른쪽으로 한 셀 이동
- 2 : 오른쪽으로 2 셀 이동
- 셋 : 오른쪽으로 3 셀 이동
- 4 : 오른쪽으로 4 셀 이동
- 5 : 오른쪽으로 5 셀 이동
- 여섯 : 오른쪽으로 6 셀 이동
- 빼기 : 왼쪽으로 한 셀 이동
- 홀수 : 1, 3 또는 5 셀을 오른쪽으로 이동합니다. 숫자는 무작위로 균일하게 선택됩니다.
- 짝수 : 오른쪽으로 2, 4 또는 6 셀 이동합니다. 숫자는 무작위로 균일하게 선택됩니다.
- 무작위 : 1, 2, 3, 4, 5 또는 6 셀을 오른쪽으로 이동합니다. 숫자는 무작위로 균일하게 선택됩니다.
카드는 최종 목적지로 곧바로 이동하므로 중간에 다른 셀을 방문하지 않습니다. 각 카드를 한 번만 사용하고 순서에 관계없이 사용할 수 있습니다. 가장 많은 수의 고유 한 소수에 도달 하도록 보장 하기 위해 카드를 어떻게 사용할 수 있습니까? 즉, 어떤 난수를 선택하든 상관없이 가장 많은 수의 고유 한 소수에 도달 할 수 있습니까? 행운을 빕니다!
답변
우리가 얻을 수있는 최선은
6 소수
전체적으로.
하나의 가능한 전략
무작위가 아닌 카드 만 사용하여 가능한 한 많은 소수를 생성하는 것으로 시작하십시오. 2를 제외한 모든 소수가 홀수이고 0 (짝수)에서 시작하므로 최대 5 개의 홀수 소수 (홀수, 짝수, 짝수, 짝수, 홀수 + 홀수) 만 건너 뛸 수 있습니다. 그러나 2 단계를 넘어 서면 홀수, 홀수 (2), 홀수, 짝수, 짝수, 짝수와 같은 방식으로 홀수 카드를 최대한 활용할 수 있습니다. 실제로 가능합니다.$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$, 카드 사용 $3, -1, 5, 4, 2, 6$순서대로. 우리는 7 장의 카드를 가지고 있고 (모든 단일 단계가 소수를 제공하면 7 개의 소수를 제공함) 7 개의 카드의 합이 20 (복합) 이므로이 시점에서 6 개의 소수가 최적입니다.
6 개의 소수 (현재 숫자가 17 또는 19 임)를 밟으면 1 또는 3, 홀수, 짝수 및 무작위의 4 개의 카드가 있습니다. 남은 상수가 1이면 무작위 카드로 인해$6k+2$ 또는 $6k+3$ 그 결과뿐만 아니라 $+1$합성이다; 당신이 3을 가지고 있다면, 랜덤은 당신을 3의 배수로 강요 할 수 있습니다. 따라서이 시점에서 더 이상 소수를 보장 할 수 없으므로 얻을 수있는 최선은 6 소수 입니다.
다른 전략이 더 이상 발전하지 않는 이유
엄격한 주장은 아니지만 가능한 이유는 다음과 같습니다.
7 개의 숫자 카드를 사용하면 모든 합이 합성이기 때문에 최대 6 개의 소수를 얻을 수 있습니다. 그 사이에 임의의 카드를 삽입하면 "악마"가 무작위 풀에서 숫자를 선택하여 턴이 합성되고 전체 합계가 합성 상태로 유지 될 가능성이 매우 높습니다 (따라서 우리가 시도하지만 0 개의 소수를 추가합니다). . 내가 생각할 수있는 유일한 예외는 2 + Odd와 1 + Even입니다. 그러나 1은 소수가 아니며 (중에 소수를 잃음) 2 + Odd는 우리가 Odd 전에 3을 넘으면 최대 효용을 잃습니다 (6 -이미 제시된 프라임 솔루션).
컴퓨터 검증
최적의 결과가 실제로
순진한 Python 3 프로그램을 사용 하는 6 개의 소수 . 링크 된 버전은 9 개의 카드 (임의 카드 제외) 만 사용하며 내 로컬 컴퓨터에서 전체 코드를 실행하는 데 20 분 정도 걸렸습니다.
히스토리 확인을 제거하면 7 개의 소수 를 얻습니다 . (불행히도 프로그램은 최적의 동작을 보여주지 않습니다.) 분명히 최적의 동작은 홀수와 짝수를 모두 사용합니다. 둘 중 하나가 없으면 최적의 점수는 6입니다.