Pigeon Hole Principle problem

67 Views Asked by At

Say that you a set A that is broken up into subsets $A_1,A_2,...,A_n$, where each subset has size x.

1) Prove that if $n<3^{x-1}$, then x is greater than 1.

2) Prove that if $n<\frac{3^{x-1}}{2^x}$, then $x\geq 3$

I am quite stumped on how to solve this but I was thinking of using the pigeonhole principle

1

There are 1 best solutions below

0
On BEST ANSWER

Hint 1: If $x \leq 1$, what does that say about $x-1$? What does that say about $3^{x-1}$?

Hint 2: If $x \leq 2$, then what? We can assume $x \geq 0$ since "each subset has size $x$". There are three possibilities, $x=0,1,2$. What is $3^{x-1}/2^x$ for each possibility? Does it leave any possible value for $n$?