Tag Info

New answers tagged

1

http://en.wikipedia.org/wiki/Automated_theorem_proving http://en.wikipedia.org/wiki/First-order_logic The short answer to your question is, "yes" there are many computer programs that can solve and check mathematical proofs for validity of the proposition and of the proof itself. Mathematicians have been designing programs like this pretty much as long as ...


0

For simplicity, let's assume that $p = 2$ and we are dealing with input in binary. Let $F : \{0,1\}^k \to \{0,1\}$ be any boolean function. Define \begin{align} P(x_0,x_1,\ldots,x_{k-1}) &= \sum_{a \in \{0,1\}^k} F(a_0,a_1,\ldots,a_{k-1})\cdot\prod_{i = 0}^{k}\Big(a_ix_i+(1-a_i)(1-x_i)\Big) \\ &= \sum_{a \in \{0,1\}^k\ :\ F(a) = 1}\ \prod_{i = ...


2

Real people navigate complex situations like mathematical research using metaphorical or visual thinking and honed intuition developed through experience. A lot of it is unconscious reasoning that we form ad hoc rationalizations for upon demand - part of mathematical training is being able to polish such mindstuff into abstract, logical arguments. ...


0

No induction needed. Define $g_i(z_1, \dots, z_k) = \sum_{(a_1,\dots, a_k) \in X'} \left (f(a_1, \dots, a_k)_i \prod_{j=1}^k (1- (z_j - a_j)^{p-1}) \right )$. It is computable in time at most $O(p^k k^2 \ln(p))$. When $p = 2$ and $k = 100$, that explains why there are some exponential time algos. But not proven yet. We'd need to prove that there exist ...


3

Real people navigate complex situations like mathematical research using metaphorical or visual thinking and honed intuition developed through experience. A lot of it is unconscious reasoning that we form ad hoc rationalizations for upon demand - part of mathematical training is being able to polish such mindstuff into abstract, logical arguments. Part of ...


7

There might be an AI wiki where this question would be appropriate (not saying it is inappropriate here). People like Ray Kurzweil, who is currently working on making search at Google "more intelligent", have claimed that within $5$ years you will be able to ask Google a research level question, and have it come back with an answer in $2$ months say. This ...


1

Any function $f$ from $\Bbb Z_p$ to $\Bbb Z_p$ can be written as a polynomial: by Fermat's little theorem, $$ f(i) = \sum_{t=0}^{p-1} f(t)\big( 1-(i-t)^{p-1} \big). $$ In your case, you want the answer to be $k$ when $0\le i\le j$ and $(a+b)c$ when $j<i\le p+1$; so the appropriate polynomial is $$ f(i) = k \sum_{t=0}^{j} \big( 1-(i-t)^{p-1} \big) + (a+b)c ...


0

I wish to substantially refine Keith Irwin's answer as follows. Given a class of problems $\mathcal{P}$, the solution to each of which can be computed in polynomial time in the size of their inputs. This does not mean that $\mathcal{P}$ lies in the complexity class $\mathsf{P}$. Why not? Because $\mathsf{P}$ admits only decision problems ! For example, ...


1

A maximum flow is a flow that attains the highest flow value possible for the given network. A maximal flow is a flow whose value cannot be increased without decreasing the flow along some arc. All maximum flows are maximal flows. Not all maximal flows are maximum flows. Figure 3.9 in the Bang-Jensen and Gutin textbook, first edition illustrates an ...


0

@Bilou06 No of pairs of x,y satisfying $ xy \le n $ is given by $$ \sum_{k=1}^{n}\left\lfloor \frac{n}{k} \right\rfloor = 2 \sum_{k=1}^{\lfloor \sqrt{n} \rfloor} \left\lfloor \frac{n}{k} \right\rfloor - {\lfloor \sqrt{n} \rfloor}^2 $$ but for $ xy \lt n $ no of pairs is given by $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k} - 1 \right\rceil $$ or it can be ...


0

Thanks guys, the solution ended up making use of graph adjacency matrix, and disconnected graphs, credit goes to Matt J. on mathworks central: [I,J]=find(a); C=bsxfun(@eq,I,I.') | bsxfun(@eq,J,J.'); The matrix C is a graph connectivity map which you can then use to segment into groups using this FEX file, ...


1

Just a hint. Once I had to show with basic algebra (permutation groups) that a standard $15$ puzzle had no solution. The idea there was the following: to rearrange the puzzle, you have to perform a permutation of the $15$ tiles. Now, notice that once you write any permutation allowed, it is written as a product of an even number of $2$-cycles (you always ...


-1

Both terms refer to the same thing. In the Wikipedia article on the maximum flow problem both terms are used equivalently. There you can also find some references to scientific publications that use both terms.


1

Yes, it will always have a solution as long as you start with a good solution and then make legal moves to randomize the tiles. BUT if you, for example, pop two pieces out and switch them, then you can get an insolvable puzzle. ;) As you discovered.


0

As det has pointed out, although you got most of the entries needed in Group 1, you missed $(6, 4)$, being in the same row as $(6, 7)$. After verifying that there are no more that need to go in Group 1, go on to making Group 2. Hint: There are only three entries left to place into groups, namely $(3, 1)$, $(5, 3)$, and $(5, 5)$.


0

"if two elements share a row or a column they are in the same group" How? "and if say (1,2) & (1,6) in group1, then group1 will also include (2,6) & (2,7) & (6,7) & (4,2)" Why not (6,4)? Use MATLAB: % use the function [e1, e2] = find(a) e = find(a(i, :)~=0); % i = 1:size(a, 1), e is a vector of size the % number of ones in row i. ...


0

First add results for all k where the result is >= ceil (sqrt (n) + 1), that's about sqrt (n) values. Then for 1 <= m <= ceil (sqrt (n)), find exactly the set of integers k where the result is equal to m, and add m times the number of elements in that set. There are about sqrt (n) calculations for that as well, so a total of 2 x sqrt (n) calculations. ...


1

I assume the queens are indistinguishable (say, both white). Wlog. $n\le m$. Then there are $n\cdot{m\choose 2}$ ways with horizontal attacks; $m\cdot {n\choose 2}$ ways with vertical attack; $(m-n)\cdot {n\choose 2}+2\sum_{k=2}^{n-1}{k\choose 2}$ ways with "falling" diagonal attack and the same number with "rising" diagonal. Use the well-known formulas for ...


1

So the problem is, I think, to prove that the outlined algorithm computes $s(n) = \sum_{i=1}^n s_i$, for a 'list' $(s_1,\ldots,s_n)$. Yes, your base case appears correct: if $n=0$, then the list is empty, so $\sum_{i=1}^n s_i=0$ (a bit by convention) and this algorithm, too, returns $0$. Otherwise, let $n>0$. Assume that the algorithm correctly computes ...


0

But why would a problem not be in polynomial time, when you cant solve for an input n? Note as well that if a problem is NP-Complete and we assume no polynomial time algorithm to solve it, we are assuming $P \neq NP$. While no proof showing $P \neq NP$, that tends to be what people believe. I think it's also important to put out some ...


0

I think that if you fix a value for x, then it's easy to know how many y's make xy < d true. it is $\lceil d/x - 1 \rceil$ possible y's. For example, imagine $d = 10$, and fix $x = 3$, so all the possible value to y is 1,2 and 3, i.e., 1 to $\lceil d/x - 1 \rceil$. The reason that I think it's $\lceil d/x - 1 \rceil$, is that when d/x is not an integer, ...


0

In terms of programming a (probably not efficient way) to do it would be to preset two arrays for $x$ and $y$ that run through all of the values from $(2,...,d)$ write a for loop with an if statement, that multplies $x$ and $y$ together, and the if statement seperates them, so if $xy\lt d $ send tjose values to an array, then when the for loop ends, the size ...


1

The amount of such configurations is $\binom{n+k-1}{n}$. A simple combinatorial argument is that when an extra digit ($n+1$) is added, the total is comprised of all "old" configurations (all counters are less than $n+1$) and all "new" configurations (the first counter is fixed at $n+1$); in other words $F(n+1, k) = F(n, k) + F(n+1, k-1)$. Trivial boundary ...


2

You want the coefficient of $y^N$ in $$(1+y+\cdots+y^{a_1})\times\cdots\times(1+y+\cdots+y^{a_m})$$ Rewrite the product as $$(1-y^{a_1+1})\times\cdots\times(1-y^{a_m+1})(1-y)^{-m}$$ Expand $$(1-y)^{-m}=\sum_0^N{n+m-1\choose m-1}x^n+{\rm\ higher\ order\ terms}$$ Now multiply in turn by $1-y^{a_1+1},\dots,1-y^{a_m+1}$. You can always discard terms in $y^s$ ...


0

Well, instead of a faster algorithm, it is actually much easier to write it with mex or convert the matlab function with Matlab Coder, which is what I finally did...


1

Let $y = a_3x^3 + a_2x^2 + a_1x+a_0.$ Then we have the following system of equations: $$\begin{align*} 19^3 a_3 + 19^2 a_2 + 19 a_1 + a_0 &= 45, \\ 10^3 a_3 + 10^2 a_2 + 10 a_1 + a_0 &= 50, \\ 15^3 a_3 + 15^2 a_2 + 15 a_1 + a_0 &= 25, \\ 65^3 a_3 + 65^2 a_2 + 65 a_1 + a_0 &= 55, \end{align*} $$ forming the linear system $$\begin{pmatrix} ...


1

You can say: $$ x\equiv 1 \pmod{2} \Leftrightarrow y=5\cdot(x \pmod{10}) $$ $$ x\equiv 0 \pmod{2} \Leftrightarrow y=5x $$ EDIT: The following is only theorizing. $$ x > 50 \Rightarrow y=5\cdot(x \pmod{10})+\frac {x-(x \pmod{10})}{2} $$ Now transform it to a function: $$ f(x) = \left\{ \begin{array}{l l} 5\cdot(x \pmod{10}) & \quad x\equiv 1 ...


1

What are the rules? If the one's place number is nonzero, multiply it by 5 for the result. If the one's place number is zero, multiply the whole number by 5 for the result. This can likely be stated in a much better way.


0

You want to work in $\Bbb{Z}/A \Bbb{Z}$ ie the integers modulo $A$, also sometimes written $\Bbb{Z}_A$. The reason is because if you find all subsets of $\Bbb{Z}_A$ that sum to $0$, then you can automatically find all integer subsets as well since if $\{a,b,c\}$ is a solution, then $\{a', b', c'\}$ is a solution for all $a' = a + Ak_1$, $b' = b + Ak_2$, and ...


1

Replace each edge by two edges, one for each direction. Fix a vertex $t\in V$, any vertex. Now simply do Max-$s$-$t$-Flow for each $s\in V\setminus\{ t\}$ and record the smallest $s$-$t$-cut every time. When you have tried them all, choose the smallest.


1

No there are only 4 values. The 32th roots of unity are $e^{\frac{2\pi i k}{32}}, k=0\dots 31$ and the values of the polynom $f(x) = x^{16} + 8x^8 + 1\,$at those roots are $$f(e^{\frac{\pi i k}{16}}) = (e^{\frac{\pi i k}{16}})^{16}+8(e^{\frac{\pi i k}{16}})^{8}+1 =e^{\pi i k}+8e^{\frac{\pi i k}{2}}+1 = (-1)^k+8i^k+1 $$ And these values are $10, 8i, -6, ...


1

The roots of unity you are dealing with satisfy:$$0=x^{32}-1=(x^{16}+1)(x^{16}-1)=(x^{16}+1)(x^8+1)(x^8-1)$$ So they are of three kinds $x^8=1$, $x^8=-1$, $x^{16}=-1$ Note that if $x^{16}=-1$ then $x^8=\pm i$ Note also that the polynomial you are asked to evaluate is a polynomial in $x^8$ and $32=4\cdot 8$ so you expect some simplification to express the ...


1

For polynomials the starting point does not really matter, since Newton's method is contractive for large arguments, but with slow convergence. What that really means that the iteration remains bounded, and converges with high probability to one of the roots. So take any random point inside the computed root radius. You have to check for cycles in the ...


1

The only reasonable solution that comes to mind is a DP algorithm that iterates through the allowed width of the page. Each iteration you try to extend the allowed page width from k to k+1. To do this, you select a particular entry (i,j), and extend its width by 1, and then update the height of this particular row i by taking the max over all the heights ...


2

In practice, you may draw a rough graph of the function. You see approximately where are the roots. This give you for each one an approximate value to start the recurrence process. The first root obviously is $1$. The second is around $3.25$ and the third around $6.75$ The convergence will be fast in starting from these values. In fact, the analytic ...


3

The general case is very complicated. See for instance: Newton fractal How to find all roots of complex polynomials by Newton's method by Hubbard et al. Invent. Math. 146 (2001), no. 1, 1–33. pdf


2

$3e^{x-4} +2=83$, subract two from both sides: $3e^{x-4}=81$, and after dividing by $3$ and taking the natural log of both sides, we have: $(x-4)=\ln(27)$, and so: x = $ln(27)+4$


1

$$ 3e^{x-4}+2 = 83 \leftrightarrow 3e^{x-4} =81 \leftrightarrow e^{x-4} = 27 \leftrightarrow \ln\left(e^{x-4}\right)= \ln(27)\leftrightarrow x-4 = \ln(27) \leftrightarrow x= \ln(27)+4 $$


2

Notice $$ 3 e^{x-4} + 2 = 83 \iff 3 e^{x-4} = 81 \iff e^{x-4} = 27 \iff x - 4 = \ln 27 \iff \boxed{x = \ln 27 + 4 } $$


3

This concerns showing the minimal number of pyramaids is bounded. I don't know the effective value of the bound, as it depends on a theorem of Hua which implies that every sufficiently large integer is the sum of nine or ten cubes of primes. Let $s(n)=n(n+1)(2n+1)$ which is $6$ times the number of blocks of a type $1$ pyramid. Then we have the identity ...


3

As I said in the comments, you can write $$Z=\sum_{i=0}^k x2^i=x\sum_{i=0}^k 2^i=x(2^{k+1}-1)\implies x=\frac{Z}{2^{k+1}-1}.$$ It seems you already know how to justify every step. You can ask for clarification if this is not the case.


1

Not quite an answer, but a start: It's easy to show there are infinitely many integers n which require at least four pyramids: The number of blocks in a pyramid is always 0 (modulo 5), 1 (modulo 5) or 4 (modulo 5). Actually, one in five numbers is 1 (modulo 5), one in five is 4 (modulo 5) and 3 in 5 are 0 (modulo 5). To get a sum that is 2 (modulo 5), we ...


0

This is a very special case of asking for a lexicographic ordering of n-vectors of integers the sum of which may not exceed a given number k. There is a beautiful closed formula for that, so you really don't need recursion to calculate each vector's rank number (of course, the recursion will be used to prove it). The specialty comes from restricting entries ...


2

There are may ways, but the easiest is to take the outer product of the vectors: cos(pi/5 * (1:10)' * (0:N-1)) Other possibilities include using meshgrid() and repmat().


0

If we interpret our colours as ternary digits, we can come up with a mechanism for handling this fairly easily. Let's consider pairs of digits, such as 00 or 12. For notation, we will let the first digit be $a$ and the second digit be $b$, so the pair is $ab$. Now, suppose we let $c=2(a+b)\pmod3$. Then here is the table of possible pairs: 00 -> 0 01 -> 2 ...


0

The number of non-ordered pair solutions is $$ \frac12\left(\left\lfloor\sqrt{N-1}\right\rfloor+\sum_{k=1}^{N-1}\left\lfloor\frac {N-1}k\right\rfloor\right) $$ The summation counts all the ordered pairs and divides by $2$. However, this divides the pairs $(k,k)$ by two, and they should not be, so the term with the square root should take care of that.


2

Try this: int count = 0; for(int x = 2; x <= N / 2; x++) { for(int y = 2; x*y < N; y++) { count++; } } This is more efficient as it does not require the square root function. The final value of the variable 'count' is now the number of unique pairs ($(3,2)$ and $(2,3)$ are different).


0

Let $g(n)$ be the number of positive integer 4-tuples $\{a,b,c,d\}$ with $a,b,c,d \in \mathbb{Z}_{>0}$, $ad-bc>0$, and $a+d=n$. Then $$ g(n)= \sum_{a=1}^{n-1} \sum_{b,c: bc<a(n-a)} 1 = \sum_{a=1}^{n-1} D(a(n-a))-\tau(a(n-a)) $$ where $D(x)$ is the summatory divisor function (https://en.wikipedia.org/wiki/Divisor_summatory_function) $$ D(x) = ...


0

No, because for every objective function $f(x)$ you can find infinitely many other functions that have the exact same maxima, e.g., $g(x)=f(x)+1$.



Top 50 recent answers are included