# Prove of Greedy Algorithm

Can anyone prove the following?

given n numbers [integer and not necessary distinct] and lets denote the sum of all those number by Sum(n) then we have one of the following facts:

1- Sum(n) is Divisible By n.

2- if Sum(n) is not Divisible By n then [Sum(n) - x] is Surely Divisible By n where x is one of those given numbers.

example: given 1 , 2 , 3 there sum is 6 then 6 is divisible by 3

another example 1 , 2 , 3 , 4 there sum is 10 not divisible by 4 but if we take 10 - 2 yield 8 that's divisible by 4

anyone can help me to prove this?

• Welcome to MSE! Could you please let us know what you have tried so far? As you are new here, I just want to let you know that these "I demand my proof"-questions are highly frowned upon. – Diglett Oct 18 '18 at 1:30

This does not always hold. If we have $$1,1,3$$ the sum $$5$$ is not divisible by $$3$$, but neither are $$5-1=4$$ and $$5-3=2$$.