How to Get Away with Candy Hoarding

Let denote the candies each house give equal to $a$ , $a+1$ , .... , $a+8$ .

A house can be visited twice at most and the 2 houses $a+8$ and $a+1$ are only visited once each only. 4 kids will visit 9 houses for a total of 16 times. However, we observe that if the maximum number of visits to the 7 houses $a$ , $a+2$ , $a+3$ , $a+4$ , $a+5$ , $a+6$ , $a+7$ is $2*7 = 14$ , plus 2 for house $a+8$ and $a+1$ which is 16. Hence, all the houses $a$ , $a+2$ , $a+3$ , $a+4$ , $a+5$ , $a+6$ , $a+7$ are visited twice each.

Therefore, the total number of candies is $a*2 + (a+1) + (a+2)*2 + (a+3)*2 + (a+4)*2 + (a+5)*2 + (a+6)*2 + (a+7)*2 + (a+8) = 16a+63$

The number of candies that Wes have is $4a + x$ where $x$ is the sum of 4 distinct numbers picked from 0 to 8. That also means, x must be divisible by 4 since 112 is divisible by 4.

Each kid will visit 4 houses, and the difference between the numbers of candies each house give must be larger than 1. Given that the lowest number of candies the kid received is $a + t$ , then the the second least number of candies he/she also receives should be at least $a + t+2$ , the third least should be at least $a + t+4$ and the most should be at least $a + t+6$ .

Hence, a kid will receive $4a + 4t + 12 \geq 4a + 12$ candies. The maximum number of candies a kid can receive can be found to be $(a+8) + (a+6) + (a+4) + (a+2) = 4a+20$ . The number of candies that Wes can take, therefore, can only be $4a+16$ or $4a+20$ .

If Wes takes only $4a+16$ candies, then the maximum total number of candies is $4a+16 +(4a+15)*3 = 16a+61$ , which is smaller than our total number of candies $16a+63$ .

To prove that 4a + 20 is the right number of candies for Wes, we can find the houses each kid visits as below.

We have $4a+20 = 112 \Rightarrow a = 23$

$\Rightarrow 16a+63 = 431$

In isolation, there are 15 ways that a child could visit four houses without visiting two adjacent houses, or the same one twice. I expressed the paths as length-9 arrays and randomly added four of them together repeatedly in python, finding only one combination that adds up to one visit to houses 2 and 9, and two visits to each other house: $c0: [1, 0, 1, 0, 1, 0, 1, 0, 0]$ $c1: [1, 0, 0, 1, 0, 1, 0, 1, 0]$ $c2: [0, 1, 0, 1, 0, 1, 0, 1, 0]$ $c3: [0, 0, 1, 0, 1, 0, 1, 0, 1]$

You can then consider that the houses each have the lowest candy value x plus i, where i is the index of the house (0 to 8). Hence, each path has the value of 4x plus the dot product of the path vector and [0, 1, ... , 8]. The dot products are: $[12, 15, 16, 20]$ , and we know that the highest amount of candy is 112, therefore: $112 = 4x + 20$ $x = 23$ Using this, one can just add 16x to the above values, making the total 431.