Waste less time on Facebook — follow Brilliant.

Combinatorics #1

Given any \(9\) integers, show that it is possible to choose \(w,x,y,z\) such that \(w+x-y-z\equiv0\)\((\text{mod}\) \(20)\).

Note by Victor Loh
3 years, 3 months ago

No vote yet
1 vote


Sort by:

Top Newest

The condition is the same as:\(w+x\equiv y+z \pmod {20}\). Notice that if we can find \(w\equiv y, x\equiv z\), then we are done. Hence it suffices to consider the case where there's at most one residue of \(20\) such that at most \(3\) numbers are congruent to it.

In this case, we have at least \(7\) distinct residues considering each integer in mod 20 . Note that there are at least \({7\choose 2}=21\) ways to choose \(2\) of the numbers and then take their sum. Using the \(20\) mod 20 residues as pigeon holes, there exist a residue \(r\) with at least two sums i.e \(w+x\equiv y+z\equiv r \pmod {20}\)(we can't have \(w=y\) because that would imply \(x\equiv z \) which contradicts having distinct residues) and we are done.

Xuming Liang - 3 years, 3 months ago

Log in to reply

The easy bash: The 10 possible sets of end digits of the 9 integers are \[[1,2,3,4,5,6,7,8,9], [0,1,2,3,4,5,6,7,8], [2,3,4,5,6,7,8,9,0] ,[3,4,5,6,7,8,9,0,1]\] \[[4,5,6,7,8,9,0,1,2] , [5,6,7,8,9,1,2,3,4,] ,[6,7,8,9,1,2,3,4,5]\]\[[7,8,9,1,2,3,4,5,6],[8,9,1,2,3,4,5,6,7] and [9,0,1,2,3,4,5,6,7]\]It suffices to show that \(1+9-2-8=0\) and \(8+0-7-1=0\) as by Pigeonhole Principle, each of the other 8 sets is just a rearrangement of the first 2. Not very elegant but it works. Since this works for single digit numbers, it works for any other set because each number in that set is basically adding a multiple of 20 to the original 1-digit set. (Not clear, I know but basically, I'm saying that for \(10+19-12-18\), it works because it is \(1+9-2-8+10+10-10-10\), or \(1+9+2+8+0\).)

Joshua Ong - 3 years, 3 months ago

Log in to reply

one more question, given the series:1,3,5,7,9,11,13,15. now choose 5 digits from here whose sum is equal to 30.(u can take a number twice also)

Sarfraz Ahmed - 3 years, 3 months ago

Log in to reply


Joshua Ong - 3 years, 3 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...