수학의재미 AMC 8 문제 모듈러 나머지 계산

다음 그림과 같이 8개의 열의 직사각형 보드의 각 정사각형 칸에는 위쪽 왼쪽

모서리에서 시작하여 오른쪽으로 이어지는 숫자가 매겨져 있다.
첫 번째 행은 1 부터 8 까지 숫자가 있고, 두 번째 행은 9 부터 16 까지 숫자가 있고
 그림과같이 이어진다.
한 학생이 1번 정사각형을 색칠하고 하나의 정사각형을 남기고, 3번 정사각형을
색칠하고 두개의 정사각형을 남기고, 6번 정사각형을 색칠하고 세개의 정사각형을
남기는 식으로 각 열에 적어도 한 개의 색칠된 정사각형이 있을때까지 진행한다.
이렇게 처음으로 결과가 나왔을때의 색칠된 정사각형은 몇번 인가?

(풀이)
(1)

첫번째 열의 숫자들은 모두 8로 나누었을때 나머지가 1이고
두번째 열의 숫자들은 모두 8로 나누었을때 나머지가 2
이런 식으로 계속된다.
0 부터 7 까지의 나머지가 적어도 한 번씩 나오도록 숫자 정사각형을
찾아야 한다.
색칠된 정사각형의 숫자는 1 , 3 , 6 ,10 , 15,  21 , 28 , 36 , 45,  55 , 66 ,
 78 ,91  ,105 ,120 이고, 8로 나누었을때의 나머지는
1, 3, 6, 2, 7 ,5 4, 4, 5, 7, 2, 6, 3, 1, 0 이다.
따라서 마지막 열에서 첫번째 색칠된 정사각형이 얻어지는 것은
120번이 색칠될 때이다.
답은 E(120) 이다

(2)
색칠된 수는 n(n+1)/2 로 나타낼수있는 삼각수(triangular number) 이다.
삼각수는 문제에서 주어진것 처럼 1부터 시작하여 1,2,3,4 ...를 더하여 구할수 있다.

8로 나누었을때 나머지가 같은( mod 8 ) 정사각형의 수는 같은 열에 속하게 된다.

(3)

삼각수를 나열해 보면 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120 등이다.

이 삼각수를 8로 나누면 나머지가 0 부터 7 까지 모두 나온다.
8로 나누었을때의 나머지는
1, 3, 6, 2, 7 ,5 4, 4, 5, 7, 2, 6, 3, 1, 0 이다.
120 이 되면 0 부터 7 까지 모두 나오게 된다
120 ㅌ 0( mod 8 ) 이다.
120 을 8로 나누면 나머지가 0 으로 나누어 떨어진다.
8의 배수가 되어 마지막열에 처음으로 색칠이 된다.
답은 E(120) 이다

(4)
그림의 칸에 규칙에 따라 색칠을 하면 120이 되면 모든열에 한번이상 색칠이 되어
 120이 답이다.



A rectangular board of 8 columns has squared numbered beginning in the upper left corner and moving left to right so row one is numbered 1 through 8, row two is 9 through 16, and so on. A student shades square 1, then skips one square and shades square 3, skips two squares and shades square 6, skips 3 squares and shades square 10, and continues in this way until there is at least one shaded square in each column. What is the number of the shaded square that first achieves this result?

Solution

Solution 1

The numbers that are shaded are the triangular numbers, which are numbers in the form  for positive integers. They can also be generated by starting with , and adding  as in the description of the problem.

Squares that have the same remainder after being divided by  will be in the same column. Thus, we want to find when the last remainder, from  to , is found.

So, instead of adding , we can effectively either add  or subtract  if we are only concerned about remainders when divided by . We will pick the number that keeps the terms on the list between  and . We get:

Finally, a term with  is found, and checking, all numbers  through  are also on the right side of the list. This means the last term in our sequence is the first time that column  is shaded. There are  terms in the sequence, leading to an answer of , which is choice .

Solution 2

Note that the triangular numbers up to  are . When you divide each of those numbers by , all remainders must be present. We first search for number(s) that are evenly divisible by ; if two such numbers exist, we search for numbers that leave a remainder of , etc.

Quickly scanning the list, only  and  are even. That smaller list doesn't have any multiples of  until it hits . So  must be the answer.

Solution 3

The numbers shaded are triangular numbers of the form . For this number to be divisible by , the numerator must be divisible by . Since only one of  and  can be even, only one of them can have factors of . Therefore, the first time the whole expression is divisible by  is when either  or when . This gives  as the first time  is divisible by , which gives . No other triangular number lower than that is divisible by , and thus the  column on the checkerboard won't be filled until then. That gives  as the right answer.

이해 되지 않는부분 있으면 연락바랍니다.
010-3549-5206