Explore BrainMass

Discrete Structures : Sequences, Subsequences and Remainders

1. How do I prove that in a group of n people there are two people with the same number of acquaintances within the group?

2. Prove that given a sequence of twelve integers, a1, a2, ...,a12, there is a subsequence aj, aj+1, ..., ak where 12 divides ∑kn= aa n.

3. A scrape of paper is found in an old desk that read: 72 turkeys $X67.9Y
The first and last digits of the price were smudged. What are the two smudged digits?

4. Show that from any five integers, not necessarily distinct, one can always choose three of these integers whose sum is divisible by 3.


Solution Preview

1. There are n people in the group. For each people, he can know at least 0 and at most the other n-1 people. We note that there are exactly n integers between 0 and n-1. If any two people have different number of acquaintances, then the n people must have 0, 1, 2, ..., n-1 acquaintances, respectively. But we know that if one person know n-1 other people, then no people can have 0 acquaintance. Every people must know at least the guy who knows other n-1 people. We get a contradiction. Therefore, we can find two people who have the same number of acquaintances.

2. We know for each integer a, a=0,+/-1,+/-2,+/-3,+/-4,+/-5,6 mod 12. In the 12 integers, if a=0 mod 12, then we find the subsequence containing only one element a. If a=k and b=-k mod 12 with 1<=k<=6, then the subsequence is a,b and we have a+b=0 mod 12. Now with repect to module 12, we ...

Solution Summary

Sequences, Subsequences and Remainders and Proofs are investigated. The solution is detailed and well presented.