2 More Difficult Questions, Any Help Is Appreciated

• Apr 11th 2008, 03:38 AM
ChiragDesai01
2 More Difficult Questions, Any Help Is Appreciated
the first question is:

let a1, a2, a3, a4, a5 , be any distinct positive integers. Show that there exists at least one subset of three of these integers whose sum is divisible by 3.

the second quesiton is:

The simplex lock is a popular push-button combination lock found in aparment buildings, offices schools, etc... The metallic lock has five buttons that can be pushed individually or simultaneously with other buttons, and the order and number of pushes make up a unique code. Codes for the lock follow the protocol listed below
(i) A code has a sequence of zero or more pushes, each involving atleast on button.
(ii) Each button may be used at most once.
(iii) Each push may include any number of previously unpushed buttons.
(iv) When two or more buttons are pushed at the same time, order does not matter.
Suppose you have a five-buton simplex lock. How many possible codes exist?

plzzzzzz help on these crazy combinatorics questions

• Apr 11th 2008, 06:01 AM
Plato
7+13+21=41 & 8+14+18=40 neither sum is divisible by 3.

Suppose {a,b,c,d,e} are the five positive integers.
Assign each to its equivalence class modulo 3.
If one of the classes contains three of the numbers then that sum is divisible by three.
If no class contains more than two then no class is empty.
So for example: a=3j in [0], b=3k+1 in [1] and c=3n+2 in [2].
Well a+b+c=3(j+k+n)+3.
• Apr 11th 2008, 01:57 PM
awkward
Quote:

Originally Posted by ChiragDesai01
[snip]

The simplex lock is a popular push-button combination lock found in aparment buildings, offices schools, etc... The metallic lock has five buttons that can be pushed individually or simultaneously with other buttons, and the order and number of pushes make up a unique code. Codes for the lock follow the protocol listed below
(i) A code has a sequence of zero or more pushes, each involving atleast on button.
(ii) Each button may be used at most once.
(iii) Each push may include any number of previously unpushed buttons.
(iv) When two or more buttons are pushed at the same time, order does not matter.
Suppose you have a five-buton simplex lock. How many possible codes exist?

plzzzzzz help on these crazy combinatorics questions

More generally, let N(n) be the number of possible codes for a n-button simplex lock.

Suppose you are choosing a code. Your first set of buttons can consist of 1 to n buttons. Let's say you decide to push i buttons. You can choose the set of i buttons in $\binom{n}{i}$ ways. You can stop right there or go on to pick another set of buttons. If you decide to continue, there are N(n-i) codes left to (possibly) choose. So

$N(n) = \sum_{i=1}^n \left( \binom{n}{i} + \binom{n}{i} N(n-i) \right) = \sum_{i=1}^n \left( 1 + N(n-i) \right) \binom{n}{i}$

Combined with $N(0) = 0$, this is sufficient to compute N(5). I calculate N(n) = 1, 5, 25, 149, 1081 for n = 1, 2, 3, 4, 5. Better check the calculations, I am notoriously unable to compute anything.

jw
• Apr 21st 2008, 05:32 AM
awkward
Quote:

Originally Posted by awkward
More generally, let N(n) be the number of possible codes for a n-button simplex lock.

Suppose you are choosing a code. Your first set of buttons can consist of 1 to n buttons. Let's say you decide to push i buttons. You can choose the set of i buttons in $\binom{n}{i}$ ways. You can stop right there or go on to pick another set of buttons. If you decide to continue, there are N(n-i) codes left to (possibly) choose. So

$N(n) = \sum_{i=1}^n \left( \binom{n}{i} + \binom{n}{i} N(n-i) \right) = \sum_{i=1}^n \left( 1 + N(n-i) \right) \binom{n}{i}$

Combined with $N(0) = 0$, this is sufficient to compute N(5). I calculate N(n) = 1, 5, 25, 149, 1081 for n = 1, 2, 3, 4, 5. Better check the calculations, I am notoriously unable to compute anything.

jw

In the above I have ignored the possibility of the "empty combination", which the phrase "zero or more pushes" in the problem statement seems to indicate is a possibility. So if you think we should be including the empty combination in the count, the final answer is 1081 + 1 = 1082.

jw