심심할 때 풀어보기 좋은 간단한 고등학교 수학 문제

일본 수학 올림피아드 2023년 예선 9번 문제인데, 올림피아드 치고는 생각보다 어렵지 않아서 가져와봄

고등학생 때 확통을 좀 했거나, 이건 예상이지만 아마도 프로그래밍 쪽 일을 하고 있다면 간단하게 풀 수 있을거라 생각함
다음은 풀이 예시

먼저 떠올릴 것은 절댓값을 거리라고 생각할 수 있다는 점임.
문제에서 주어진 상황을 생각해보면, 수직선 위에서 1부터 2023까지 모든 점을 한 번씩만 거치는 경로의 길이에 첫 번째 점과 마지막 점의 좌표를 더했다고 볼 수 있음.
그런데 이렇게 문제를 보면 영 깔끔한 맛이 없음. 그래서 다들 식을 변형해서 p1과 p2023을 묶어주면 예쁠 것 같다는 생각이 들거임.
이를 위해서 p0=0을 도입하고, p0을 두 개 빼주고 각각 p1과 p2023에 하나씩 붙인 후 절댓값으로 묶으면 abs(p1-p0), abs(p0-p2023)의 꼴이 나옴. 그러면 이제 식의 의미가 깔끔해지는데, 원점에서 시작해서 1부터 2023까지를 한 번씩 찍고 다시 원점으로 돌아올 때의 길이가 됨.

여기에서 우리는 좌변의 최솟값을 생각해볼 수 있음. 우변이 4048인데 0에서 2023을 한 번 찍고 돌아오려면 직선으로 달려도 4046이니까 조건을 만족하는 경로는 딱 1만큼만 가다가 반대 방향으로 꺾을 수 있음. 즉, 2023을 찍기 전이라면 10을 찍었다가 다시 8을 찍으면 8부터 10까지를 두 번 더 거치는데, 이러면 4046에 2*2가 더해져서 길이가 4050이 되니까 이런 순열은 불가능함.
딱 1만큼만 꺾을 수 있다는 건, 이 두 점을 묶을 수 있다는 뜻이 됨. 2023은 반환점 역할을 해야 하니까 제외하고, 1부터 2022 중에서 연속한 둘을 골라 묶으면 2021개가 됨. 이제 이 2021개 중 2023까지 갈 때 찍을 점을 적당히 고르고 나머지는 원점으로 돌아갈 때 찍을 점으로 쓰면 조건을 만족하니까, 그 경우의 수만 계산하면 문제는 해결. 묶인 두 개의 점은 갈 때 골랐으면 큰 거 먼저 찍고 작은 걸 찍고, 아니라면 작은 걸 먼저 찍으면 되겠지.

2021개 중 k개를 고르는 경우의 수를 묻는 문제가 되었으므로, 2021Ck를 k=0부터 k=2021까지 모두 더하면 이항계수의 성질에 따라 2^2021이고, 두 점을 묶는 경우가 2021가지이므로 다시 이 둘을 곱해주면 답은 2021*2^2021.