Derek's permutations

By symmetry, the number of permutations such that the problem is satisfied is the same as the number of permutations such that the inequality is reversed, or such that $\tau(1)+\tau(9)+\tau(25)<\tau(4)+\tau(16)+\tau(36)$ To find our answer, we must find the number of ways that either the above inequality or the one in the problem is satisfied, and we can then divide by 2.

There are exactly three possibilities for the inequality sign. It could be $>$ , $<$ , or $=$ . Since the total number of permutations is $7!=5040$ , we can find the number of ways $=$ can be achieved, and subtract from 5040, and divide.

We must find the number of ways that the sum three distinct elements in $\tau$ is also the sum of three other distinct elements in $\tau$ . The sum of the elements in $\tau$ is 140. Therefore, if two sums are equal, the number left out must be even. We can leave out 4, 16, or 36.

4 left out:

In this case, the sum of each set of three is 68. 1 must be paired with two numbers that add to 67. It is easy to see there is no such pair.

16 left out:

In this case, each sum must be 62. 1 must pair with numbers that add to 61. We find that only 25+36=61, and so one pair of triplets is $((1,25,36),(4,9,49))$

36 is left out:

In this case, each set sums to 52. The set with 1 must have a total of 3 from two other elements. This is not possible.

Therefore, LHS=RHS in exactly one case. However, we can first choose which of the two sets is on the LHS, and then we can permute the elements on both sides. This is a factor of $2\cdot 3!\cdot 3!=72$ Using our logic from above, we find that $N=\dfrac{5040-72}{2}=2484$ The answer is $\boxed{484}$ .

Sidenote: The cases might appear long, but they are quite simple.

By symmetry, $N$ will be equal to the number of permutations for the case where the inequality is flipped. So $N$ must equal the total number of permutations minus the permutations for which the left- and right-hand sides are equal, divided by two. The two sides are equal only if the triplets are $(1,25,36)$ and $(4,9,49)$ , since $1 + 25 + 36 = 4 + 9 + 49$ .

There are $3! = 6$ ways to order each triplet, and since we are counting cases when the two sides are equal, we can assign either the left- or right-hand side either triplet.Thus there are $6\times 6\times 2 = 72$ cases where they are equal. There are $7! = 5040$ permutations in total.

Hence, $N = \dfrac{5040 - 72}{2} = \boxed{2484}$ .

We would first count the number of cases where $\tau(1)+\tau(9)+\tau(25) = \tau(4)+\tau(16)+\tau(36)$ . Thus $\tau(1)+\tau(4)...+\tau(36)$ must be even. Note that $\tau(1)+\tau(4)+...+\tau(49)=140$ , so $\tau(49)$ must be even, so it is either $4$ , $16$ , or $36$ .

Case $1$ : $\tau(49)=4$ .

$\tau(1)+\tau(4)...+\tau(36)=140-4=136$ , so $\tau(1)+\tau(9)+\tau(25) = \tau(4)+\tau(16)+\tau(36) = \frac{136}{2} = 68$ . We consider the one containing the $49$ . The sum of the other $2$ in that group will be $68-49=19$ . However, there are no two perfect squares that have a sum of $19$ , because $19-16=3$ , $19-9=10$ , $19-4=15$ , and $19-1=18$ are not perfect squares.

Case $2$ : $\tau(49)=16$ .

$\tau(1)+\tau(4)...+\tau(36)=140-16=124$ , so $\tau(1)+\tau(9)+\tau(25) = \tau(4)+\tau(16)+\tau(36) = \frac{124}{2} = 62$ . We consider the one containing the $49$ . The sum of the other $2$ in that group will be $62-49=13$ . The only two perfect squares that sum up to $13$ is $9$ and $4$ . It is easy to check that $13-1=12$ is not a perfect square. Hence we have a pairing of ${49, 9, 4}$ and ${36, 16, 1}$ . There are 2 ways to choose which unordered triplet goes to ${\tau{1}, \tau{9}, \tau{25}}$ or ${\tau{4}, \tau{16}, \tau{36}}$ , and $6$ ways to rearrange within each, so there are $(2)(6)(6)=72$ permutations in all.

Case $3$ : $\tau(49)=36$ . $\tau(1)+\tau(4)...+\tau(36)=140-36=104$ , so $\tau(1)+\tau(9)+\tau(25) = \tau(4)+\tau(16)+\tau(36) = \frac{104}{2} = 52$ . We consider the one containing the $49$ . The sum of the other $2$ in that group will be $52-49=3$ . However, the smallest possible value of two distinct perfect squares is $1+4=5$ , so this case is not possible.

Hence there are only $72$ combinations such that $\tau(1)+\tau(9)+\tau(25) = \tau(4)+\tau(16)+\tau(36)$ . Note that there are $7!=5040$ permutations in all, so there are $5040-72=4968$ permutations where $\tau(1)+\tau(9)+\tau(25) \neq \tau(4)+\tau(16)+\tau(36)$ . Note that exactly half of those satisfy $\tau(1)+\tau(9)+\tau(25) > \tau(4)+\tau(16)+\tau(36)$ because we could just reverse the numbers then the symbol will be reversed.

Hence $N=\frac{4968}{2}=2484$ . Its last $3$ digits are $\boxed{484}$ .

Symmetry is the essence of combinatorics

Let $S_1 = \tau(1) + \tau(9) + \tau(25)$ & $S_2 = \tau(4) + \tau(16) + \tau(36)$ . Given any value of $\tau(49)$ , all permutations $\tau$ can be classified in 3 parts: (i) when $S_1 > S_2$ ; (ii) when $S_1 = S_2$ & (iii) when $S_1 < S_2$ .

Observe that cases (i) & (iii) are symmetric & equally present in permutations $\tau$ , as they are basically same(oppositely). In fact, say for a particular permutation $S_1 > S_2$ , then you can switch values of $\tau(4)$ , $\tau(16)$ & $\tau(36)$ with $\tau(1)$ , $\tau(9)$ & $\tau(25)$ to obtain $S_1 < S_2$ (and for each such permutation you can do so).

So, cases (i) & (iii) occur in equal numbers.Now let's find when $S_1 = S_2$ .

Observe that sum of all terms $\tau(1) + \tau(4) + ... + \tau(49) = 1+4+9+...+49 = 140$ , then, so that $S_1 = S_2 = \frac{140 - \tau(49)}{2}$ , $\tau(49)$ must be even (4,16 or 36).

On checking, for $\tau(49) = 16$ , we have $9+4+49 = 1+25+36$ . Both sides $S_1$ & $S_2$ can be switched in 2 ways, & each triplet can permute in $3!$ ways. So number of such permutations is $2\cdot 3! \cdot 3!$ .

So we subtract it from total permutations & divide by 2 to get the particular case when $S_1>S_2$ , which is $\frac{7! - 2\cdot 3! \cdot 3!}{2} = 2484$ .

Define $P_>$ , $P_\leq$ , $P_<$ and $P_=$ as the number of permutations $\tau$ such that, respectively:

$\tau(1)+\tau(9)+\tau(25) > \tau(4)+\tau(16)+\tau(36)$ $(1)$ $\tau(1)+\tau(9)+\tau(25) \leq \tau(4)+\tau(16)+\tau(36)$ $\tau(1)+\tau(9)+\tau(25) < \tau(4)+\tau(16)+\tau(36)$ $\tau(1)+\tau(9)+\tau(25) = \tau(4)+\tau(16)+\tau(36)$

Since $\tau$ can map each number into any other anyway, it doesn't matter in which order we write 1, 4, 9, 16 and 25 in the expression above: they will allways lead to the same respective results. Therefore, by convenientely repositioning the numbers in $(1)$ , we may conclude that $S_> = S_<$ .

Naturally, $P_> + P_\leq = 7!$ , which is the total number of permutations, and $S_\leq = S_< + S_=$ . By manipulating the equations, we get:

$P_> = \frac{7! - P_=}{2}$

Now we are only left to find $P_=$ . By directly testing the possibilities, we find that the only ways to attain the equality are the following:

$(\tau(1), \tau(9), \tau(25)) = (1, 25, 36)$ $(\tau(4), \tau(16), \tau(36)) = (4, 9, 49)$

or:

$(\tau(1), \tau(9), \tau(25)) = (4, 9, 49)$ $(\tau(4), \tau(16), \tau(36)) = (1, 25, 36)$ ,

where the triples $(1, 25, 36)$ and $(4, 9, 49)$ may assume any order. Because there are $3!$ ways to order each triple, we get that $P_= = 3!3! + 3!3! = 72$ and therefore $P_> = \frac{7!-72}{2} = 2484$ .

The answer is thus $484$ .

I found it easiest to think of the problem in terms of writing down a permutation of the numbers on a piece of paper and finding the number of permutations with the given property. The key is to note that "half" the time, the sum of the numbers in positions 1,3,5 is bigger than the sum of the numbers in positions 2,4,6.

Consider first the number that can go in the last pace (i.e. the image of 49) or $\tau(49)$ . It can be any of 1,4,9,16,25,36 or 49. Lets say $\tau(49) =36$

Once we have done this, we then have 6 numbers to distribute in the rest of the places, which we can do in $6!$ ways. In half the cases, we will have the permutations satisfying the required property, and we get $\frac{6!}{2}=360$ permutations that satisfy the condition.

All that we now need to check if there are any permutations in which the sums of the numbers are the same. This actually occurs when $\tau(49)=16$ and $\tau(1), \tau(9),\tau(25)$ is some permutation of $36,25,1$ or $4,9,49$ .

There are $3! \times 3! \times 2=72$ such permutations.

So the total number of such permutations is $\frac{6!}{2}\times 6 + \frac{6!-72}{2}=2484$