Tagged Questions

51 views

Reverse Hex board game winning strategy

I just wanted to know the winning strategy to this question: In a reverse Hex board game I know it means where the player who first forms a path between his/her edges loses. Find a winning ...
49 views

Winning or Non-losing strategy for A or B

Find a winning or a non-losing strategy for the following game: Consider $25$ sticks arranged in a $5$ x $5$ square. Players alternately take any number of sticks from a single row or column. At ...
83 views

Hex game winning strategy

I was teaching myself how to play a hex board game by reading some books a couple days ago. I learned how to do $2$ x $2$ and $3$ x $3$ hex games by starting at the principal diagonal. I wanted to ...
43 views

I want to prove that $\binom{n}{n/2} \leq 2^{n-1}$ [Assuming $n$ is even] I've tried to do that but I didn't succeed.
57 views

Using Plancherel's Theorem to Prove the Gauss Sum

I'm interested in proving the following: Where $p$ is an odd prime and $z$ is a primitive $p$th root of unity, we let $Q(p)=\sum^{p−1}_{k=0}z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$. Specifically, I want ...
61 views

66 views

combinatorics proof with i - Peter J. Cameron book

I'm working through Peter J. Cameron's combinatorics book and I'm having trouble understanding one of his proofs. In proposition 3.3.3, he states: "If n is a multiple of $8$, then the number of sets ...
67 views

Finishing proof of identity $\sum_{k=b}^{n} \binom{n}{k} \binom{k}{b} = 2^{n-b} \binom{n}{b}$

The identity $$\sum_{k=b}^{n} \binom{n}{k} \binom{k}{b} = 2^{n-b} \binom{n}{b}\$$ is one of a few combinatorial identities I having been trying to prove, and it has taken me way too long. I am ...
60 views

Find the number of subsets $S$ of $X$ (of any size) that satisfy the following property

Let $X=\{1,2,\dots,10\}$ define the relation $R$ on $X$ by: for all $a,b\in X$, $a\mathrel{R}b \iff ab$ is even. 1) Find the number of subsets $S$ of $X$ (of any size) that satisfy the ...
45 views

how many elements does Ia have?

Let $A=\{1,2,3,4\}$. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by $f,g \in F$ $f R g \Leftrightarrow |f(A)|=|g(A)|$ $f(A)=\{f(x): x\in A\}$ ...
76 views

Let S = {1,2…10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S),

Let S = {1,2....10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S), XRY <=> X∩Y=∅ is it true that ∀X∈P(S),∃Y∈P(S) so that (X,Y)∈R? I dont know what is (X,Y)? ...
129 views

How to prove that if n and k are integers with 1 ≤ k ≤ n, then k*(n C k)=n(n−1 C k−1) combinatorally?

I am having with combinatorial proofs. My professor says to come up with a scenario so that we can connect both sides by double counting but I am clueless.
58 views

Convergence of formal power series substitution

Prove that the substitution of formal power series $F(G(x))=\sum_{k\geq0}f_k \frac{G(x)^k}{n!}$ converges for every $F$ if and only if $G(0)=0$
340 views

Formal power series, the Chain Rule and the Product Rule.

Definitons Let $$\mathbb{C}[[x]] := \left\{ \sum_{n\geq 0} a_n x^n : a_n \in \mathbb{C} \right\}$$ be the set of formal power series of $x$. Exercise i) If $F_1(x)$ and $F_2(x)$ are power series ...
203 views

For all positive integers n,m,k where $n\ge m\ge k$ , $\binom {n}{m}\binom {m}{k}=\binom {n}{k}\binom {n-k}{n-m}$ [duplicate]

For all positive integers n,m,k where $n\ge m\ge k$ , $\binom {n}{m}\binom {m}{k}=\binom {n}{k}\binom {n-k}{n-m}$ Prove the following statements using combinatorial proofs. I can't come up ...
127 views

Stirling numbers of second type [duplicate]

How can I do a combinatoric proof that for Stirling number of second type the equality if true: $${n\brace k} = \frac{1}{k!}\sum_{i=0}^{k}{k \choose i}i^n(-1)^{k-i}$$
578 views

How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do ...
61 views

Pigeonhole question and generalization

Let H be a regular hexagon with side length 1 unit. (a) Show that if more than 6 points are speci ed inside H then the points of at least one pair of them are at most 1 unit apart. (b) State and ...
Show that any subset of $\{1, 2, 3, ..., 200\}$ having more than $100$ members must contain at least one pair of integers which add to $201$. I think it is doable using the Pigeonhole Principle.
Proving there are at least $N$ surjective functions from $A$ to $B$
Let $A = \{1,2,\ldots,m\}$; $B = \{1,2,\ldots,n\}$. I have to prove that there are at least $\frac{m!}{(m-n+1)!}$ surjective functions from $A$ to $B$. I've given it some thought, but I don't know ...