New answers tagged

1

Let $(a_1, \cdots , a_k)$ be a solution to the desired equation. Note that this describes a partition of $1979$ given as $$\lambda = (a_1 \times 1, a_2\times 2, a_3\times 3, \cdots , a_k\times k),$$ i.e. each positive solution describes a unique partition of $1979$ with largest part $k$. Turning the Young diagram of the partition sideways, this translates to ...


0

I searched online and it is not a single solution for any number of teams. If n is even, and is a member of the infinite series 8,14,20,26,32,... [n=6i +2: i>=1] or a member of the series 6,12,18,24,30,36,... [n=6i : i>=1] then there is a simple modification to the cyclic algorithm that can give the necessary court balance. More details can be found at this ...


0

Say that a linear order $\langle X,\le\rangle$ is cushioned iff every order-preserving injection $f:X\to X$ has the property that $x\le f(x)$ for each $x\in X$. Let $\langle X,\le\rangle$ be an incompressible linear order. If $X$ is not cushioned, there are an order-preserving injection $f:X\to X$ and an $a\in X$ such that $f(a)<a$. Define $$g:X\to X:x\...


0

Maybe there's some elegant combinatorial solution to this problem, but you could also take the constraint optimization approach. Meaning, write up a cost function which for any given schedule returns the magnitude of the imperfections in it, and try to minimize that cost. For the minimization, I'd recommend simulated annealing (https://en.m.wikipedia.org/...


0

There are $10^{15}$ squares. There are $10^{10}$ cubes. There are $10^6$ quints. There are $10^5$ powers to the 6 which are both squares and cubes. There are $10^3$ powers to the 10 which are both squares and quints. There are $10^2$ powers to the 15 which are both cubes and quints. And there are $10$ powers to the 30 which are all three. Apply ...


3

Since $10^{30}=(10^{15})^2=(10^{10})^3=(10^{6})^5=(10^5)^6=(10^3)^{10}=(10^2)^{15}$. Thus, the number of square is $10^{15}$, the number of cubes is $10^{10}$, the number of 5-th power is $10^6$, the number of 6-th power is $10^5$, the number of 10-th power is $10^3$, the number of 15-th power is $10^2$, and the number of 30-th power is $10$. Thus, there ...


-1

There are $10^{15}$ square numbers. There are $10^{10}$ cubes. There are $10^{6}$ quints. Sorry, I've corrected this answer and don't have time to finish it, but...: We have to enumerate the permutations of $2$, $3$, and $5$ whose products reach right up to 99 and apply the inclusion-exclusion principle appropriately to all of the following numbers: $2$:...


4

To sum up to $20$, we could: first write a $1$ and count all the ways to add up to the remainder, $19$, or first write a $3$ and count all the ways to add up to the remainder, $17$, or first write a $5$ and count all the ways to add up to the remainder, $15$, or … The answer will be the sum of all these counts. Let’s denote the number of lists of odd ...


1

By your method, there are $64$ ways to place the first rook. This attacks $15$ squares, leaving $49$ ways to place the 2nd rook. This attacks 13 squares not attacked by the first rook, leaving $36$ was to place the third rook, and so on... $64 \times 49 \times 36 \times 25 \times 16 \times 9\times 4 \times 1 = (8!)^2$ But since every rook is identical ...


0

Length[Flatten[Permutations /@ IntegerPartitions[20, All, 2 Range[10] - 1], 1]] 6765 ways, according to Mathematica.


1

Note that $a^p \equiv a \pmod p$ if $p \not \mid a$ and $a^p \equiv 0 \pmod p$ if $p \mid a$. This comes from Fermat's Little Theorem. So using these we can determine when a number is a p-remainder-number. So a number is p-remainder-number iff the sum of all digits of the number that aren't divisible by $p$ is divisible by $p$. For the second one I don't ...


3

Obviously you have to place a rook on the each of the $8$ columns. Now for the first column we have $8$ options. For the second we have $7$, as one of the rows is already taken by the previous rook and so on. Eventually you will get that the number of ways to place them is $8! = 40320$. To see why your reasoning is false note that the rooks aren't ...


4

There are $10\cdot9\cdot8\cdot7\cdot6=30\,240$ strings having $5$ different digits. One tenth of these strings begin with a $0$, which is forbidden. The number of admissible strings therefore is $27\,216$.


2

As derived at Balls In Bins With Limited Capacity, there are $$ \sum_{t=0}^m(-1)^t\binom mt\binom{m+n-t(r+1)-1}{m-1} $$ ways to distribute $n$ balls over $m$ bins with capacity $r$, where, contrary to convention, binomial coefficients with negative upper index are taken to be zero. If we subtract $1$ from each die and regard a die with rolls up to $k$ as a ...


6

You need to split into two cases, according to whether or not the $0$ appears in the least $4$ slots. Case I: the $0$ does appear. There are $4$ ways to place the $0$, then $9\times8\times 7\times 6$ ways to populate the other slots. Thus $$ 4\times 9\times 8\times 7\times 6=\boxed{12096}$$ Case II: the $0$ does not appear. Then you just have nine ...


0

You can work recursively. For the minimum: Denote the sum of the minimums with $m_n$ $$m_n:=\sum_{A\subset S_n}\min A$$ where $S_n=\{1,2,\dots,n\}$. Hence $S_n$ has $2^n$ subsets. Now consider the set $S_{n+1}=\{1,2,\dots,n,n+1\}$. The set $S_{n+1}$ has $2^{n+1}=2^n+2^n$ sets. The first $2^n$ sets are exactly the subsets of $S_n$ and the other $2^n$ are ...


1

There are $35$ partitions of $10$ with maximal part $\leq6$. Example: The partition $(4,2,2,1,1)$ has maximal part $4$, requires $5$ throws, and can be realized in $5\cdot{4\choose 2}=30$ ways. The probability that this partition is realized therefore comes to $30/6^5$. Going through all $35$ partitions in this way leads to the following probabilities $...


0

There are six ways to end the game: scores of 10 through 15. We only care about the cases of a 10, and the rest are bust. Drawing this as a digraph, we see the number of ways reaching: 492 484 468 436 373, and 248 for a total of 2501 possible roll combinations giving an outcome of the game. Therefore, the odds of winning are $$\frac{492}{2501}=0....


1

max of 6 happens in the following ways where the order doesn't matter [6,4]; [6,3,1]; [6,2,2]; [6,2,1,1]; [6,1,1,1,1]; Let's use the [6,2,1,1] case as an example. The exact ordering 6211 happens with probability $\frac{1}{6^{4}}$. Then it's a matter of figuring out how many distinct orderings there are. But this is $\frac{4!}{2!1!1!} = 12$ and thus, the ...


0

With varying counterfeit weights, I don't think there's any point in weighing groups of coins against each other. So all weighings will be one coin to one coin. As soon as one balance is found, those coins are true and can be used as a reference to check all other coins (where their status is unknown) A somewhat analogous graph theory problem would be ...


2

my hunch is this. Each weighing can turn out one of 3 ways -- be left side heavy, right side heavy or ballance. If we put the coins in a line, there are ${11\choose 7} = 28$ ways the counterfeits could be arranged. But each coin could be one of 8 different weights! I think there are $28\cdot8!$ different distributions to identify. $n > \log_3 28\...


0

$$1+2+...+9=\frac{9\cdot10}{2}=45\\(x_1+x_3+x_5+x_7+x_9)-(x_2+x_4+x_6+x_8)=11m$$ $m$ must be $1$ or $3$ since 45 is odd and $3$ is discarded immediately so we have $$\begin{cases}X+Y=45\\X-Y=11\end{cases}$$ Hence $X=28$ and $Y=17$ We work with $28$. 1) With $9$ and $8$ one has $x_1+x_2=11$ and $x_1+x_2+x_3=11$ (because $28-(9+8)=11$). $x_1+x_2=7+4=6+5$ ...


2

The number of edges of $K_n$ is $\binom{n}2=\frac12n(n-1)$, so if you’re told that you have $e$ edges, you need to solve $2e=n(n-1)$ for $n$. It’s always true that $n-1<\sqrt{n(n-1)}<n$, so $$n=\left\lceil\sqrt{2e}\right\rceil\;,$$ the integer obtained by rounding up $\sqrt{2e}$. For values of $2e$ with no more than four digits, $n$ will be a two-...


2

If you can estimate square roots, you can try the following approach: If there are $v$ vertices and $e$ edges in a complete graph, then we have $e=\frac{v(v-1)}{2}$. So $2e=v^2-v$. But also $v^2-v$ is between $(v-1)^2$ and $v^2$. That is, $(v-1)^2<2e<v^2$. So $v-1<\sqrt{2e}<v$. So $v$ can be found by taking the square root of $2e$ and ...


3

In this particular case (number of edges in a complete graph), it's easy, because the number is $\frac12 n(n-1)$. So you have $$n(n-1)=210$$ and $n(n-1)$ lies between the consecutive squares $(n-1)^2$ and $n^2$. So obviously $n=15$. You can use this trick well into the thousands, I would think.


2

You could use guess and check. If a complete graph has $n$ vertices, then it has $f(n) = n(n-1)/2$ edges --- the number of different "handshakes" between $n-1$ people if everyone shakes everyone else's hand. So for example, you could compute various values of $f(n)$: $f(1) = 1$, $f(2) = 3$, $f(3) = 6$, $f(4) = 10$, and so on. You can guess large values for $...


0

In the simplified case, since all the coordinates are symmetric, if the closest vector has $k$ coordinates equal to $1$, then the probability that the $i$th coordinate has value $1$ is equal to $\frac{k}{t}$. Hence, if we let $X$ denote the number of $1$'s in the closest vector, the probability that the $i$th coordinate is equal to $1$ is given by $\sum_{k=...


0

Here is a way to see that $$ \sum_{k=0}^{n} {2n+1 \choose k} = 2^{2n}, $$ by a counting argument which counts the number of subsets of $\{1, \ldots, 2n\}$ rather than half the number of subsets of $\{1, \ldots, 2n, 2n+1\}$. Essentially to count the subsets of $\{1, \ldots, 2n\}$, we break the subsets into whether or not their size is at most $n$. Now to ...


2

Note. I assume that $m(\emptyset)=0$. Question. Consider the set $S=\{1,2,3,\dots,j\}$. Let $m(A)$ denote a maximum element of a subset $A$ of $S$. Prove that $$\sum_{A\subseteq S}m(A) = (j-1)2^j+1$$ where summation ranges over all subsets $A$ of $S$. Solution. Let us consider the element $4$. $4$ will be maximum element if we pick elements from ...


0

The question is to find three positive integers $A$ and $B$ and $ C$ such that $A \times B \times C = 2104000$. The way you can solve questions like these is by factoring the number 2104000. Here's a simpler example. Find three positive integers $A$, $B$, $C$ so that $A\times B \times C = 60$. By examining the number 60, you can remember or figure out ...


3

There are $9\cdot10^4$ five-digit numbers, since there are $9$ choices for the first digit, and $10$ choices for the next $4$ digits. Of these numbers, $8\cdot 9^4$ do not contain $4$ as a digit. Therefore the number of $5$-digit numbers with at least one $4$ as a digit is equal to $$ 9\cdot 10^4-8\cdot 9^4=37512$$


1

The easiest is to just subtract all of the ones that don't: 1 digit numbers: 8 possibilities (1,2,3,5,6,7,8,9) 2 digit numbers: 8 possibilities for the first * 9 possibilities for the second (0,1,2,3,5,6,7,8,9) = 72 3 digit numbers: 8 possibilities for the first * 9 possibilities for the second (0,1,2,3,5,6,7,8,9) * 9 possibilities for the third (0,1,2,3,...


1

All combinatorics problems cannot always be solved by methods other than exhaustive search of the search space. This problem can't be done with multiplication and division, but it can be solved in the general case without resorting to brute force search of all possible permutations. There are three main cases and I offer explanations of each of them. By the ...


0

Since all the integers are positive, we can only have $$x_1+x_2+x_3=3$$ $$y_1+y_2+y_3+y_4=5$$ In the first equation, clearly $x_1=x_2=x_3=1$ In the second,only one is equal to $2$ and everything else is equal to 1 Hence, the solutions: $$(1,1,1)(2,1,1,1)$$ $$ (1,1,1)(1,2,1,1)$$ $$(1,1,1)(1,1,2,1)$$ $$(1,1,1)(1,1,1,2)$$ 4 possibilities.


0

$15 = 5 * 3$, So $(x_1 + x_2 + x_3) = 3$ or $5$ same for the other one. $(y_1 + y_2 + y_3 + y_4) = 3$ has no solution. $\therefore$ $(x_1 + x_2 + x_3) = 3$ and $(y_1 + y_2 + y_3 + y_4) = 5$. Now you know $x_1, x_2, x_3$ can't be greater than $1$. $\therefore$ the only solution for it is $(1 + 1 + 1)$. In $(y_1 + y_2 + y_3 + y_4) = 5$, only one ...


4

Since $15 = 1\cdot15 = 3 \cdot 5$, the only possibilities are $$(x_1 + x_2 + x_3, y_1 + y_2 + y_3 + y_4) = (1, 15), (15, 1), (3, 5), (5, 3)$$ Since the variables are all at least $1$, we can rule out the case where $x_1 + x_2 + x_3 = 1$ or where $y_1 + y_2 + y_3 + y_4 = 1, 3$ for the minimum values of each sum exceeds the respective assignments. This ...


1

I interpret your $S_1$ as the set of all combinations of cards that have at least one same suit Ace King pair. Similarly, I interpret your $S_2$ as the set of all combinations that have at least two same suit Ace King pair. Then indeed the number of combinations with exactly one same suit Ace King pair is $|S_1|-|S_2|$. However, the first term $\binom{4}{1}...


1

The issue is that the $S_2$ that you define in words does have ${4 \choose 2}{4 \choose 4}{48 \choose 9}$ card hands. There is an over counting here that must be dealt with. To see this, let's break down these binomial coefficients. First, we choose the two suits for our pairs. [${4 \choose 2}$ ways to do this] Second, once we've chosen the suits, there ...


2

According to Eilenberg [1, Chap. IV, Prop. 1.1], the following result holds: Proposition. For any nonempty subset $L$ of $A^*$, the following conditions are equivalent: for all $u, v \in L$, $u^{-1}L = v^{-1}L$, the minimal automaton of $L$ has a single final state, $L$ is recognized by a deterministic automaton with a single final state that ...


7

Let's denote such a number by $\overline{a_9 a_8\cdots a_1}$ you get $$\sum_{i=1}^9 a_i = \sum_{i=1}^9 i = 45.$$ Furthermore we can indeed use the alternating sum to check divisibility by $11$. This can be expressed as $$(a_1+a_3+a_5+a_7+a_9) - (a_2+a_4+a_6+a_8) \equiv 0 \pmod{11}.$$ Since we already know the total sum of the digits we can simplify this ...


5

Since the raw digit sum of $1..9$ will be $45$, an odd number, we clearly can't have two equal sums for the even-position and odd-position digits. So we need to have one set of digits sum to $17$ and the others to $28$, so that the difference is divisible by $11$. This can be done either way around; $28$ as the sum of the four even-position digits or the ...


2

Denote by $a_1a_2...a_9$ such a number. Let $a=\sum_{i=0}^4 a_{2i+1}$ and $b=\sum_{i=1}^4 a_{2i}$, then $b-a$ is a multiple of 11. Note that since $a+b=1+2+...+9=45$ is odd necessarily $b-a$ is odd. So $a-b=11$ or $a-b=33$. Case $b-a =11$ If we add the equation $a+b=45$ we obtain $b=28$, and $a=17$. Now it is easy to write down all solutions. Case $b-a ...


0

WLOG, {v_1,..v_2n}={0,...,2n-1}=2n (by the Von-Neumann ordinal convention of k={0,..,k-1}). Our chosen set is determined by its intersection with n which is an arbitrarily chosen element of the powerset P(n) with cardinality 2^n .


1

For each $m = 1 \ldots M$, let $g(m) = \min\{i:a_{im} = 1\}$ and $h(m) = \max \{j: b_{mj} = 1\}$. In order for $C$ to be strictly lower triangular, what we need is $g(m) > h(m)$. We may as well take $h(m) = g(m) - 1$, and assume $a_{im} = 1$ for all $i \ge g(m)$ and $b_{mj} = 1$ for all $j\le h(m)$. Then $c_{ij} > 0$ iff there is $m$ such that $i \...


-1

Using inclusion-exclusion we obtain immediately $$2^{2n} + \sum_{k=1}^n {n\choose k} (-1)^{k} 2^{2n-2k} = \sum_{k=0}^n {n\choose k} (-1)^{k} 2^{2n-2k} = (-1+4)^n \\ = 3^n.$$ Remark. This is for the case of the subsets not containing the forbidden pairs having any size. We now do the case of the subsets containing $n$ elements, with the same ...


2

You have set the requirement for subsets that do not contain both $v_i$ and $v_{n+i} $. However, in order for such a subset to have $n$ elements, it is clear that it must contain one of these. As such, every subset can be generated by combining all those choices between $v_i$ and $v_{n+i} $. Each of those choices is binary, and there are $n$ choices, ...


0

In the second formula you give for the number of was to draw a two pair which is a product of $6$ terms, the outcomes (4, heart and spade, 3, heart and diamond, J, club) and (3, heart and diamond, 4, heart and spade, J, club) are counted as different hands when in fact they are the same five-card hand. So you need to divide this value by $2$ to get the ...


1

There is a basic counting principle called the product rule, which says the following: in an experiment consisting of two steps, if the number of ways to do the first step is $n_1$, and the number of ways to do the second step is $n_2$ for each of the $n_1$ outcomes in the first step, then the total number of possible outcomes for the experiment is the ...


3

You can always make a non-deterministic automaton with a single accepting state for any regular language (even without $\varepsilon$-transitions) -- unless the language contains the empty string and is not closed under concatenation. Just take an automaton without this restriction and create a new accepting state, and then for each transtion into a state ...


3

There is an index of notations in the book on page 573. If you look up "$\Delta$" in it, you see that this is the symmetric difference of sets: $$X \mathbin\Delta Y = (X \setminus Y) \cup (Y \setminus X).$$ It does not appear to be an operation on graphs, just on sets.



Top 50 recent answers are included