이차항의 계수가 양수인 경우만 다뤄도 충분하다.
이차항의 계수가 0인 경우 최대 7개 (애초에 이차함수도 아님)
이차항의 계수가 음수인 경우 y=2를 기준으로 대칭하면 양수인 경우와 같은 문제로 환원됨.
이차함수의 특징 중에서 대칭축을 기준으로 한쪽이 증가, 한쪽이 감소 (R^2위에서)인 점을 이용함.
1. 이차함수는 함수임. 즉, 하나의 x에 대해 하나의 y가 대응됨.
2. 앞서 설명했듯이 증가 또는 감소함. 증가 또는 감소하지 않는 점은 대칭축과의 교점 뿐임.
즉, 격자 내부의 거의 대부분 (대부분의 격자에서는 전체)가 증가 또는 감소하고 일정하게 유지되는 점은 없다는거임.
이 두가지가 맞물리면 다음 정리를 얻을 수 있음
lemma. 증가만 하는 구간이라면, 이웃한 두 세로 격자칸들을 취했을 때 5개보다 많은 수의 격자 칸을 이차함수가 지날 수 없다.
proof. 이차함수가 지나는 격자칸을 1, 아닌칸을 0이라 하자.
5개 이상의 칸이 1이라면, 비둘기집의 원리에 의해 두 세로줄에서 모두 1이 되는 높이가 존재한다.
함수가 증가할때로 한정하자. 이차함수는 함수이므로 두 격자칸의 교점을 지난다.
이때 함수가 증가하므로 왼쪽 세로줄의 경우 교점보다 낮은 칸만 지날 수 있고, 오른쪽 세로줄은 높은 칸만 지날 수 있다.
조건을 만족하는 최대 1의 개수는 5. 감소할때는 대칭으로 자명.
추가로, 가능한 격자칸의 높이는 최대 4가지( [0,1],[1,2],[2,3],[3,4])임도 자명하다.
10개의 1을 가지는 이차함수는 쉽게 그릴수 있으므로 존재성은 보장된다.
11개 이상의 1을 가지는 이차함수가 존재한다고 가정하자.
4개의 1을 가지는 세로줄이 2개 존재하거나, 3개의 1을 가지는 세로줄이 셋 이상 존재해야 한다.
또는 각 세로줄의 1의 개수가 4,3,2,2여야 한다.
1. 4개의 1을 가지는 세로줄이 2개 존재한다면, 그 두줄 사이에 대칭점이 존재한다.
ㄱ. 4개의 1을 가지는 세로줄 2개가 [0,2] 또는 [2,4]라면 lemma에 의해 나머지 두 줄에는 최대 2개의 1이 존재한다. (실제로 2개 모두 존재하지는 않는다.)
ㄴ. 4개의 1을 가지는 세로줄 2개가 [1,3]이라면 lemma에 의해 나머지 두 줄에는 최대 2개의 1이 존재한다. (실제로 존재한다.)
ㄷ. 4개의 1을 가지는 세로줄 2개 사이에 다른 세로줄이 하나 존재한다면
두 세로줄 바깥에 존재하는 세로줄에는 lemma에 의해 하나의 1만 존재할 수 있다.
두 세로줄 모두 높이가 [0,1]인 격자 칸 내부를 이차함수가 지나므로 대칭점이 있는 세로줄을 [a,b]라 하면 [a,b]에는 높이가 [1,4]인 점을 지날 수 없다. (지나는 점 x=p가 있다고 가정할 때 [a,p]에는 증가하는 구간이 존재하고, [p,b]에 감소하는 구간이 있다는것과 동일한데, 이차함수는 감소하다가 증가해야하기 때문에 모순)
따라서 나머지 두줄에는 최대 2개의 1이 존재한다.
ㄹ. 4개의 1을 가지는 세로줄 2개 사이에 다른 세로줄이 둘 존재한다면
lemma에 의해 [1,3]에는 최대 2개의 1이 존재한다.
따라서 1의 경우에는 최대 10개의 1이 존재한다.
2. 3개의 1을 가지는 세로줄이 셋 존재하는 경우 적어도 두 3개의 1을 가지는 세로줄은 이웃하고 lemma에 모순이다.
3. 이차함수가 이웃한 두 세로줄에 모두 둘 이상이 있는 경우 둘 사이에 대칭점이 있어야 한다. 이차함수의 대칭점은 하나로 유일하므로 모순이다.
정답 : 10개.
