네 장 중 가장 작고 큰 카드만 잡을 수 있을까요? 교사는 서로 다른 실수 값의 카드를 무작위 순서로 한 장씩 보여 줘요. 숫자는 가리고 지금까지 나온 카드 사이의 크기 순서만 알려 줘요. 버린 카드와의 비교도 기억할 수 있어요. 학생은 매번 즉시 남길지 버릴지 정하며, 되찾거나 교환하지 못해요. 마지막에는 정확히 두 장을 남겨야 해요. 남은 장수가 필요한 수와 같으면 모두 남겨요. 성공은 전체에서 가장 작은 카드와 가장 큰 카드를 모두 남기는 거예요. 자체 종이 활동이며 실제 채용 규칙은 아니에요.
첫 두 장 뒤 j장을 남긴 상태의 최대 성공확률을 V_j라 해 볼까요? 0장이나 2장이면 두 선택 위치가 정해져, 양끝 카드가 그 위치에 있을 확률은 1/6입니다.
한 장만 남긴 경우, 그것이 버린 카드보다 작다고 해 볼까요? 세 번째는 앞선 두 장보다 아래·사이·위에 각각 1/3로 들어가요. 아래면 남긴 카드가 중간값이 되어 성공은 불가능해요. 사이면 버리고, 네 번째가 새 최댓값일 확률 1/4를 얻어요. 위면 남기고, 네 번째가 앞선 양끝 사이일 확률 1/2를 얻어요. 남긴 카드가 더 컸던 경우도 크기를 뒤집으면 같아요.
따라서 첫 장을 남겼다면 둘째는 버리고, 첫 장을 버렸다면 둘째는 남기는 쪽이 나아요. 한 최적 지시를 써 볼까요? 첫 장은 버리고 둘째는 남겨요. 셋째는 둘째와 함께 앞선 세 장의 양끝일 때만 남기며, 아니면 넷째를 남겨요. 24가지 순서를 따라가면 성공은 6가지예요. P_fixed는 미리 정한 두 위치를 남기는 확률이에요.
첫 선택은 유일하지 않아요. 최대값 1/4는 성공의 보장은 아니에요.
착안: MIT 순차 선택 §2. 두 장·양끝 목표는 자체 모형이에요.