Tag Info

Hot answers tagged

42

For $133$ ones there is $1$ outcome. For $131$ ones and $1$ two there are $132$ outcomes. For $129$ ones and $2$ twos there are ${131 \choose 2}$ outcome. Thus there are ${133 \choose 0}+{133-1 \choose 1}+{133-2 \choose 2}+...+{133-66 \choose 66}$ outcomes, which is, as noted by Jack D'Aurizio, the 134th Fibonacci number (You may refer to Fibonacci number ...


10

Hint: Note that the first digit in the sum is either a $1$ or a $2$, so the number of ways of getting a sum of $133$ is the number of ways of getting a sum of $132$ (add one at the beginning) plus the number of ways of getting a sum of $131$ (add two at the beginning). Let's do it with the number of ways of getting to $5$. If the first number in the sum ...


4

This is essentially an explanation of Jack D'Aurizio's answer. Let $k$ be the number of twos, then we have $n-2k$ ones. There are then $$ \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}=\sum_{k=0}^\infty\binom{n-k}{n-2k} $$ ways to write $n$ as a sum of ones and twos. One way to compute this number is to look at the generating function. $$ \begin{align} ...


4

I'll prove that this holds in general, not just for 133 Let $P_i$ be the solution to this problem for number $i$. That is, the answer to the exact question is $P_{133}$ Let $F_i$ be the $ith$ Fibonacci number. Proof by induction that $\forall i\geq1:P_i = F_{i+1}$ Base: $i=1$ Can make with only a single 1. So $P_1 = 1 = F_2$ Hypothesis: Assume holds ...


4

Hints: It suffices to show that $\sim$ is an equivalence relation on $M_2(\mathbb R)$. So simply show that it's reflexive, symmetric, and transitive. This follows immediately, since $\sim$ is defined in terms of $=$. Try some examples. Pick a matrix at random, and find its equivalence class. Then try going backwards: pick a determinant at random, then try ...


3

Hint: $$[x^{133}]\,\frac{1}{1-(x+x^2)}=F_{134}=4517090495650391871408712937.$$ More information and context can be found in the questions here and here. Just to be clear, the number we want to compute is given by the coefficient of $x^{133}$ in the sum: $$1+(x+x^2)+(x+x^2)^2+(x+x^2)^3+\ldots = \frac{1}{1-(x+x^2)}$$ and since the Taylor coefficients $a_n$ of ...


3

Yes. Just solve the equation $f(x) = f(y)$: $$2x^2 + 4x + 8 = 2y^2 + 4y + 8 \\ 2(x^2-y^2) + 4(x-y) = 0 \\ (x-y) \big( 2(x+y) + 4 \big) = 0 \\ x = y \vee x+y = -2$$ So $(x, y) \in E \iff x = y \text{ or } y = -x-2$.


2

Consider for instance how many ways to make a sum of 1? Then of 2? To make a sum of 3, you can add a 2 to all the ways to make a sum of 1, and a 1 to all the ways to make a sum of 2 (so the number of ways of making 3 is the sum of the ways of making 2 plus the number of ways of making 1). For a total of 4, you can add a 2 to the ways to make 2, and a 1 to ...


2

Whenever we have a function $f\colon X\to Y$, we can define a relation $\sim_f$ over $X$ by declaring $$ a\sim_f b\qquad\text{if and only if}\qquad f(a)=f(b) $$ This is readily seen to be an equivalence relation: for all $a\in X$, $a\sim_f a$: indeed $f(a)=f(a)$ for all $a,b\in X$, if $a\sim_f b$, then $b\sim_f a$: indeed $f(a)=f(b)$ implies $f(b)=f(a)$ ...


2

Compute $$\det\pmatrix{a&0\\0&1}$$ What do you notice? The partition property is inherent because $\det$ is a function and $x \sim_f y :\Leftrightarrow f(x) = f(y)$ is an equivalence relation for any function $f$.


2

You can partition any set $X$ as $X=\displaystyle\bigcup_{x\in X}\{x\}$.


2

Hint: if $x\in\bar{0}\cap \bar{1}$, then in particular $x\in\bar{0}$ and $x\in\bar{1}$. Now, $x\in\bar{0}$ means that $xR0$, so that $x-0=x$ is divisible by $2$ so that $x$ is even. Perform a similar computation assuming that $x\in\bar{1}$ and derive a contradiction.


2

Let some of the pieces in the first case contain zero. Then add 1 to all of them.


1

You can do this using generating functions. This is analogous to the classic coin change problem. In your case, you want to look at the term for $x^{133}$ in the expansion of $$ f(x) = \frac{1}{(1-x^1)(1-x^2)(1-x^3)}.$$ We may rewrite $f$ as $$ f(x) = \frac{1/6}{(1-x)^3} + \frac{1/4}{(1-x)^2} + \frac{17/72}{1-x} + \frac{1/8}{1+x} + \frac{-j/9}{x-j} + ...


1

The equivalence classes partition $S$ which means $$S=\cup_iE_i$$ $$i\neq j\Rightarrow E_i\cap E_j=\phi$$ So if we assume each class is made of one element we see that the number of classes cannot exceed $|S|$ Now the second claim is slightly more subtle. Take any partition of $S$ in other words any set of disjoint subsets whose union is $S$ and define ...


1

This is true. One way to think about an equivalence relation is as a partition of a set. Think about dividing a set up into disjoint subsets. The largest number of partitions is achieved when you let $x\sim x\Leftrightarrow x=x$, so the number of classes can never exceed $|S|$. You can achieve $k$ classes by having $k-1$ singleton classes, and letting the ...


1

Ok, Here is a simple answer that you can explain to an elementary school student. The answer is 67. First you make 133 by using as many twos as possible, which is 133/2 = 66. That gives you one way of making 133. Now you can look at the number of twos in your answer, and you can add another way by splitting one of those twos into ones. Since you have 66 ...


1

I'm not sure what the question is, but you're 100% correct. The way I look at it: There's a category $\mathbf{CMon}$ of commutative monoids. The underlying set functor $U:\mathbf{CMon} \rightarrow \mathbf{Set}$ has a left-adjoint $F:\mathbf{Set} \rightarrow \mathbf{CMon}$. Let $\Phi$ denote an object of $F \dashv U$, where I write $F \dashv U$ for the ...


1

For (d), OEIS A000930 delights in the name of Narayana's cows sequence. Starting with $n=0$: $1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745$


1

You can assume that $x_N\ge N/2$ and so you want to prove that $$ \frac{\sum \limits_{i = 1}^N x_i^4}{\left(\sum \limits_{i = 1}^N x_i^2\right)^2}\ge \frac{x_N^4 + (N-x_N)^4}{(x_N^2 + (N-x_N)^2)^2} $$ Set $\lambda:=N-x_N$, and assume $\lambda>0$ (else the inequality is trivially true), and set also $$ x:= \frac{x_N}{\lambda},\quad\text{and}\quad ...



Only top voted, non community-wiki answers of a minimum length are eligible