Intereting Posts

How to prove this conjecture $x_{n}(n\ge 4)$ can't be an integer.
Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.
Finitely generated projective module
Is there a closed-form equation for $n!$? If not, why not?
Constructing a subset not in $\mathcal{B}(\mathbb{R})$ explicitly
Is $n! + 1$ often a prime?
Showing that $(A_{ij})=\left(\frac1{1+x_i+x_j}\right)$ is positive semidefinite
Proving a function is onto and one to one
Laplace's Equation in Spherical Coordinates
Shortlist of problems in linear algebra
Bijection from finite (closed) segment of real line to whole real line
Examples of a quotient map not closed and quotient space not Hausdorff
Integral $\int_{-1}^{1} \frac{1}{x}\sqrt{\frac{1+x}{1-x}} \log \left( \frac{(r-1)x^{2} + sx + 1}{(r-1)x^{2} – sx + 1} \right) \, \mathrm dx$
Question about Riemann integral and total variation
How many ordinals can we cram into $\mathbb{R}_+$, respecting order?

‘6 professors begin courses of lectures on Monday, Tuesday, Wednesday, Thursday, Friday and Saturday, and announce their intentions of lecturing at intervals of 2,3,4,1,6,5 days respectively. The regulations of the University forbid Sunday lectures (so that Sunday lecture must be omitted). When first will all six professors find themselves compelled to omit a lecture?’

This is the question I’m struggling with, I believe it can be solved using the Chinese Remainder theorem, but am really going no where with it. Any progress I make I will post, but I have not yet done anything worth adding to this. Any help would be greatly appreciated!

EDIT: Ok, so I have reduced the problem down to finding the minimum positive value such that, d=11(mod 12), 6(mod 5), 0(mod 7).

- Proof of Fermat's little theorem using congruence modulo $p$
- Find the least number b for divisibility
- Any digit written $6k$ times forms a number divisible by $13$
- What is a negative number?
- Bijection between the set of classes of positive definite quadratic forms and the set of classes of quadratic numbers in the upper half plane
- Prove the _Chinese Remainder Theorem_

- The ring of integers of $\mathbf{Q}$
- Find general solution for the equation $1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) $
- How can I tell if a number in base 5 is divisible by 3?
- Probable prime test for specific class of $N=k \cdot b^n-1$
- $2^{4n+1} \equiv 1 \pmod{8n+7}$, this has been bugging me
- Most even numbers is a sum $a+b+c+d$ where $a^2+b^2+c^2=d^2$
- Prove a property of the divisor function
- A number-theory question on the deficiency function $2x - \sigma(x)$
- If R and S are rings then $R \times S$ is never a field
- Show that $a^3+b^5=7^{7^{7^7}}$ has no solutions with $a,b\in \mathbb Z.$

Let the number $1$ label the first Monday. Then the professors’ schedules mean that their lecturing days satisfy the congruences below:

$$\begin{align*}

d_1&\equiv1\pmod2,\\

d_2&\equiv2\pmod3,\\

d_3&\equiv3\pmod4,\\

d_4&\equiv4\pmod1,\\

d_5&\equiv5\pmod6,\\

d_6&\equiv6\pmod5.

\end{align*}$$

In order to find the Sunday in which the last professor is forced to refrain lecturing, we will take the minimum positive solution to each system $d_i=i\pmod\circ$, $d_i=0\pmod 7$ (so that professor $i$ should be lecturing by the schedule but can’t because it’s Sunday) and find the maximum among them. I just checked multiples of $7$ mentally until I found solutions to each. The solutions are $7,14,7,7,35,21$, so by $35$ days every professor will have omitted a lecture at some point.

On the other hand, if you’re looking for the first Sunday in which all six professors *simultaneously* omit a lecture, then we must solve all of the above congruences for a single $d$ at the same time, with the additional congruence of $0\bmod7$. Note that the modulo $1$ congruence is trivially satisfied and can be thrown out, the modulo $2$ congruence gets subsumed into the modulo $4$ congruence and the modulo $3$ congruence gets subsumed into the modulo $6$ congruence, so reducing gives $d\equiv$

$$\begin{align*}3&\bmod4,\\5&\bmod6,\\1&\bmod5,\\0&\bmod7.\end{align*}$$

The first two can be solved into $11\bmod12$, leaving the remaining modulus’s coprime so that you can use the general construction method from Wikipedia’s article on the Chinese remainder theorem in order to solve this system. The computation is

$$11\cdot35\cdot(35_{12}^{-1})+1\cdot84\cdot(84_5^{-1})=4571\equiv371\bmod420$$

hence our solution is day 371. (But what crazy classes take over a year nonstop?)

Luckily seven is a prime, so all the professors will need to skip every seventh lecture. Let the coming Sunday be number zero, let $i$ be the Sunday $i$ weeks into the future, and let $N$ denote the number of a Sunday, on which they all need to skip a class. Prof. Monday will need to skip this Sunday and every second Sunday thereafter, so $N\equiv 0 \pmod 2$. Prof. Tuesday would first like to preach on Sunday $\#1$ exactly $12=4\cdot3$ days after his course commences, so $N\equiv 1\pmod 3$. Prof. Wednesday will miss an opportunity on the coming Sunday as well, so $N\equiv 0\pmod 4$. The eager beaver prof. Thursday will be irritated on every single Sunday, and can thus be left out of the reckoning. The lazy professor Friday will first be annoyed (or relieved?) on Sunday $\#4$ (four full weeks plus two days from Fri to Sun = $30=5\cdot 6$ days), so $N=4\pmod 6$. Professor Saturday’s first miss is $15=3\cdot5$ days after his course has started on Sunday $\#2$, so $N\equiv 2\pmod 5.$

BUT I’m not going to solve this for you. Check the above, and **then** use the CRT to find the possible values of $N$. For extra credit you should observe that it was not a priori clear that the six professors would all miss a lecture on the same Sunday. A number of miraculous fits occurred, so I give some due credit to whoever composed this problem.

**HINT** $\ $ It’s easy since $\rm\ n\equiv -1\ $ for almost all moduli. Therefore, for example

$$\rm\qquad\ \ n \equiv -1\ \ (mod\ i,\:j,\:k)\ \ \Rightarrow\ \ n\equiv -1\ \ (mod\ \ lcm(i,j,k)) $$

Said in more elementary terms $\rm\ \ i,\:j,\:k\ |\ n+1\ \ \Rightarrow\ lcm(i,j,k)\ |\ n+1$

So you can replace most of the Chinese Remainder calculation by much simpler $\rm\:lcm\:$ calculations. One can perform the same optimization in any CRT problem where the values are the same for more than one modulus, i.e. where the solution has “constant” value, e.g. $\rm\:n\:$ is constant $\rm\equiv -1\:$ for all three moduli above. For another example of analogous CRT optimization see this answer, where the above optimization simplifies a three-page calculation to a trivial three-line calculation.

If you want to use the Chinese Remainder Theorem, you must number the days starting with the first lecture on Monday; then to find the Sunday when they all omit a lecture, you find the number of the day that it lands on. Now you can use arithmetic.

The given conditions on 1) the days that the professors start and 2) the intervals between their lectures show that the day numbers on which each professor lectures will satisfy a congruence condition. Sundays satisfy another congruence condition. You need the smallest positive solution of all of these congruences, and one way to solve them is to use the constructive proof of the CRT. However, I think a faster and simpler solution will combine some trial-and-error with the statement of the CRT to show that the solution you found is the smallest one.

The answer can be further simplified : 371 (mod 420) = 371 (mod 420 ÷2) = 161 (mod 210). On the (161 ÷7=) 23rd Sunday when all 6 profs are compelled to omit a lecture.

Remark:

if keep x = 1 (mod 2) and x= 2 (mod 3) instead of the equivalent x = 3 (mod 4) = 3 (mod 4÷2) =1 (mod 2), x = 5 (mod 6) = 5 (mod 6 ÷2) = 5 (mod 3) = 2 (mod 3), resp., then you would get directly : x = 161 (mod 210).

See: https://tomcircle.wordpress.com/2017/01/05/crt-problem/

- Prove that $\sum\limits_{n=1}^{\infty} \frac{n}{3^n} = \frac{3}{4}$
- $P(x)\in\mathbb Z$ iff $Q(x)\in\mathbb Z$
- Asymptotics of a summation over real valued functions
- Rounding Percentages
- Prove that $\lfloor\lfloor x/2 \rfloor / 2 \rfloor = \lfloor x/4 \rfloor$
- Steps to solve this system of equations: $\sqrt{x}+y=7$, $\sqrt{y}+x=11$
- Find all positive integers $n$ such that $\phi(n)=6$.
- composition of two uniformly continuous functions.
- Maximal ideals and the projective Nullstellensatz
- Associativity of product measures
- Prime $p$ with $p^2+8$ prime
- Got stuck in proving monotonic increasing of a recurrence sequence
- Integrate $x^ {1/2}e^{-x}$ using integration by parts
- Induction proof of $\sum_{k=1}^{n} \binom n k = 2^n -1 $
- Why isn't there interest in nontrivial, nondiscrete topologies on finite groups?