There are 47 students in a classroom with seats arranged in 6 rows $ \times$ 8 columns, and the seat in the $ i$-th row and $ j$-th column is denoted by $ (i,j).$ Now, an adjustment is made for students’ seats in the new school term. For a student with the original seat $ (i,j),$ if his/her new seat is $ (m,n),$ we say that the student is moved by $ [a, b] = [i - m, j - n]$ and define the position value of the student as $ a+b.$ Let $ S$ denote the sum of the position values of all the students. Determine the difference between the greatest and smallest possible values of $ S.$
Problem
Source: CGMO 2003, Problem 2
Tags: combinatorics unsolved, combinatorics
feliz
29.12.2008 22:42
Isn't it $ |a| + |b|$?
Andy Loo
24.10.2010 16:15
feliz wrote: Isn't it $ |a| + |b|$? No! It's $a+b$.
chaotic_iak
24.10.2010 17:46
Andy Loo wrote: feliz wrote: Isn't it $ |a| + |b|$? No! It's $a+b$. So a student moved from $(1,5)$ to $(5,1)$ has the position value of $0$?
vsathiam
06.12.2016 18:12
Idk if this can constitute as a proof, but the problem's summation of position values is essentially equivalent to the the difference between initial total state value and final total state value. (Here I am defining state value as the sum of the coordinates of a space.) Our maximum total position value is acquired for any configuration with an initial empty space at (1,1) and final empty space at (6,8). This gives a value of 12. The minimum occurs when the above two states are flipped, and gives -12. So the difference is 24. *2 things: can someone please tell me if the above solution is legit? Here's an example to help illustrate my solution: Define position value similarly for initial sequences (1,2,3...n) and $(p_1,p_2,p_3...p_n)$ where second set is a permutation of the former one. Sum of both sequences are fixed, the total position value should always be 0.
rafayaashary1
06.12.2016 18:35
vsathiam wrote: Idk if this can constitute as a proof, but the problem's summation of position values is essentially equivalent to the the difference between initial total state value and final total state value. (Here I am defining state value as the sum of the coordinates of a space.) Our maximum total position value is acquired for any configuration with an initial empty space at (1,1) and final empty space at (6,8). This gives a value of 12. The minimum occurs when the above two states are flipped, and gives -12. So the difference is 24. *2 things: can someone please tell me if the above solution is legit? Here's an example to help illustrate my solution: Define position value similarly for initial sequences (1,2,3...n) and $(p_1,p_2,p_3...p_n)$ where second set is a permutation of the former one. Sum of both sequences are fixed, the total position value should always be 0. Specifically $S=\sum_{\text{filled old}}i+\sum_{\text{filled old}}j-\sum_{\text{filled new}}i-\sum_{\text{filled new}}j=i_{\text{empty new}}+j_{\text{empty new}}-i_{\text{empty old}}-j_{\text{empty old}}$ Then the max is clearly $14-2$, and the min is $2-14$ giving $\boxed{24}$