Skip to main content

New answers tagged

6 votes

What is the minimum number of avoids for Dota 2 never ever have a match?

This can be translated into a graph theory problem belonging to the general heading of extremal graph theory. Namely, consider the graph $G$ on $N$ vertices given by the players where there is an edge ...
Qiaochu Yuan's user avatar
1 vote

Is this correct solution to arranging consecutive flowers?

Between two red flowers, there are three spaces (including ends) where clumps of white flowers can be inserted, $\square R \square R \square$ as $\;\;8,\;\; 7-1,\;\; 6-2,\;\;or\;\; 6-1-1$ Favorable ...
true blue anil's user avatar
0 votes

Counting problem involving sums

Alternative approach: Consider the following table: \begin{array}{| r | r | r | r |} \hline \text{Range of} ~d & \text{Range of} ~a & \text{Range of} ~(a-d) & \text{...
user2661923's user avatar
  • 36.9k
2 votes
Accepted

On $(0,1)$-strings and counting

If the total number of $1$ digits is $2^k,$ then we can group the ones digits as $1+1+2+4+\dots+2^{k-1}$ in $k+1$ places, with one zero after, and $n-2^k-1$ zeros out after $1,1,2,\dots,2^{k-1}.$ This ...
Thomas Andrews's user avatar
2 votes
Accepted

Is this correct solution to arranging consecutive flowers?

I would count arrangements with at least six consecutive white flowers by conditioning on the longest white block: Case 1: Longest White block is $8$ (denoted $W^8$). There are three ways this could ...
paw88789's user avatar
  • 40.9k
1 vote
Accepted

Counting problem involving sums

With the edits, your attempt is nearly correct. As you noted the correct answer is half of yours. The reason why your answer is off by half is because you have double counted scenarios. You counted ...
JMoravitz's user avatar
  • 80.1k
1 vote

Vanishing of Stirling number of second kind $S(n,k)$ for $k>n$

Substituting $j= k-i$ we have $$ S(n, k) = \frac {1}{k!} \sum_{j=0}^{k}(-1)^{k-j}{\binom k j}j^{n} $$ and that is (apart from the factor $1/k!$) the value of the $k$-th iterated forward difference of ...
Martin R's user avatar
  • 116k
2 votes

Combinatorial Proof of the $\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n + 1) 2^{n - 2}$

You have a set of $n$ people and want to pick a nonempty subset of this set and then pick a leader and treasurer from this group (the leader and the treasurer could be the same person). In how many ...
stochastic's user avatar
  • 2,578
3 votes

A deceiving simple question of combinations about ways of selecting 5 questions with atleast 1 question from each sections

Overcounting by your method has been nicely explained by angryavian To get the correct count, you could use the format [Select sectionwise numbers] x [Permute sections] $= \left[\binom52\binom52\...
true blue anil's user avatar
4 votes

A deceiving simple question of combinations about ways of selecting 5 questions with atleast 1 question from each sections

@angryavian explained it well, but I am putting similar question link here to expand our understanding. When we come to how to solve this question, the answer is Inclusion-exclusion principle such ...
Not a Salmon Fish's user avatar
4 votes
Accepted

A deceiving simple question of combinations about ways of selecting 5 questions with atleast 1 question from each sections

Your way of counting is correct if you are required to mark one of your selected questions from each section with a star. But this overcounts because we don't care which question is your "starred&...
angryavian's user avatar
  • 90.9k
0 votes

Fairest way to share gifts between kids

I happened to be faced with an analogous problem in actuality, with the following differences The people were grown-ups with some background in Operations Research We first had to agree upon some ...
true blue anil's user avatar
0 votes

Changing positions about 10 people around a circular table

The solution is $$10! - 10\left[\binom{10}{1} 8! - \binom{10}{2}7! + \binom{10}{3}6! - \binom{10}{4} 5! + \cdots + \binom{10}{9} 0! - 1\right] = 10!\left(1+ \sum _{k=1} ^{9} (-1)^k \frac{1}{k! (10-k)}...
Eli Yablon's user avatar
2 votes

7 students in 4 desks

It is correct. As an alternative approach, select the empty seat from the $4$ right-side possibilities and then seat the seven students in the remaining seats in one of the $7!$ orders, giving $4 \...
Henry's user avatar
  • 159k
2 votes

Minimum number of dominoes needed in order to force a tiling of a 2n by 2n board

Here's a solution which reduces the casework for the $6 \times 6$ board, but I don't think it will scale to larger boards. We say that a board with some given dominoes on it is tileable if we can ...
Bob Krueger's user avatar
  • 6,286
1 vote

Euler's polyhedron formula modulo 2

The question was already answered here: https://mathoverflow.net/questions/310335/closed-orientable-surfaces-have-even-euler-characteristic Although the answer deals with simplicial complexes (so all ...
3 votes
Accepted

Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.

Given a binary tree $T$ with $n$ vertices, let $v$ be any vertex of $T$ with these two properties: The subtree rooted at $v$ has more than $n/3$ leaves. Out of all vertices satisfying the first ...
Mike Earnest's user avatar
  • 77.6k
3 votes
Accepted

Unique reconstruction of rubik's cube state from images

No there won't be a uniwue solution everytime. Take counter case $$\begin{matrix} & \begin{bmatrix} Y & W & Y \\ Y & Y & Y \\ Y & W & Y \end{bmatrix} & & \\ \begin{...
EnEm's user avatar
  • 1,017
2 votes

How many six-digit numbers are there where the third digit is equal to the second last digit, ...

If, as indicated in the edit, $0$ is not a natural number, that means the product of digits can't be zero and there are only $9$ possibilities for each digit. Consequently every $10$ in your ...
Especially Lime's user avatar
1 vote
Accepted

Counterexample for a proof

Here's the example. Let all the points colored red except one layer (the upper layer). And if this layer looks like this, we'll be unable to only color a point. r r r r
Charles Green's user avatar
0 votes
Accepted

Find all pairs of natural numbers $m$ and $n$ that satisfy the following conditions:

If $m^2$ and $n^2$ have the same last digit, then their difference is divisible by 10. $$\exists k\in\mathbb{Z}: m^2 - n^2 = 10k$$ Factoring the difference of two squares gives: $$(m - n)(m + n) = 10k$...
Dan's user avatar
  • 15.7k
0 votes

A magic trick - find out the fifth card if four is given

Here's a different solution that does not use suits or cyclic differences. Label the cards as 0 through 51, inclusive. Given any five cards, sort them as $y < z < a < b < c$. If $z \leq 24$...
xdavidliu's user avatar
  • 646
0 votes
Accepted

How many six-digit numbers are there where the third digit is equal to the second last digit, ...

EDIT: Especially Lime correctly pointed out in their answer that my math didn't properly account for all the $abcbcf=0$ cases, so here is a fixed version. We are looking for numbers of the form $...
DotCounter's user avatar
  • 1,180
4 votes

Find all pairs of natural numbers $m$ and $n$ that satisfy the following conditions:

WLOG let $m=n+16$, then modulo $10$ we have that $m^2=n^2+32n+16^2$ so that $2n+6=0$ modulo $10$. Hence $n$ has either $2$ or $7$ as a last digit since only those two solve the congruence. Check that ...
person's user avatar
  • 1,458
0 votes

high school math: summands

Let $S$ be the set of positive integers whose decimal digits are all $0$ or $1$. Let $f(n)$ denote the number of ways to write $n$ as a sum of elements of $S$, where order does not matter. Let $f(n, m)...
Mike Earnest's user avatar
  • 77.6k
0 votes

high school math: summands

Maybe you could think of the number $1287$ as adding $1$ to itself that many times. $1+1+1+1+…=1287$ Then you can figure out how many different ways the $1$s can be grouped (added) together to make ...
VV_721's user avatar
  • 302
1 vote

Euler's polyhedron formula modulo 2

Here is a high-brow proof. This is equivalent to showing that the Euler characteristic of any compact orientable connected surface $S$ is even. The Euler characteristic is $$\chi(S)=\dim_{\mathbb Q}H^...
Kenta S's user avatar
  • 16.7k
2 votes
Accepted

Ramsey's Theorem and Weihrauch reducibility

You might want to take a look at [1], it contains a large number of results on the many versions of Ramsey's theorem. In particular, by Corollary 4.21, for every $m\ge 1$ and every $k$, $\mathsf{RT}^...
Manlio's user avatar
  • 3,288
1 vote

Euler's polyhedron formula modulo 2

Consider the Simplest Polyhedron : Pyramid with triangular sides. $V=4,E=6,F=4$ , where $V-E+F=2\equiv 0 \mod 2$ We can make a larger Polyhedron by gluing together 2 Polyhedra along a face. $V_1-E_1+...
Prem's user avatar
  • 11.4k
2 votes

Number of binary trees of given size, except some nodes are unary

I will add a generating function method (using the symbolic method). Let $G(z,u)$ be the generating function for this class, where $z$ enumerates the number of internal nodes and $u$ the number of ...
ploosu2's user avatar
  • 9,588
5 votes

Partition of a complete directed graph into hamiltonian cycles

For odd $n$, we always get a decomposition of the edges of $K_n$ into disjoint Hamilton cycles. This has a very nice "visual" proof: simply "rotate" the cycle drawn below around ...
Florian Lehner's user avatar
5 votes
Accepted

Number of binary trees of given size, except some nodes are unary

Let $T(n,k)$ be the set of trees of size $n$ such that $n-k$ internal nodes have exactly two children while $k$ internal nodes have exactly one children. Let $T(n)$ be the set of binary trees of size $...
Marc-André Brochu's user avatar
0 votes

How Many Lists Can Be Created by Moving One Element to Another Position?

Alternative approach: Use induction. For $~n = 2,~$ the number of satifying permutations is clearly $~1 = (2-1)^2.$ Assume that there are $~(n^2)~$ satisfying permutations, for the elements in $~\{1,2,...
user2661923's user avatar
  • 36.9k
4 votes

How Many Lists Can Be Created by Moving One Element to Another Position?

Choose an element to move ($n$ choices). Choose a new position for that element ($n-1$ choices, since you can't put it back in its original position). HOWEVER, Each choice where an element moves only ...
paw88789's user avatar
  • 40.9k
0 votes

Tennis match - combinatorics

There are $13\cdot12\cdot11\cdot10$ ways to build the string $s_1s_2s_3s_4$ using characters from $\{A,B,...,M\}$ w\o repetition.
greycatbird's user avatar
1 vote
Accepted

For integers $a, b, c,$ and $d$ where $a > b > c > d$ and $(1 - a)(1 - b)(1 - c)(1 - d) = 10.$

The factors of $10$ are $1,2,5$. Furthermore, a product is positive only when an even number of its factors are negative. Finally, there are four factors in our expression but there are only three ...
H. sapiens rex's user avatar
2 votes

For integers $a, b, c,$ and $d$ where $a > b > c > d$ and $(1 - a)(1 - b)(1 - c)(1 - d) = 10.$

Note $a >b >c >d$ so $(1-a)< (1-b) < (1-c) < (1-d)$. So you can't have $1 \cdot 1 \cdot 1\cdot 1\cdot 10$ as a solution as that would require $1-a = 1-b=1-c= 1$. Can you take if ...
fleablood's user avatar
  • 125k
1 vote

Is there a finite dimensional vector space over a finite field with exactly two bases?

To give this question an answer: Any $\mathbb{F}_3$-vector space $V$ of dimension $1$ has exactly two bases, namely the two singletons $\{x\}$ and $\{y\}$, where $x$ and $y$ are the two non-zero ...
azimut's user avatar
  • 23k
0 votes

Proportion of vertices in components of size $k$ in Erdos Renyi

As abacaba's answer states, you've miscalculated the probability that $1,2,\dots,k$ are connected, since it may not be that $1,2,\dots,k-1$ are connected. Here it is better to compute the probability ...
Bob Krueger's user avatar
  • 6,286
1 vote

Enumerating all subsets of a family of set by size and size of union

I describe below an algorithm using Dynamic Programming. Let $A_k = \{0, 1, 2, \dots, k\}$ and $A_k^* = A_k \setminus \{0\}$ for all $k\in \mathbb{N}^*$. Also let $\mathcal{B} = \{\mathcal{B}_1, \...
EnEm's user avatar
  • 1,017
2 votes

Prove that at least two people shake hands the same number of times

Just as I posted this, this popped up in my head: $(1,1,2,2)$ --> this is a valid combination of handshakes for the unique case. Now, we add $(0,1,0,1)$ --> handshake of 2nd and 4th person and, $...
ztart14578's user avatar
0 votes

Proportion of vertices in components of size $k$ in Erdos Renyi

I think there is a mistake in computing the probability that vertices $1,2,\cdots, k$ are connected. The problem is that it might be the case that vertices $1,2, \cdots, k$ are connected, but $$1,2,\...
abacaba's user avatar
  • 9,055
10 votes
Accepted

2009th smallest number in base 10 whose binary representation contains even number of 1's

For positive integer $n$, exactly one of $2n$ and $2n+1$ is jubilant, since they differ only in the last bit. (An edge case need checking: 0 is jubilant, 1 is not. So the jubilant positive ...
Michael Lugo's user avatar
  • 22.8k
15 votes

2009th smallest number in base 10 whose binary representation contains even number of 1's

For any $k$, exactly one of $2k$ and $2k+1$ will be jubilant, because an even and the subsequent odd just differ in the rightmost bit (the even has a $0$ in the rightmost bit, the odd a $1$). Note ...
paw88789's user avatar
  • 40.9k
2 votes

2009th smallest number in base 10 whose binary representation contains even number of 1's

You get other 12-digit Jubilant numbers by replacing two 1s (not the first one) with two 0s. There's one option for the last two digit, 2 for the last three, 6 for the last four and one additional for ...
Keba's user avatar
  • 2,530
0 votes

Isosceles triangle calculations

First, prove this: For any two points $a,b∈ S$, there are at most two isosolece triangles whose base edge is $ab$. As a corollary, there are at most $2(nC2)$ isosolece triangles in $S$, as there are ...
Mike Earnest's user avatar
  • 77.6k
2 votes

Is it possible to efficiently create a matrix M in which the elements are the sum of all possible "path-products" of matrix A?

If I've understood you correctly, we have $$M = A + A^2 + A^3 + \dots = \frac{A}{I - A}.$$ (In general the notation $\frac{X}{Y}$ for two matrices is ambiguous since it could refer either to $XY^{-1}$ ...
Qiaochu Yuan's user avatar
0 votes

Number of ways to schedule activities using combination or permutation.

The problem can be solved by using Stars and Bars theory. For Stars and Bars theory, see this article and this article. It is assumed that: Neither break can occur on either of the two ends. The ...
user2661923's user avatar
  • 36.9k
1 vote

Prove $\sum_{k=0}^n\binom{2n+1}{2k}=4^n$

For a combinatorial proof, count even-cardinality subsets of $\{1,2,\dots,2n+1\}$ in two ways. The LHS is clear. For the RHS, choose an arbitrary subset of $\{1,2,\dots,2n\}$ in $2^{2n}=4^n$ ways, ...
RobPratt's user avatar
  • 47.1k
2 votes

Prove $\sum_{k=0}^n\binom{2n+1}{2k}=4^n$

$$\sum_{k=0}^n\binom{2n+1}{2k}$$ $$=\sum_{k=0}^n\left[\binom{2n}{2k}+\binom{2n}{2k-1}\right]$$ $$=\sum_{k=0}^{2n}\binom{2n}{k}$$ $$=4^n$$
JMP's user avatar
  • 21.9k

Top 50 recent answers are included