Perms and Combs help (again 😭) (1 Viewer)

[potatoe456]

pls help with the following qs (idk where to even start)


1. How many selections of at least one object can be made from n distinct objects?


2. Recall that a digit sum of a number n is the value obtained when the digits of n
are added together. For example, the digit sum of 152 is1+5+2=8.

(a) How many four-digit numbers must be selected to guarantee that at least two of them have
the same digit sum?

(b) 110 randomly -chosen three-digit numbers are selected. Show that at least five of them have
the same digit sum.

 

[liamkk112]

pls help with the following qs (idk where to even start)


1. How many selections of at least one object can be made from n distinct objects?


2. Recall that a digit sum of a number n is the value obtained when the digits of n
are added together. For example, the digit sum of 152 is1+5+2=8.

(a) How many four-digit numbers must be selected to guarantee that at least two of them have
the same digit sum?

(b) 110 randomly -chosen three-digit numbers are selected. Show that at least five of them have
the same digit sum.

for one, we can pick either one object, or two objects, or … n objects. using choose, we get nC1 + nC2 + … + nCn ways (assuming no repetition).

for 2)a), we need to use pigeonhole principle. firstly let’s consider all the different digit sums we can get. the first digit can’t be 0 so 1 is the lowest digit we can pick there (otherwise it wouldn’t be a 4 digit number) but the rest can be 0, so we get 1 to be our lowest digit sum. alternatively we can get 9999 which has a digit sum of 36. so in total, there are 36 possible digit sums. hence, we need to pick 37 4 digit numbers to guarantee that two have the same digit sum.

for b) again we use pigeonhole principle; by similar logic to before there are 27 possible digit sums for 3 digit numbers. now 110/27 = 4.07… > 4, so by pigeonhole principle we can guarantee that at least 5 of the numbers randomly chosen have the same digit sum