The positive integers 1 through 49 are divided into k disjoint subsets so that no two integers whose sum is divisible by 10 are in the same subset. For example, 13 and 37 cannot be in the same subset. What is the smallest possible value of k?
Ok, so I know I can just list them out like (1, 49), (2, 48), etc. and then find all total values 49 choose 2 and then minus the subsets that have a sum that is divisible by 10, but in real mathematical competitions that will take to long. Pls give a intellectual way of solving without endeavoring listing all although as long as strategy works, pls show me :)
