2ⁿ−1과 2ⁿ+1 — 하나 차이로 틀리는 문제를 만드는 법

프로그래머들 사이에 오래된 농담이 있어요. 「세상에서 가장 어려운 문제는 두 가지예요. 이름 짓기, 캐시 지우기, 그리고 하나 차이로 틀리기.」 셋을 말하면서 둘이라고 하는 것 자체가 농담이에요. 하나 차이 실수는 그만큼 흔하고, 틀린 사람이 틀린 줄 모른다는 점이 특별해요. 계산이 거의 맞았기 때문이에요.

오늘 딸깍에 문제 두 개를 새로 넣었어요. 둘 다 고수 단계 문제이고, 둘 다 이 「하나 차이」를 노려요. 하나는 답이 2ⁿ − 1 쪽으로 하나 모자라고, 다른 하나는 2ⁿ + 1 쪽으로 하나 넘쳐요. 만들면서 무엇을 고민했는지 적어 둘게요. 아래에 답이 나오니, 먼저 풀어 보고 싶다면 여기서 멈추세요.

첫째 문제, 업다운 게임은 몇 번이면 될까

상대가 1부터 64 사이의 수를 몰래 정하고, 나는 수를 말해요. 상대는 「업」 · 「다운」 · 「정답」 셋 중 하나로만 대답해요. 가장 잘 말하면 많아야 몇 번 만에 「정답」을 들을까요? 정답을 맞힌 번도 세요.

많은 사람이 곧바로 이렇게 생각해요. 「반씩 줄이니까 2를 몇 번 곱해야 64인지 보면 되겠네. 2⁶ = 64니까 6번.」 그럴듯하지만 답은 7번이에요.

거꾸로 세면 보여요. 한 번만 말할 수 있으면 확실히 맞히는 건 1개뿐이에요. 두 번이면 가운데 하나를 말하고, 업이면 위쪽 1개 · 다운이면 아래쪽 1개가 남으니 3개까지 돼요. 세 번이면 가운데 하나와 양쪽 3개씩, 7개예요.

1번 →  1개
2번 →  3개
3번 →  7개
4번 → 15개
5번 → 31개
6번 → 63개
7번 → 127개

k번이면 2^k − 1개까지 가려요. 한 번 말할 때마다 그 수 하나를 「확인」하는 데 쓰기 때문에, 반으로 나누는 힘에서 하나씩 빠지는 거예요. 6번으로는 63개까지라 64는 딱 하나가 넘쳐요. 「2⁶ = 64니까 6번」은 마지막에 「정답」을 듣는 그 한 번을 빼먹은 셈이에요.

범위를 1~100에서 1~64로 바꾼 이유

처음 초안은 「1부터 100까지」였어요. 업다운 게임은 보통 그렇게 하니까요. 답도 똑같이 7번이에요. 그런데 검수에서 이 초안이 걸렸어요. 100은 2의 거듭제곱이 아니라서 「2를 몇 번 곱해야 100을 넘나? 2⁷ = 128이니 7번」이라고 대충 어림해도 답이 맞아 버려요. 틀린 생각으로 맞는 답이 나오면 그 문제는 아무것도 묻지 않은 문제예요.

64로 바꾸자 사정이 달라졌어요. 이제 「2⁶ = 64」가 너무 깔끔하게 떠올라서, 어림하는 사람은 6에서 멈춰요. 미끼가 제대로 물리는 자리예요. 그리고 그 6을 의심해 본 사람만 「6번이면 63개까지구나」라는 장면에 닿아요. 숫자 하나를 바꿨을 뿐인데 문제가 묻는 것이 「계산할 줄 아느냐」에서 「셈의 끝을 정확히 보느냐」로 바뀌었어요.

지문에 「정답을 맞힌 번도 세요」를 적은 것도 같은 이유예요. 이 약속이 없으면 「정답」을 듣는 번을 세느냐 마느냐로 답이 6과 7로 갈리고, 그건 생각의 차이가 아니라 말의 차이예요. 하나 차이를 노리는 문제일수록 어디서부터 어디까지 세는지를 지문이 못 박아 줘야 해요.

둘째 문제, 8겹을 잘랐는데 9조각

긴 종이띠를 길이가 반이 되게 세 번 접어요. 접힌 뭉치의 한가운데를 띠와 수직으로 한 번 자르고 펼치면 몇 조각일까요? 보기는 8 · 9 · 16 · 17이에요.

세 번 접으면 8겹이고, 가위는 한 번에 8겹을 지나가요. 그래서 「8조각」이 먼저 떠올라요. 색종이를 접어 구멍을 뚫으면 겹 수만큼 구멍이 생기는 경험이 있어서 더 그래요. 하지만 펼친 띠를 보면 가위 자국이 8군데예요. 끈을 8군데 자르면 토막은 9개예요. 자국 사이의 토막들은 접힌 선으로 이어져 있다가 펼쳐질 뿐, 따로 떨어지지 않아요.

1번 접기 → 2겹 → 자국 2곳 → 3조각
2번 접기 → 4겹 → 자국 4곳 → 5조각
3번 접기 → 8겹 → 자국 8곳 → 9조각

이번에는 2ⁿ + 1이에요. 울타리 기둥 셈과 같아요. 10m 울타리에 1m마다 기둥을 세우면 기둥은 10개가 아니라 11개죠. 자국을 세는 셈과 조각을 세는 셈이 하나 차이로 어긋나요.

16과 17은 다른 실수를 받는 보기예요. 「자르면 두 배가 된다」고 보면 16, 겹 수를 한 번 더 늘려 세고 +1을 하면 17이 나와요. 보기 넷이 각각 하나의 생각에 대응하도록 골랐어요. 아무 숫자나 채운 보기는 실수를 받아 주지 못하고, 그러면 틀린 사람이 왜 틀렸는지도 알 수 없어요.

이 답은 손으로만 믿지 않았어요. 접힌 종이의 좌표를 분수로 반사해 계산하는 방법과 격자로 직접 접어 보는 방법, 두 가지로 따로 검산했고 1 · 2 · 3번 접기에서 둘 다 3 · 5 · 9가 나왔어요. 자르는 자리도 가운데만 본 게 아니라 접힌 선 위가 아닌 96곳을 전부 잘라 봤는데 모두 9조각이었어요. 그래서 지문의 「한가운데」는 답을 바꾸는 조건이 아니라 상상을 돕는 말이에요.

고무줄 한 번, 하나 차이의 반대편

이 두 문제를 만들기 전에 새싹 단계에 「고무줄 자르기」를 넣었어요. 끈은 1번 자르면 2조각, 3번 자르면 4조각이에요. 그런데 동그란 고무줄은 1번 잘라도 1조각이에요. 끝이 없는 고리는 첫 가위질이 고리를 긴 끈으로 펴기만 하거든요. 그래서 고무줄을 4번 자르면 5조각이 아니라 4조각이에요.

세 문제를 나란히 놓으면 같은 질문을 다른 방향에서 하고 있어요. 세는 대상이 「칸」인가 「경계」인가, 그리고 끝이 열려 있나 닫혀 있나. 업다운은 「확인하는 한 번」이 칸 하나를 차지해서 하나 모자라고, 종이띠는 양 끝이 열린 줄이라 하나 넘치고, 고무줄은 끝이 닫혀 있어서 넘치던 하나가 사라져요.

하나 차이 문제를 만들 때 지키는 것

• 틀린 셈이 거의 맞아야 해요. 하나 차이가 아니라 두 배 차이로 틀리면 풀이자가 스스로 이상하다고 느껴요. 거의 맞는 답이 나와야 의심하지 않고 멈춰요.
• 틀린 생각으로는 정답이 안 나오게 범위를 골라요. 1~100이 아니라 1~64를 고른 이유예요. 미끼가 정확히 한 칸 옆에 떨어지도록 숫자를 맞춰요.
• 어디까지 세는지는 지문이 정해요. 「정답을 맞힌 번도 센다」 「한 번에 한 군데씩 자른다」처럼, 답이 말 해석으로 갈리지 않게 막아요.
• 작은 경우로 확인하는 길을 열어 둬요. 힌트가 늘 「1번 접으면?」 「1번 말하면?」에서 시작하는 건 그 때문이에요. 하나 차이는 작은 경우를 직접 세어 보면 바로 드러나요.

하나 차이 문제의 「아하」는 계산이 아니라 자기 셈을 다시 보는 순간에 와요. 「6번이면 63개까지야. 64는 딱 하나가 넘쳐!」 「8겹을 잘랐는데 9조각이네!」 이 한마디가 나오면 그 문제는 제 몫을 한 거예요. 오늘 문제들도 그 한마디를 기다리며 은행 끝에 들어갔어요.