Welcome, Guest. Please login or register.

August 24, 2019, 05:38:32 am

Author Topic: "Challenge" Math Qs - Can You Figure It Out?  (Read 3313 times)  Share 

0 Members and 1 Guest are viewing this topic.

lzxnl

  • Victorian
  • ATAR Notes Legend
  • *******
  • Posts: 3430
  • Respect: +207
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #15 on: December 24, 2018, 07:00:26 pm »
0
Shouldn't the upper boundary be \( \frac\pi2\) here if you're trying to allude to a classic?

(In any case it can't be \(\pi\) because "\(\sec\) is negative in the second quadrant", so \(\ln (\sec x) \) would be non-real)
I mean you probably could still define this integral perfectly the way I originally wrote it, but you're right; I really shouldn't make this more complicated than it already is. Fixed.
« Last Edit: December 24, 2018, 07:05:09 pm by lzxnl »
2012
Mathematical Methods (50) Chinese SL (45~52)

2013
English Language (50) Chemistry (50) Specialist Mathematics (49~54.9) Physics (49) UMEP Physics (96%) ATAR 99.95

2014-2016: University of Melbourne, Bachelor of Science, Diploma in Mathematical Sciences (Applied Maths)

2017-2018: Master of Science (Applied Mathematics)

2019-: ???

Accepting students for  VCE tutoring in Maths Methods, Specialist Maths and Physics! PM for more details

AlphaZero

  • MOTM: DEC 18
  • Forum Obsessive
  • ***
  • Posts: 308
  • \[F(s)=\int_0^\infty \!f(t)e^{-st}\,\text{d}t\]
  • Respect: +128
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #16 on: December 24, 2018, 10:59:49 pm »
+5
My Set 3 Solutions

Question 1 Solution
\begin{align*}\Big[Q\mid I\Big]&=\begin{bmatrix}3&0&-2&1&0&0\\4&-1&1&0&1&0\\4&1&1&0&0&1\end{bmatrix}\\
&\sim\begin{bmatrix}1&0&-2/3&1/3&0&0\\1&-1/4&1/4&0&1/4&0\\1&1/4&1/4&0&0&1/4\end{bmatrix}\\
&\sim\begin{bmatrix}1&0&-2/3&1/3&0&0\\0&-1/4&11/12&-1/3&1/4&0\\0&1/4&11/12&-1/3&0&1/4\end{bmatrix}\\
&\sim\begin{bmatrix}1&0&-2/3&1/3&0&0\\0&1&-11/3&4/3&-1&0\\0&0&11/6&-2/3&1/4&1/4 \end{bmatrix}\\
&\sim\begin{bmatrix}1&0&-2/3&1/3&0&0\\0&1&0&0&-1/2&1/2\\0&0&1&-4/11&3/22&3/22 \end{bmatrix}\\
&\sim\begin{bmatrix}1&0&0&1/11&1/11&1/11\\0&1&0&0&-1/2&1/2\\0&0&1&-4/11&3/22&3/22 \end{bmatrix}\\
&=\Big[I\mid Q^{-1}\Big]\end{align*}Hence, we have \begin{align*}QDQ^{-1}&=\begin{bmatrix}3&0&-2\\4&-1&1\\4&1&1\end{bmatrix}\begin{bmatrix}1&0&0\\0&1/4&0\\0&0&1/12\end{bmatrix}\begin{bmatrix}1/11&1/11&1/11\\0&-1/2&1/2\\-4/11&3/22&3/22\end{bmatrix}\\
&=\begin{bmatrix}3&0&-2\\4&-1&1\\4&1&1\end{bmatrix}\begin{bmatrix}1/11&1/11&1/11\\0&-1/8&1/8\\-1/33&1/88&1/88 \end{bmatrix}\\
&=\begin{bmatrix}1/3&1/4&1/4\\1/3&1/2&1/4\\1/3&1/4&1/2 \end{bmatrix}\\
&=A \end{align*}

Question 2 Solution
First, note that \[A^k=(QDQ^{-1})^k=\underbrace{QDQ^{-1}\;QDQ^{-1}\dots QDQ^{-1}\;QDQ^{-1}}_{k\text{ times}}=Q\underbrace{D\dots D}_{k\text{ times}}Q^{-1}=QD^kQ^{-1}\] and that \[D^k=\begin{bmatrix}1^k&0&0\\0&(1/4)^k&0\\0&0&(1/12)^k \end{bmatrix}=\begin{bmatrix}1&0&0\\0&(1/4)^k&0\\0&0&(1/12)^k \end{bmatrix}.\] Hence, \begin{align*}\lim_{k\to\infty}A^k&=\lim_{k\to\infty}(QD^kQ^{-1})\\
&=\begin{bmatrix}3&0&-2\\4&-1&1\\4&1&1\end{bmatrix}\begin{bmatrix}1&0&0\\0&0&0\\0&0&0 \end{bmatrix}\begin{bmatrix}1/11&1/11&1/11\\0&-1/2&1/2\\-4/11&3/22&3/22 \end{bmatrix}\quad\quad\Big[(1/4)^k,(1/2)^k\to0\ \text{as}\ k\to\infty\Big]\\
&=\begin{bmatrix}3&0&-2\\4&-1&1\\4&1&1\end{bmatrix}\begin{bmatrix}1/11&1/11&1/11\\0&0&0\\0&0&0\end{bmatrix}\\
&=\begin{bmatrix}3/11&3/11&3/11\\4/11&4/11&4/11\\4/11&4/11&4/11\end{bmatrix} \end{align*}

Question 3 Solution
\(A\) is a right stochastic matrix.

Great questions @Rui :)



My Set 4 Solutions

Question 1 Solution
\[I=\int_0^{\pi/2}\frac{\sin^\pi(x)}{\sin^\pi(x)+\cos^\pi(x)}\;dx\] We will make use of the substitution \(u=\dfrac{\pi}{2}-x\implies -\dfrac{du}{dx}=1\) so that \[I=-\int_{\pi/2}^0\frac{\sin^\pi(\pi/2-u)}{\sin^\pi(\pi/2-u)+\cos^\pi(\pi/2-u)}\;du=\int_0^{\pi/2}\frac{\cos^\pi(u)}{\sin^\pi(u)+\cos^\pi(u)}\;du.\]Thus, \begin{align*}2I&=\int_0^{\pi/2}\frac{\sin^\pi(x)}{\sin^\pi(x)+\cos^\pi(x)}\;dx+\int_0^{\pi/2}\frac{\cos^\pi(x)}{\sin^\pi(x)+\cos^\pi(x)}\;dx\\
&=\int_0^{\pi/2}dx\\
&=\frac{\pi}{2}. \end{align*}Hence, \(I=\dfrac{\pi}{4}\).

Question 2 Solution
\[I=\int_0^{\pi/2}\log(\sec(x))\;dx\] We will use the substitution \(u=\dfrac{\pi}{2}-x\implies -\dfrac{du}{dx}=1\) so that \[I=-\int_{\pi/2}^0\log\left[\sec\left(\frac{\pi}{2}-u\right)\right]\;du=\int_0^{\pi/2}\log(\csc(u))\;du\]Thus, we have \begin{align*}2I&=\int_0^{\pi/2}\log(\sec(x))\;dx+\int_0^{\pi/2}\log(\csc(x))\;dx\\
&=\int_0^{\pi/2}\log(2\csc(2x))\;dx\\
&=\int_0^{\pi/2}\log(2)\;dx+\int_0^{\pi/2}\log(\csc(2x))\;dx \end{align*} Now, we use the substitution \(v=2x\implies\dfrac12\dfrac{dv}{dx}=1\) so that \[2I=\frac{\pi}{2}\log(2)+\frac{1}{2}\int_0^\pi\log(\csc(v))\;dv.\]But, \(\csc(\pi-\theta)\equiv\csc(\theta)\), so \begin{align*}2I&=\frac{\pi}{2}\log(2)+\int_0^{\pi/2}\log(\csc(x))\;dx\\
&=\frac{\pi}{2}\log(2)+\int_0^{\pi/2}\log(\sec(x))\;dx\\
&=\frac{\pi}{2}\log(2)+I\end{align*}Hence, \(I=\dfrac{\pi}{2}\log(2)\).

Thanks @lzxnl. I've always loved these types of integrals. They're difficult, but once you see it, it looks super obvious (esp. the first one) :P
« Last Edit: December 25, 2018, 12:03:50 am by dantraicos »
2015\(-\)2017:  VCE
2018\(-\)2021:  Bachelor of Biomedicine and Concurrent Diploma in Mathematical Sciences, University of Melbourne


RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8451
  • "All models are wrong, but some are useful."
  • Respect: +2313
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #17 on: December 25, 2018, 08:50:31 am »
+5
May be worth mentioning that the first one can be generalised. It turns out that \( \int_0^{\pi/2} \frac{\sin^A x}{\cos^A x + \sin^A x}dx = \int_0^{\pi/2} \frac{\cos^A x}{\cos^A x + \sin^A x} dx = \frac\pi4 \) for all \( A \in \mathbb{R} \). Basically that working out can be replicated for any power, and that power of \(\pi\) was just some arbitrary choice for \(A\).

But yeah my question was basically teasing at stochastic matrices and also eigenvalues :P

NEXT QUESTION: Got given this one ages ago and it was just ugly. (Merry Christmas.)
\[ \int \frac{(x-1)\sqrt{x^4+2x^3 +4x^2+2x+1}}{x^2(x+1)}dx \]

TheBigC

  • Guest
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #18 on: December 25, 2018, 02:11:42 pm »
+1
Just wanted to throw in a quick comment.

I love the way this thread has taken off! I am seeing some really fun questions here! ;) Cannot wait for more awesome stuff... Merry Christmas everyone!

lzxnl

  • Victorian
  • ATAR Notes Legend
  • *******
  • Posts: 3430
  • Respect: +207
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #19 on: December 25, 2018, 09:57:46 pm »
+4
May be worth mentioning that the first one can be generalised. It turns out that \( \int_0^{\pi/2} \frac{\sin^A x}{\cos^A x + \sin^A x}dx = \int_0^{\pi/2} \frac{\cos^A x}{\cos^A x + \sin^A x} dx = \frac\pi4 \) for all \( A \in \mathbb{R} \). Basically that working out can be replicated for any power, and that power of \(\pi\) was just some arbitrary choice for \(A\).

But yeah my question was basically teasing at stochastic matrices and also eigenvalues :P

NEXT QUESTION: Got given this one ages ago and it was just ugly. (Merry Christmas.)
\[ \int \frac{(x-1)\sqrt{x^4+2x^3 +4x^2+2x+1}}{x^2(x+1)}dx \]

Indeed. I like picking strange values for A because it throws people off :D

I was waiting for someone to comment on eigenvalues for that one.

RuiAce's integral is absolutely terrible to do. I'm not going to fully back-substitute, because that answer becomes a gargantuan mess.



Man, had to dig a bit into my bag of tricks for that one.

Here is an easy one suitable for year 12 students.

1. Differentiate \(\frac{e^{ix}}{\cos(x) + i\sin(x)}\) with respect to \(x\) where \( i\) is the imaginary unit. Comment on your result.

Here is a harder one.

Given that \( \int_{-\infty}^\infty e^{-x^2}\,dx = \sqrt{\pi} \), calculate

Yes, the technique could be followed by a high school student, but I don't expect them to think of this.
2012
Mathematical Methods (50) Chinese SL (45~52)

2013
English Language (50) Chemistry (50) Specialist Mathematics (49~54.9) Physics (49) UMEP Physics (96%) ATAR 99.95

2014-2016: University of Melbourne, Bachelor of Science, Diploma in Mathematical Sciences (Applied Maths)

2017-2018: Master of Science (Applied Mathematics)

2019-: ???

Accepting students for  VCE tutoring in Maths Methods, Specialist Maths and Physics! PM for more details

GMT. -_-

  • Trailblazer
  • *
  • Posts: 35
  • Respect: +2
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #20 on: December 25, 2018, 10:37:22 pm »
0
For lzxnl's first question, the derivative would be 0 (numerator would have e^ix(cos(x) +i sin(x)) - (i cos(x) - sin(x)) which when expanded becomes 0 ). However, e^ix is defined as cos(x)+isin(x). You would think that anything besides 0 divided by itself would be 1 but apparently not for this case!

lzxnl

  • Victorian
  • ATAR Notes Legend
  • *******
  • Posts: 3430
  • Respect: +207
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #21 on: December 25, 2018, 10:55:58 pm »
0
For lzxnl's first question, the derivative would be 0 (numerator would have e^ix(cos(x) +i sin(x)) - (i cos(x) - sin(x)) which when expanded becomes 0 ). However, e^ix is defined as cos(x)+isin(x). You would think that anything besides 0 divided by itself would be 1 but apparently not for this case!
The point is more to show that this definition makes sense to a high school student, not to prove the definition. Then, it's about making an appropriate comment regarding zero derivative. I think you're overlooking something in your answer there.
2012
Mathematical Methods (50) Chinese SL (45~52)

2013
English Language (50) Chemistry (50) Specialist Mathematics (49~54.9) Physics (49) UMEP Physics (96%) ATAR 99.95

2014-2016: University of Melbourne, Bachelor of Science, Diploma in Mathematical Sciences (Applied Maths)

2017-2018: Master of Science (Applied Mathematics)

2019-: ???

Accepting students for  VCE tutoring in Maths Methods, Specialist Maths and Physics! PM for more details

RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8451
  • "All models are wrong, but some are useful."
  • Respect: +2313
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #22 on: December 25, 2018, 10:57:18 pm »
0
snip
Haha, this was a rare integral where I found that using a trigonometric substitution was better than a hyperbolic substitution. That route made it a bit harder ;)
\[ u+1 = \tan \theta \implies du = \sec^2\theta \,d\theta. \]
\begin{align*} \int \frac{\sqrt{(u+1)^2 + 1}}{u+2}du&= \int \frac{\sqrt{\tan^2\theta +1}}{\tan\theta+1}\sec^2\theta \, d\theta\\ &= \int \frac{\sec^3\theta}{\tan\theta+1}d\theta\\&= \int \frac{\sec^2\theta}{1+\tan\theta}\sec\theta\,d\theta\\ &= \int \frac{\tan^2\theta+1}{\tan\theta+1}\sec\theta \\ &= \int \tan\theta\sec\theta-\sec\theta - \frac{2\sec\theta}{\tan \theta+1}\,d\theta\\ &= \sec\theta - \ln |\sec\theta+\tan\theta| - 2\int \frac{d\theta}{\sin\theta+\cos\theta}\end{align*}
\[ \text{of which that last integral can be treated as}\\ \int \frac{d\theta}{\sin\theta+\cos\theta} = \int \frac{d\theta}{\sqrt{2} \sin\left (\theta + \frac\pi4 \right)}\\ \text{and }\int \csc x \,dx = -\ln |\csc x + \cot x|+C \]
For lzxnl's first question, the derivative would be 0 (numerator would have e^ix(cos(x) +i sin(x)) - (i cos(x) - sin(x)) which when expanded becomes 0 ). However, e^ix is defined as cos(x)+isin(x). You would think that anything besides 0 divided by itself would be 1 but apparently not for this case!
You're right about the final answer but I think the intended approach was to use the quotient rule to bash that the derivative was equal to 0, before justifying it by Euler's formula.

Also, I don't think \(e^{ix}\) is 'defined' as \(\cos x + i \sin x\). It is something that can be proven via Taylor series
________________________________________

Anyway won't steal that integral (although hahaha, \(n\)-th moment of a normal distribution). But I just wanted to put up some C code for problem set 2 because I thought it was a fun programming exercise.
Code: (22dec2018question.c) [Select]
// Finds and prints the first matrix that works
// If none exists, mention that none exists
// Designed specifically for matrices over Z_2

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Size of matrix - can be changed
#define SIZE 4

typedef struct matrixRep *Matrix;
typedef struct matrixRep {
  int mm[SIZE][SIZE];
} _matrix;

Matrix newMatrix();
void destroyMatrix(Matrix m);
unsigned long long maxNumIterations(unsigned int size);
void matrixInit(Matrix m, int i);
void idInit(Matrix id);
void kkInit(Matrix k);
bool matrixCmp(Matrix a, Matrix b);
Matrix matrixAdd(Matrix a, Matrix b);
Matrix matrixMult(Matrix a, Matrix b);
Matrix matrixCube(Matrix m);
Matrix matrixFourth(Matrix m);
void printMatrix(Matrix m);

int main() {

  Matrix m, mcubed, mfourth, msum;
  Matrix id, kk;
  unsigned long long n = maxNumIterations(SIZE);
  bool found = false;

  id = newMatrix();
  idInit(id);
  kk = newMatrix();
  kkInit(kk);

  m = newMatrix();

  for (unsigned long long i = 0; i < n; i++) {
    if (found) break;
    matrixInit(m, i);
    mcubed = matrixCube(m);
    msum = matrixAdd(mcubed, m);
    mfourth = matrixFourth(m);

    if (matrixCmp(msum, kk) && matrixCmp(mfourth, id)) found = true;
    destroyMatrix(mcubed);
    destroyMatrix(msum);
    destroyMatrix(mfourth);
  }

  if (found) {
    printf("Found matrix:\n");
    printMatrix(m);
    printf("\n");
  } else {
    printf("Not found.\n");
  }

  destroyMatrix(id);
  destroyMatrix(kk);
  destroyMatrix(m);
  return 0;
}

// newMatrix: allocates memory for a new matrix
Matrix newMatrix() {
  Matrix new = calloc(1, sizeof(struct matrixRep));
  return new;
}

// destroyMatrix: frees up memory associated with a matrix
void destroyMatrix(Matrix m) {
  free(m);
}

// maxNumIterations: computes 2^(size^2) - the max amount of times
// the loop in the main function can run for
unsigned long long maxNumIterations(unsigned int size) {
  unsigned long long n = 1;
  unsigned long int sizeSq = size*size;
  for (unsigned long int i = 0; i < sizeSq; i++) {
    n <<= 1;
  }
  return n;
}

// matrixInit: sets up m for the current value of i in the main function's loop
void matrixInit(Matrix m, int n) {
  int mask = 1;
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      m->mm[i][j] = n & mask;
      mask <<= 1;
      m->mm[i][j] = (m->mm[i][j] == 0) ? 0 : 1;
    }
  }
}

// idInit: sets up the identity matrix
void idInit(Matrix id) {
  int posOfOne = 0;
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      if (j == posOfOne) id->mm[i][j] = 1;
      else id->mm[i][j] = 0;
    }
    posOfOne++;
  }
}

// kkInit: sets up the matrix of 1's
void kkInit(Matrix k) {
  for (int i = 0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++)
      k->mm[i][j] = 1;
}

// matrixCmp: checks if two
bool matrixCmp(Matrix a, Matrix b) {
  bool same = true;
  for (int i = 0; i < SIZE; i++) {
    if (!same) break;
    for (int j = 0; j < SIZE; j++) {
      if (a->mm[i][j] != b->mm[i][j]) {
        same = false;
        break;
      }
    }
  }
  return same;
}

// matrixAdd: computes the sum of two matrices
Matrix matrixAdd(Matrix a, Matrix b) {
  Matrix sum = newMatrix();
  for (int i = 0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++)
      sum->mm[i][j] = a->mm[i][j] ^ b->mm[i][j];
  return sum;
}

// matrixMult: computes the product of two matrices
Matrix matrixMult(Matrix a, Matrix b) {
  Matrix prod = newMatrix();
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      for (int k = 0; k < SIZE; k++)
        prod->mm[i][j] += a->mm[i][k] * b->mm[k][j];
       
      prod->mm[i][j] &= 1;
    }
  }
  return prod;
}

// matrixCube: computes the cube of a matrix
Matrix matrixCube(Matrix m) {
  Matrix msq = matrixMult(m, m);
  Matrix mcb = matrixMult(msq, m);
  destroyMatrix(msq);
  return mcb;
}

// matrixFourth: computs the fourth power of a matrix
Matrix matrixFourth(Matrix m) {
  Matrix msq = matrixMult(m, m);
  Matrix mfr = matrixMult(msq, msq);
  destroyMatrix(msq);
  return mfr;
}

// printMatrix: displays a matrix to stdout
void printMatrix(Matrix m) {
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++)
      printf("%d ", m->mm[i][j]);
    printf("\n");
  }
}
...but then soon enough I realised how shit this code was because it's an \( \mathcal{O}(2^{n^2}) \) algorithm (slow when \(n=5\)) :'( wonder if improvements can be made to it. I know that right now it's checking matrices which aren't of full rank which is redundant. Anyone got suggestions on some easy math that I can probably convert into code to make it faster?
« Last Edit: December 25, 2018, 11:02:21 pm by RuiAce »

lzxnl

  • Victorian
  • ATAR Notes Legend
  • *******
  • Posts: 3430
  • Respect: +207
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #23 on: December 25, 2018, 11:15:51 pm »
0
Haha, this was a rare integral where I found that using a trigonometric substitution was better than a hyperbolic substitution. That route made it a bit harder ;)
\[ u+1 = \tan \theta \implies du = \sec^2\theta \,d\theta. \]
\begin{align*} \int \frac{\sqrt{(u+1)^2 + 1}}{u+2}du&= \int \frac{\sqrt{\tan^2\theta +1}}{\tan\theta+1}\sec^2\theta \, d\theta\\ &= \int \frac{\sec^3\theta}{\tan\theta+1}d\theta\\&= \int \frac{\sec^2\theta}{1+\tan\theta}\sec\theta\,d\theta\\ &= \int \frac{\tan^2\theta+1}{\tan\theta+1}\sec\theta \\ &= \int \tan\theta\sec\theta-\sec\theta - \frac{2\sec\theta}{\tan \theta+1}\,d\theta\\ &= \sec\theta - \ln |\sec\theta+\tan\theta| - 2\int \frac{d\theta}{\sin\theta+\cos\theta}\end{align*}
\[ \text{of which that last integral can be treated as}\\ \int \frac{d\theta}{\sin\theta+\cos\theta} = \int \frac{d\theta}{\sqrt{2} \sin\left (\theta + \frac\pi4 \right)}\\ \text{and }\int \csc x \,dx = -\ln |\csc x + \cot x|+C \]You're right about the final answer but I think the intended approach was to use the quotient rule to bash that the derivative was equal to 0, before justifying it by Euler's formula.

Also, I don't think \(e^{ix}\) is 'defined' as \(\cos x + i \sin x\). It is something that can be proven via Taylor series
________________________________________

Anyway won't steal that integral (although hahaha, \(n\)-th moment of a normal distribution). But I just wanted to put up some C code for problem set 2 because I thought it was a fun programming exercise.
Code: (22dec2018question.c) [Select]
// Finds and prints the first matrix that works
// If none exists, mention that none exists
// Designed specifically for matrices over Z_2

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Size of matrix - can be changed
#define SIZE 4

typedef struct matrixRep *Matrix;
typedef struct matrixRep {
  int mm[SIZE][SIZE];
} _matrix;

Matrix newMatrix();
void destroyMatrix(Matrix m);
unsigned long long maxNumIterations(unsigned int size);
void matrixInit(Matrix m, int i);
void idInit(Matrix id);
void kkInit(Matrix k);
bool matrixCmp(Matrix a, Matrix b);
Matrix matrixAdd(Matrix a, Matrix b);
Matrix matrixMult(Matrix a, Matrix b);
Matrix matrixCube(Matrix m);
Matrix matrixFourth(Matrix m);
void printMatrix(Matrix m);

int main() {

  Matrix m, mcubed, mfourth, msum;
  Matrix id, kk;
  unsigned long long n = maxNumIterations(SIZE);
  bool found = false;

  id = newMatrix();
  idInit(id);
  kk = newMatrix();
  kkInit(kk);

  m = newMatrix();

  for (unsigned long long i = 0; i < n; i++) {
    if (found) break;
    matrixInit(m, i);
    mcubed = matrixCube(m);
    msum = matrixAdd(mcubed, m);
    mfourth = matrixFourth(m);

    if (matrixCmp(msum, kk) && matrixCmp(mfourth, id)) found = true;
    destroyMatrix(mcubed);
    destroyMatrix(msum);
    destroyMatrix(mfourth);
  }

  if (found) {
    printf("Found matrix:\n");
    printMatrix(m);
    printf("\n");
  } else {
    printf("Not found.\n");
  }

  destroyMatrix(id);
  destroyMatrix(kk);
  destroyMatrix(m);
  return 0;
}

// newMatrix: allocates memory for a new matrix
Matrix newMatrix() {
  Matrix new = calloc(1, sizeof(struct matrixRep));
  return new;
}

// destroyMatrix: frees up memory associated with a matrix
void destroyMatrix(Matrix m) {
  free(m);
}

// maxNumIterations: computes 2^(size^2) - the max amount of times
// the loop in the main function can run for
unsigned long long maxNumIterations(unsigned int size) {
  unsigned long long n = 1;
  unsigned long int sizeSq = size*size;
  for (unsigned long int i = 0; i < sizeSq; i++) {
    n <<= 1;
  }
  return n;
}

// matrixInit: sets up m for the current value of i in the main function's loop
void matrixInit(Matrix m, int n) {
  int mask = 1;
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      m->mm[i][j] = n & mask;
      mask <<= 1;
      m->mm[i][j] = (m->mm[i][j] == 0) ? 0 : 1;
    }
  }
}

// idInit: sets up the identity matrix
void idInit(Matrix id) {
  int posOfOne = 0;
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      if (j == posOfOne) id->mm[i][j] = 1;
      else id->mm[i][j] = 0;
    }
    posOfOne++;
  }
}

// kkInit: sets up the matrix of 1's
void kkInit(Matrix k) {
  for (int i = 0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++)
      k->mm[i][j] = 1;
}

// matrixCmp: checks if two
bool matrixCmp(Matrix a, Matrix b) {
  bool same = true;
  for (int i = 0; i < SIZE; i++) {
    if (!same) break;
    for (int j = 0; j < SIZE; j++) {
      if (a->mm[i][j] != b->mm[i][j]) {
        same = false;
        break;
      }
    }
  }
  return same;
}

// matrixAdd: computes the sum of two matrices
Matrix matrixAdd(Matrix a, Matrix b) {
  Matrix sum = newMatrix();
  for (int i = 0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++)
      sum->mm[i][j] = a->mm[i][j] ^ b->mm[i][j];
  return sum;
}

// matrixMult: computes the product of two matrices
Matrix matrixMult(Matrix a, Matrix b) {
  Matrix prod = newMatrix();
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      for (int k = 0; k < SIZE; k++)
        prod->mm[i][j] += a->mm[i][k] * b->mm[k][j];
       
      prod->mm[i][j] &= 1;
    }
  }
  return prod;
}

// matrixCube: computes the cube of a matrix
Matrix matrixCube(Matrix m) {
  Matrix msq = matrixMult(m, m);
  Matrix mcb = matrixMult(msq, m);
  destroyMatrix(msq);
  return mcb;
}

// matrixFourth: computs the fourth power of a matrix
Matrix matrixFourth(Matrix m) {
  Matrix msq = matrixMult(m, m);
  Matrix mfr = matrixMult(msq, msq);
  destroyMatrix(msq);
  return mfr;
}

// printMatrix: displays a matrix to stdout
void printMatrix(Matrix m) {
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++)
      printf("%d ", m->mm[i][j]);
    printf("\n");
  }
}
...but then soon enough I realised how shit this code was because it's an \( \mathcal{O}(2^{n^2}) \) algorithm (slow when \(n=5\)) :'( wonder if improvements can be made to it. I know that right now it's checking matrices which aren't of full rank which is redundant. Anyone got suggestions on some easy math that I can probably convert into code to make it faster?
I'm not convinced your method is easier. You needed to recognise that compound angle formula, and even at the end, you have to expand both resulting compound angle trig functions back, and that's a bit of algebra too. Initially, I did a trig sub, saw the sec cubed, and thought it was needlessly complicated because of the high power :P

The intent with my question was as follows.
1. Show that the derivative vanishes.
2. Note that zero derivative means function is constant.
3. Find the value of the constant by plugging in x = 0 to get \(\frac{e^{ix}}{\cos(x) + i\sin(x)} = 1\)

Now it's a matter of semantics. If you define the exponential function by a Taylor series, which is probably the sensible thing to do, Taylor series are initially only defined for real arguments; you have to assume that the Taylor series also holds for complex arguments, which is a priori not a given because we previously have no understanding of the meaning of e^complex number. Once you assume this definition for complex arguments, Euler's identity follows immediately.
2012
Mathematical Methods (50) Chinese SL (45~52)

2013
English Language (50) Chemistry (50) Specialist Mathematics (49~54.9) Physics (49) UMEP Physics (96%) ATAR 99.95

2014-2016: University of Melbourne, Bachelor of Science, Diploma in Mathematical Sciences (Applied Maths)

2017-2018: Master of Science (Applied Mathematics)

2019-: ???

Accepting students for  VCE tutoring in Maths Methods, Specialist Maths and Physics! PM for more details

RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8451
  • "All models are wrong, but some are useful."
  • Respect: +2313
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #24 on: December 25, 2018, 11:19:02 pm »
0
I'm not convinced your method is easier. You needed to recognise that compound angle formula, and even at the end, you have to expand both resulting compound angle trig functions back, and that's a bit of algebra too. Initially, I did a trig sub, saw the sec cubed, and thought it was needlessly complicated because of the high power :P
See, maybe I'm wrong because of the HSC vs VCE context, but the auxiliary transform is actually a part of the HSC MX1 syllabus and basically a one-liner :P it's a buzz-kill for those problems here to those who've integrated for a bit too long in their life


lzxnl

  • Victorian
  • ATAR Notes Legend
  • *******
  • Posts: 3430
  • Respect: +207
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #25 on: December 25, 2018, 11:23:01 pm »
0
See, maybe I'm wrong because of the HSC vs VCE context, but the auxiliary transform is actually a part of the HSC MX1 syllabus and basically a one-liner :P it's a buzz-kill for those problems here to those who've integrated for a bit too long in their life



Fair enough. That was never actually covered in VCE or at university (afaik), so while I learned it in high school (from a HSC textbook ironically), most of my classmates wouldn't have. It really is the same as finding the argument of a complex number though. I didn't even know it was called that tbh.
2012
Mathematical Methods (50) Chinese SL (45~52)

2013
English Language (50) Chemistry (50) Specialist Mathematics (49~54.9) Physics (49) UMEP Physics (96%) ATAR 99.95

2014-2016: University of Melbourne, Bachelor of Science, Diploma in Mathematical Sciences (Applied Maths)

2017-2018: Master of Science (Applied Mathematics)

2019-: ???

Accepting students for  VCE tutoring in Maths Methods, Specialist Maths and Physics! PM for more details

AlphaZero

  • MOTM: DEC 18
  • Forum Obsessive
  • ***
  • Posts: 308
  • \[F(s)=\int_0^\infty \!f(t)e^{-st}\,\text{d}t\]
  • Respect: +128
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #26 on: December 26, 2018, 12:15:21 am »
+1
\[ \int \frac{(x-1)\sqrt{x^4+2x^3 +4x^2+2x+1}}{x^2(x+1)}dx \]
Ewwwwwwwwwwww. That's probably the worst I've seen :P  (what a great christmas gift lol)

I'm not going to write out the full working for the Gaussian integral stuff because I'm so tired, but I'll write some brief notes. Perhaps someone can finish it off :D

_______________________________________________________________

Define \[I_n(\alpha)=\int_{-\infty}^\infty x^ne^{-\alpha x^2}dx,\quad\alpha>0,\ n\in\mathbb{N}.\] We are given that \(I_0(1)=\sqrt{\pi}\) and so by scaling \(x\) appropriately, we find that \[I_0(\alpha)=\sqrt{\frac{\pi}{\alpha}}.\]Now, note that if \(n\) is odd, then the integrand is an odd function, and so \[I_{2k-1}(\alpha)\equiv0,\quad k\in\mathbb{N}.\] Therefore, we consider even \(n\).

Making use of the fact that \[I_n(\alpha)=-\frac{\partial}{\partial\alpha}\big[I_{n-2}(\alpha)\big],\]we find that for even \(n\), \[I_n(\alpha)=\frac{(n-1)!!}{(2\alpha)^{n/2}}\sqrt{\frac{\pi}{\alpha}}.\] Substituting in \(\alpha=1\) gives us the final result of \[\int_{-\infty}^\infty x^ne^{-x^2}dx=\begin{cases}0 & \text{odd }n\\ \dfrac{(n-1)!!}{2^{n/2}}\sqrt{\pi} & \text{even }n\end{cases},\quad n\in\mathbb{N}.\]

_______________________________________________________________

But I just wanted to put up some C code for problem set 2 because I thought it was a fun programming exercise.
Code: (22dec2018question.c) [Select]
// Finds and prints the first matrix that works
// If none exists, mention that none exists
// Designed specifically for matrices over Z_2

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Size of matrix - can be changed
#define SIZE 4

typedef struct matrixRep *Matrix;
typedef struct matrixRep {
  int mm[SIZE][SIZE];
} _matrix;

Matrix newMatrix();
void destroyMatrix(Matrix m);
unsigned long long maxNumIterations(unsigned int size);
void matrixInit(Matrix m, int i);
void idInit(Matrix id);
void kkInit(Matrix k);
bool matrixCmp(Matrix a, Matrix b);
Matrix matrixAdd(Matrix a, Matrix b);
Matrix matrixMult(Matrix a, Matrix b);
Matrix matrixCube(Matrix m);
Matrix matrixFourth(Matrix m);
void printMatrix(Matrix m);

int main() {

  Matrix m, mcubed, mfourth, msum;
  Matrix id, kk;
  unsigned long long n = maxNumIterations(SIZE);
  bool found = false;

  id = newMatrix();
  idInit(id);
  kk = newMatrix();
  kkInit(kk);

  m = newMatrix();

  for (unsigned long long i = 0; i < n; i++) {
    if (found) break;
    matrixInit(m, i);
    mcubed = matrixCube(m);
    msum = matrixAdd(mcubed, m);
    mfourth = matrixFourth(m);

    if (matrixCmp(msum, kk) && matrixCmp(mfourth, id)) found = true;
    destroyMatrix(mcubed);
    destroyMatrix(msum);
    destroyMatrix(mfourth);
  }

  if (found) {
    printf("Found matrix:\n");
    printMatrix(m);
    printf("\n");
  } else {
    printf("Not found.\n");
  }

  destroyMatrix(id);
  destroyMatrix(kk);
  destroyMatrix(m);
  return 0;
}

// newMatrix: allocates memory for a new matrix
Matrix newMatrix() {
  Matrix new = calloc(1, sizeof(struct matrixRep));
  return new;
}

// destroyMatrix: frees up memory associated with a matrix
void destroyMatrix(Matrix m) {
  free(m);
}

// maxNumIterations: computes 2^(size^2) - the max amount of times
// the loop in the main function can run for
unsigned long long maxNumIterations(unsigned int size) {
  unsigned long long n = 1;
  unsigned long int sizeSq = size*size;
  for (unsigned long int i = 0; i < sizeSq; i++) {
    n <<= 1;
  }
  return n;
}

// matrixInit: sets up m for the current value of i in the main function's loop
void matrixInit(Matrix m, int n) {
  int mask = 1;
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      m->mm[i][j] = n & mask;
      mask <<= 1;
      m->mm[i][j] = (m->mm[i][j] == 0) ? 0 : 1;
    }
  }
}

// idInit: sets up the identity matrix
void idInit(Matrix id) {
  int posOfOne = 0;
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      if (j == posOfOne) id->mm[i][j] = 1;
      else id->mm[i][j] = 0;
    }
    posOfOne++;
  }
}

// kkInit: sets up the matrix of 1's
void kkInit(Matrix k) {
  for (int i = 0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++)
      k->mm[i][j] = 1;
}

// matrixCmp: checks if two
bool matrixCmp(Matrix a, Matrix b) {
  bool same = true;
  for (int i = 0; i < SIZE; i++) {
    if (!same) break;
    for (int j = 0; j < SIZE; j++) {
      if (a->mm[i][j] != b->mm[i][j]) {
        same = false;
        break;
      }
    }
  }
  return same;
}

// matrixAdd: computes the sum of two matrices
Matrix matrixAdd(Matrix a, Matrix b) {
  Matrix sum = newMatrix();
  for (int i = 0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++)
      sum->mm[i][j] = a->mm[i][j] ^ b->mm[i][j];
  return sum;
}

// matrixMult: computes the product of two matrices
Matrix matrixMult(Matrix a, Matrix b) {
  Matrix prod = newMatrix();
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      for (int k = 0; k < SIZE; k++)
        prod->mm[i][j] += a->mm[i][k] * b->mm[k][j];
       
      prod->mm[i][j] &= 1;
    }
  }
  return prod;
}

// matrixCube: computes the cube of a matrix
Matrix matrixCube(Matrix m) {
  Matrix msq = matrixMult(m, m);
  Matrix mcb = matrixMult(msq, m);
  destroyMatrix(msq);
  return mcb;
}

// matrixFourth: computs the fourth power of a matrix
Matrix matrixFourth(Matrix m) {
  Matrix msq = matrixMult(m, m);
  Matrix mfr = matrixMult(msq, msq);
  destroyMatrix(msq);
  return mfr;
}

// printMatrix: displays a matrix to stdout
void printMatrix(Matrix m) {
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++)
      printf("%d ", m->mm[i][j]);
    printf("\n");
  }
}
...but then soon enough I realised how shit this code was because it's an \( \mathcal{O}(2^{n^2}) \) algorithm (slow when \(n=5\)) :'( wonder if improvements can be made to it. I know that right now it's checking matrices which aren't of full rank which is redundant. Anyone got suggestions on some easy math that I can probably convert into code to make it faster?

Yeah, it just grows super really really really fast lol. When I got this problem I did have a think about how to search efficiently, but failed horribly because I'm a terrible programmer. Here were my thoughts nonetheless:

First, take your \(n\times n\) matrix for even \(n\) and form a binary number by taking each row of the matrix and placing them next to each other. That is, \[M=\begin{bmatrix}m_{11} & \dots & m_{1n}\\ \vdots & \ddots & \vdots\\ m_{n1} & \dots & m_{nn} \end{bmatrix}\ \ \text{becomes}\ \ D=\big[m_{11}...m_{1n}\dots m_{n1}...m_{nn}\big].\] Now, there's no point checking matrices that have zero rows or columns, so we can check the digits of \(D\) in blocks of \(n\) for any \(1\)'s. Clearly, if we start checking from \(M=0\) (corresponding to \(D=0\)), then we're going to be checking many matrices with zero rows, so, we should start checking from the lowest number \(D\) that contains at least a \(1\) in every row and column. That number would be formed from matrix with \(1\)'s only on the minor diagonal (with \(0\)'s everywhere else). Then, just start adding \(1\) to \(D\) and if the corresponding matrix contains no zero rows/columns, then check if \(M=M^3\) and \(M^4=I\) simultaneously.

Then again, I'm not sure this would have a great affect though :/
« Last Edit: December 26, 2018, 12:18:49 am by dantraicos »
2015\(-\)2017:  VCE
2018\(-\)2021:  Bachelor of Biomedicine and Concurrent Diploma in Mathematical Sciences, University of Melbourne


RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8451
  • "All models are wrong, but some are useful."
  • Respect: +2313
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #27 on: December 26, 2018, 06:09:37 pm »
+1
Ewwwwwwwwwwww. That's probably the worst I've seen :P  (what a great christmas gift lol)
Be careful what you wish for ;)
\[ \int \sqrt[4]{\tan x}\,dx \]
(That's not the next question and I ain't touching it either, but you can if you really want to.)

But yeah I give up on that code. After thinking about it again, if I still need to "check" the obvious before computing the matrix powers (e.g. no 0 in each row and column) it's still gonna be an inefficient algorithm.
______________________________________________________

NEXT QUESTION: Ok I'm bored of integrals for now. For the high schoolers:
\[ \text{Find the implied domain of}\\ f(x) = \ln (x^2-4x) \arcsin (x^2-4x-3).\]
For the university students:
\[ \text{Let }X_1, \dots, X_n\text{ be an i.i.d. sequence of }\operatorname{Ber}(p)\text{ random variables.}\\ \text{Prove that }S := \sum_{i=1}^n X_i \sim \operatorname{Bin}(n,p). \]

AlphaZero

  • MOTM: DEC 18
  • Forum Obsessive
  • ***
  • Posts: 308
  • \[F(s)=\int_0^\infty \!f(t)e^{-st}\,\text{d}t\]
  • Respect: +128
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #28 on: December 26, 2018, 07:52:49 pm »
+1
Be careful what you wish for ;)
\[ \int \sqrt[4]{\tan x}\,dx \]
...



;D lol, there's no way I'm attempting that.

As for the probability question, I'm not too sure how to argue it succinctly. I'm a jaffy, so I haven't taken (and probably won't be able to take) any probability or statistics subjects in Uni. Nonetheless, I'll give the question a go. Probably gonna need some correcting though. I'm just doing a combinatorics argument.
_______________________________________________________________

My dodgy proof
\(S=X_1+\dots+X_n\) counts the number of Bernoulli variables that are equal to \(1\), so \(S\in\left\{0,\dots,n\right\}\). We start by noticing that if we wish to calculate \(\Pr(S=k)\), where \(k\in\left\{0,\dots,n\right\}\), there are \(\binom{n}{k}\) possible cases to consider. Let \(A\) be one of those specific cases. Since \(X_1,\dots,X_n\) are independent, \[\Pr(A)=p^k(1-p)^{n-k}\] because there are \(k\) Bernoulli variables equal to \(1\) with probability \(p\) and \(n-k\) variables equal to \(0\) with probability \(1-p\). Hence, \[\Pr(S=k)=\binom{n}{k}p^k(1-p)^{n-k},\] which is the probability mass function of the binomial distribution. Thus, \(S\sim\text{Bi}(n,p)\).
_______________________________________________________________

I'm having trouble clearly describing what I mean by the event \(A\) being a "specific case". Help?
2015\(-\)2017:  VCE
2018\(-\)2021:  Bachelor of Biomedicine and Concurrent Diploma in Mathematical Sciences, University of Melbourne


RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8451
  • "All models are wrong, but some are useful."
  • Respect: +2313
Re: "Challenge" Math Qs - Can You Figure It Out?
« Reply #29 on: December 26, 2018, 08:02:25 pm »
+2
(Image removed from quote.)

;D lol, there's no way I'm attempting that.

As for the probability question, I'm not too sure how to argue it succinctly. I'm a jaffy, so I haven't taken (and probably won't be able to take) any probability or statistics subjects in Uni. Nonetheless, I'll give the question a go. Probably gonna need some correcting though. I'm just doing a combinatorics argument.
_______________________________________________________________

My dodgy proof
\(S=X_1+\dots+X_n\) counts the number of Bernoulli variables that are equal to \(1\), so \(S\in\left\{0,\dots,n\right\}\). We start by noticing that if we wish to calculate \(\Pr(S=k)\), where \(k\in\left\{0,\dots,n\right\}\), there are \(\binom{n}{k}\) possible cases to consider. Let \(A\) be one of those specific cases. Since \(X_1,\dots,X_n\) are independent, \[\Pr(A)=p^k(1-p)^{n-k}\] because there are \(k\) Bernoulli variables equal to \(1\) with probability \(p\) and \(n-k\) variables equal to \(0\) with probability \(1-p\). Hence, \[\Pr(S=k)=\binom{n}{k}p^k(1-p)^{n-k},\] which is the probability mass function of the binomial distribution. Thus, \(S\sim\text{Bi}(n,p)\).
_______________________________________________________________

I'm having trouble clearly describing what I mean by the event \(A\) being a "specific case". Help?
(Yeah. Told you to be careful :D)
(Background context - basically \( \int \sqrt{\tan x}\,dx\) is a very popular painful integral. It's so popular that people have went on to discovering more efficient ways of solving it, but they lack a lot less intuition than the original approach. But I didn't want to put that one up because that one is either barely easier or 'on par' with the painful one above. So I just decided to revamp up the power a bit instead 8))

I mean, that proof is fair enough at the first year level I think :P it's basically using enumerative combinatorics here instead. To make \(A\) rigourous, you could comment on something along the lines of for a fixed \(k\), let \(A\) be a particular configuration (or sequence) of the \(n\) Ber(p)'s, and then provide an example - e.g. if \(n=2\) and \(k=1\), a particular configuration could be \(X_1 = 0\) and \(X_2 = 1\)). But if you wanna do a bit of reading, look up "sums of independent random variables" and "convolutions" :)