AMC 10 · 2021 · #16
학년 7 counting답을 골라 클릭하세요.
이 문제의 핵심은 멈추는 규칙입니다. 기술자는 네트워크가 하나로 이어지는 순간 그만두므로, 마지막 케이블은 항상 일을 끝내는 케이블입니다. 따라서 가능한 최대 총수는 아직 끊겨 있는 네트워크가 가질 수 있는 케이블 수의 최댓값보다 정확히 하나 더 많습니다. 이렇게 하면 무작위 과정에 대한 질문이 깔끔한 극단값 질문으로 바뀝니다. 끊긴 상태를 갈 수 있는 데까지 밀어붙이면 됩니다(극단의 원리). 점 20개와 점 10개가 마주 보는 그림으로 그리면(그림 그리기) 끊긴 네트워크란 케이블이 하나도 건너가지 않는 두 그룹으로 갈라진 상태임이 보이고, 그룹의 크기에 문자를 붙이면(변수 도입하기) 최대로 만들 식이 나옵니다. 그리고 있는 케이블 대신 없는 케이블을 세면(관점 바꾸기) 최댓값이 한 줄에 드러납니다.
존재할 수 있는 케이블 전부 세기
가능한 케이블 전부를 셉니다.
케이블 하나는 A 점 하나와 B 점 하나를 맞춘 것이므로, 케이블을 세는 일은 곧 짝을 세는 일입니다.
모든 케이블은 한쪽의 점 하나와 다른 쪽의 점 하나를 이은 것이므로, 케이블을 세는 것은 짝을 세는 것이다.
▸ 왜?
두 끝점은 서로 상관없이 골라지므로, 개수가 곱해진다.
▸ 왜?
각 케이블이 정확히 한 짝을 가리키고 각 짝이 한 케이블을 가리키므로, 어느 쪽을 세든 같다.
끊긴 상태보다 케이블 하나 더
답은 끊긴 최대 배치보다 하나 많습니다.
끝나는 순간 종료되는 일은 언제나 가장 긴 미완성 상태보다 정확히 한 걸음 더 걸립니다.
7.EE.B.4Work Backwards끊긴 배치를 문자로 나타내기
끊긴 배치를 두 문자로 나타냅니다.
끊겼다는 말은 네트워크가 두 개의 섬으로 갈라졌다는 뜻이고, 각 섬은 자기 안에서만 케이블을 놓을 수 있습니다.
6.EE.A.2Introduce A Variable대신 없는 케이블을 세기
대신 없는 케이블을 셉니다.
끊긴 상태를 유지하는 가장 싼 방법은 버리는 케이블이 가장 적은 방법입니다.
7.EE.A.2Change Focus Count The Complement갈라놓기를 극단까지 밀어붙이기
갈라놓기를 극단까지 밀어붙입니다.
컴퓨터 한 대를 굶기는 것이 네트워크를 끊어 두는 가장 싼 방법이고, 굶기기 가장 싼 대상은 놓을 수 있는 케이블이 가장 적은 컴퓨터입니다.
4.OA.A.3Extreme Principle191개면 반드시 끝난다는 확인
하나 더하면 191입니다.
빈틈 9개를 B 브랜드 컴퓨터 10대에 뿌리면 한 대는 반드시 멀쩡하게 남고, 그 한 대만으로 사무실 전체가 묶입니다.
7.EE.B.4Extreme Principle모든 것이 이어지는 순간 끝나는 일은 가장 버티는 끊긴 상태보다 딱 한 걸음 더 갈 수 있고, 끊긴 상태를 유지하는 가장 싼 방법은 놓을 수 있는 케이블이 가장 적은 컴퓨터 한 대를 빼놓는 것입니다.
- 존재할 수 있는 케이블 전부 세기
- 끊긴 상태보다 케이블 하나 더
- 끊긴 배치를 문자로 나타내기
- 대신 없는 케이블을 세기
- 갈라놓기를 극단까지 밀어붙이기
- 191개면 반드시 끝난다는 확인