Coursera FB problem
Find 11 positive integers such that none of them add up to a multiple of 11, or prove that this cannot be done.
The above problem was posted on the FB page of the Coursera Introduction to mathematical thinking mooc.
To begin with I misunderstood the problem, however reading posts by other members of the group it became clear what the problem was and of how to proceed. This provided a very interesting experience of being in a virtual classroom.
I began the problem after my Japanese class on Tuesday night reading it on my iPhone in my car — please note that the car was stationary:) The final insight was provided by a fellow classmates posting several hours later as I got out of bed.
I am adding my attempt at understanding this problem below for the sake of interest. As discussed on the group I am looking at a smaller number to begin with ie showing the case for 3 positive integers:
- a, b, and c are +ve ints
- none of a, b, or c are divisible by 3
- hence a, b, and c leave remainder 1 or 2 when divided by 3
- we want to form the sums a+b, a+c, b+c, and a+b+c and to see what the remainder is when divided by 3
- it suffices to add the remainders of a, b, and c
- eg consider 4 and 8
- 4 leaves remainder 1 when divided by 3
- 8 leaves remainder 2 when divided by 3
- 4 + 8 = 12 leaves remainder 0 when divided by 12
- however the remainders of 4 and 8 when we add them gives 1 + 2 = 3 but note that in terms of dividing by 3 a remainder of 3 is the same as a remainder of 0
- in mathematical notation we say 1+ 2 = 3 ≡ 0 (mod3)
- similarly consider 4 and 7, both leave remainder 1 when divided by 3
- 4 + 7 = 11 which leaves a remainder of 2 when divided by 3
- note that the remainders of 4 and 7 are both 1 and that when we add these we get 2
|
a |
b |
c |
a+b |
a+c |
b+c |
a+b+c |
|
|
Remainder |
1 |
1 |
1 |
2 |
2 |
2 |
3 ≡ 0 (mod3) |
|
Remainder |
1 |
1 |
2 |
2 |
2 |
3 |
4 ≡ 1 (mod3) |
|
Remainder |
1 |
2 |
2 |
3 |
3 |
4 |
5 ≡ 2 (mod3) |
|
Remainder |
1 |
2 |
1 |
3 |
2 |
3 |
4 |
|
Remainder |
2 |
2 |
2 |
4 |
4 |
4 |
6 ≡ 0 (mod3) |
|
Remainder |
2 |
2 |
1 |
4 |
3 |
3 |
5 |
|
Remainder |
2 |
1 |
1 |
3 |
3 |
2 |
4 |
|
Remainder |
2 |
1 |
2 |
3 |
4 |
3 |
5 |
- notice that in each row there always occurs at least one cell in which there is a 3 or a 6 (≡ 0 (mod3) ie divisible by 3).
- with the necessary changes being made it would be possible to show that for any set containing n positive integers there must be at least one way of combining the numbers in the set to form a sum which is divisible by n.