Math Challenge - December 2018

In summary, the challenges for this special month of December will be posted daily from 12/1 to 12/25, ranging from relatively easy logical and numerical problems to little proofs. There are certain rules for participation, including the requirement of a full derivation or proof for solutions to count. There are also recommended problems from a previous forum thread, and some specific problems listed for consideration. These include problems involving sequences, logic puzzles, matrices, functions, areas and volumes, polynomials, and number algorithms.
  • #1
fresh_42
Mentor
Insights Author
2023 Award
18,994
23,950
It's December and we like to do a Special this month. The challenges will be posted like an Advent Calendar. We will add a new problem each day, from 12/1 to 12/25. They vary between relatively easy logical and numerical problems, calculations, to little proofs which hopefully add some nice-to-know lemmata to your toolbox. We hope you will have fun with this format. In case open questions are too difficult and a new one isn't opened yet, we recommend https://www.physicsforums.com/threads/math-challenge-november-2018.960003/#post-6087946 where still some easy ones can be found.

Rules:

a) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
b) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
c) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
d) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

Hints: on demand

1. (solved by @julian ) Let ##(a_n)_{n \in\mathbb{N}}\subseteq \mathbb{R}^+## be a sequence of positive real numbers and ##A=\sum_{n=1}^\infty a_n\,.## Prove the following statements:
  1. (Kummer) If there is a sequence ##(b_n)_{n \in \mathbb{N}}\subseteq \mathbb{R}^+## of positive real numbers, such that there is an index ##N \in\mathbb{N}## for which ##b_{n-1}\cdot \dfrac{a_{n-1}}{a_n} - b_n \geq C## for a constant ##C>0## and all ##n>N##, then ##A## converges.
  2. (Kummer) If there is a sequence ##(b_n)_{n \in \mathbb{N}}\subseteq \mathbb{R}^+## of positive real numbers, such that the series ##\sum_{n=1}^{\infty}\dfrac{1}{b_n}## diverges, and there is an index ##N\in \mathbb{N}## such that ##b_{n-1}\cdot \dfrac{a_{n-1}}{a_n}-b_n \leq 0## for all ##n>N##, then ##A## diverges.
  3. (Bertrand) We define the sequence of real numbers by $$b_n := \left(n \cdot \left( \dfrac{a_n}{a_{n+1}}-1 \right)-1 \right)\log (n)$$ and ##B :=\lim_{n \to \infty}b_n \in \overline{\mathbb{R}}=\mathbb{R}\cup \{\,\pm \infty\,\}\,.##
    Then ##A## converges if ##B>1## and diverges if ##B<1\,.##
2. a.) (solved by @alind31 ) Here is a logic puzzle especially for our younger members:

Two mathematicians meet by chance on a plane: "Didn't you have three sons?" asks one, "how old are they?" - "The product of years is 36," is the answer, "and the sum of years is exactly today's date." "Hmm, that's not enough for me," says the colleague. "Oh, right," says the second mathematician, "I forgot to mention that my eldest son has a dog."
How old are the three sons?

All others are recommended to [/URL]https://www.physicsforums.com/threads/math-challenge-november-2018.960003/. Especially the problems 7,8,9,19,20 should be manageable, and even 15,16 look more complicated as they actually are. If you want a new problem despite of these:

2. b.)
(solved by @jbstemp) The unitary matrices build a manifold, the Lie group ##SU(n)##. Calculate its tangent space at the neutral element of the group.

3. Find functions ##y(t)## and ##z(t)## which locally solve the equations
$$
\begin{cases}
e^t + \tan y(t) &= 1\\
t^2 + z(t)^3+z(t) &=0
\end{cases}
$$
in a neighborhood of ##t=0## and investigate their behavior with respect to monotony (where defined). It is sufficient to determine the functions up to a differential equation. It's a mathematical problem, so existence will do.

4. (solved by @DeathByKugelBlitz ) Find a ten digits integer with all ten digits, such that the first ##n## digits (##1\leq n \leq 10##) are divisible by ##n##. The integer should thus contain all ##10## different symbols ##0,1,2,3,4,5,6,7,8,9##.

5. Is there always a position on a floor (continuous, no holes, steps etc.) for a rectangular table with four equal legs, such that the table does not wiggle?

6. (solved by @SSequence ) Show that ##(0,1) \subset \mathbb{R}## cannot be written as a countable disjoint union of closed intervals.

7. Areas and Volumes
7.a.) (solved by @Delta2 ) Show that the paraboloid
$$P=\{\,(x,y,z)^\tau\in \mathbb{R}^3\,|\,x^2+y^2=z\, , \,x,y\in [-1,1]\,\} \subseteq \mathbb{R}^3$$
and the hyperboloid
$$H=\{\,(x,y,z)^\tau\in \mathbb{R}^3\,|\,x^2-y^2=z\, , \,x,y\in [-1,1]\,\} \subseteq \mathbb{R}^3$$
have equal areas.

7.b.) (unsloved) Bring ##M =\{\,(x,y,z)^\tau\in \mathbb{R}^3\,|\,x^2\leq y^4\leq z^8\leq 1\,\}## into a normal form and calculate its volume.

8. (solved by @Young physicist ) The table cards at a rotatable round table with 12 seats are set up for expected 12 guests. However, the persons ignore the cards and randomly distribute themselves to the seats.
Is it always possible with a single turn of the table to make sure that at least two people sit in front of their correct table cards?

9. Let ##p(x)=x^n+a_{n-1}x^{n-1}+\ldots +a_1x+a_0 \in \mathbb{R}[x]## be a polynomial where all roots are negative. Prove that $$\int_{1}^{\infty}\dfrac{1}{p(x)}\,dx$$ converges absolutely if and only if ##n>1\,.##

10. (solved by @Young physicist ) Tom bets John that he can do the following: John will recite ##99## different numbers in the range ##1 \ldots 100## (i.e. positive integers) in a random order and he will be able to find and name the only number in that range that John will have missed. Tom will do it without taking any notes. What is the best algorithmic strategy to use in order to accomplish this? Give the relevant math.

11. Let ##\emptyset \neq U \subseteq \mathbb{R}^+## be an open set, and ##x_0\in U\,.## We define the quotient logarithm of a function ##f\; : \;U \longrightarrow \mathbb{R}^+## at ##x=x_0## by
$$
f\,^-(x_0) := \lim_{x \to x_0} \dfrac{\log f(x)-\log f(x_0)}{\log x-\log x_0}
$$
Solve the 'differential equation' ##f^-=f\,.##

12. (solved by @lpetrich ) Let [itex]x_0=0,x_1=1[/itex], and [itex]x_{n+1}=n(x_n+x_{n-1})[/itex] for [itex]n\geq 1[/itex]. Find [itex]\lim_{n\to\infty}\dfrac{x_n}{n!} \quad[/itex].

13. (solved by @lpetrich ) Let ##p>q## be prime numbers such that ##p \not\equiv 1 \operatorname{mod}q##.
Prove that each group with ##pq## elements is cyclic.

14. (solved by @Young physicist ) If we multiply our five digits number by four, we will get the same number in reverse order. What's the number?

15. (solved by @Math_QED ) Let ##\mathcal{B}## be a Boolean ring with ##1##, i.e. each element of ##\mathcal{B}## is idempotent. Show that each prime ideal is maximal.

16. (solved by @lpetrich ) On a state fair is a booth where you can shoot at a square. You get ##1## point for each hit and ##2## points if you hit closer to the center than to the boundary. How big is your chance to get the extra point?

17. Let ##F_r = x^{r}\sin rA + y^{r}\sin rB + z^{r}\sin rC##, where ##x, y, z, A, B, C## are real numbers and ##A + B + C## is an integer multiple of ##\pi##. Prove that if ##F_1 = F_2 = 0## then ##F_r = 0## for all positive integers ##r##.

18. (solved by @lpetrich ) Find all three digits numbers ##x= [abc] = 100a+10b+c## such that all powers ##x^n\; , \;n\in \mathbb{N}## end on ##[...abc]##, too.

19. (solved by @lpetrich ) The product of two of the four roots of the equation ##x^4 - 18x^3 + kx^2 + 200x - 1984 = 0## is ##-32##. Find ##k##.

20. Find the maximum number of different arithmetic progressions with three terms that can be chosen from a sequence of ##n## real numbers ##a_1 \lt a_2 \lt\dots\lt a_n##.

21. (solved by @lpetrich ) Calculate curvature and torsion of the curve
$$
x\, : \,[0,a]\longrightarrow \mathbb{R}^3\, , \,x(t)=\left(t,t^2,\frac{2}{3}t^3\right)^\tau
$$

22. (solved by @lpetrich ) The teacher writes a number less than ##50,000## on the board.
  • The first student finds that n is divisible by ##2##.
  • The second student finds that n is divisible by ##3##.
  • The third student finds that n is divisible by ##4##.
  • ...
  • The twelfth student finds that n is divisible by ##13##.
Ten of the students told the truth, two lied. The two liars have made their statements immediately after each other. What number did the teacher write on the board?

23. The Italian mathematician G.F.Malfatti presented the following in 1803, because of its degree of difficulty well-known task: Construct three circles into a given triangle so that the total area of the circles is maximal.

For the equilateral triangle, Malfatti found the solution

Malfatti_1.png


It wasn't until 1929 when the mathematicians Lob and Richmond showed that Malfatti had made a mistake here.

Show that there is a better solution for the equilateral triangle.

24. In which country in Europe originated this christmas custom?
Note the numbers behind your answers. If you like you can post your percentage!
  1. From Nikulden to Budni Vecher is lent in this country. At Christmas you can then taste Kravai, the traditional Christmas bread. The presents on Christmas Eve brings the Djado Koleda ("Grandfather Christmas").
    Russia 56 - Bulgaria 27
  2. Christmas is Jul and a house elf named Nisse (Julenisse) is even more important in this country than Santa Claus. It is said that he lives in stables and in barns and takes care of the animals there. He likes to play a little prank on the children.
    Norway 87 - Denmark 81
  3. The Christmas holidays are also called "beer festivals" in this country. Traditionally, they were celebrated rather quietly in the circle of the family. Even visitors were rather undesirable on the Christmas holidays, female visit on the 2nd Christmas holiday was once even considered a particularly bad omen. Christmas dinner in this country includes dishes such as roast goose, sauerkraut, potatoes, or ginger cookies.
    Estonia 81 - Germany 42
  4. Ilex and mistletoe are important symbols of Christmas in this country, as is the robin that is most often seen on Christmas cards.
    England 9 - Netherlands 3
  5. At Christmas, a log is burned in the fireplace and a cake shaped like a log is made, according to old customs. Otherwise, you will dine in this country rather nobly with selected delicacies. Even the smell of roasted sweet chestnuts must not be missing in the run-up to Christmas.
    France 24 - Spain 67
  6. An absolute must at Christmas in this country is the Joulukinkku, the Christmas ham. Christmas peace is proclaimed in this country on 12/24 and deceased family members are remembered on Christmas Eve. For Christmas dinner you will be served traditional rice pudding with cinnamon, sugar and an almond, which should bring good luck.
    Latvia 16 - Finland 34
  7. This country put the Christmas tree into the focus of Christmas for the first time. Also edible tree decoration of former times was replaced for the first time by glass balls. There are not just one, but several official gift bringers.
    Germany 12 - Czech Republic 2
  8. ##14## days before Christmas, they turn up, the thirteen charming, but also somewhat sneaky Christmas goblins - the last one, called the "Thirteenth", will not disappear until January ##6##th. However, the children of this country have to be especially careful of the troll woman Grýla, the mother of the thirteen kobolds - who was not good, is caught by her and consumed without further ado. An absolute must at Christmas is the traditional Christmas drink Jólaöl.
    Iceland 14 - Greenland 9
  9. Christmas is referred to in the language of this country as "Winter Festival" and Christmas Eve is the "Winter Festive Evening". On this day, according to Christian custom, the birth of Christ is celebrated, and according to ancient pagan custom, the return of the virgin of the sun. A popular Christmas ornament is Puzuri, a kind of mobile made of straw.
    Latvia 22 - Poland 33
  10. An important pre-Christmas custom in this country is the celebration of Lucia Day: on the day of Saint Lucia, December ##13##, the eldest daughter of the house plays the "Lucia Bride" and wakes the whole family for breakfast.
    On Christmas Eve, which is often called the "Dopparedan" (one-day's day), sausages, potato casserole with anchovies or Lutfisk, marinated cod are often served.
    The gifts are not brought by Santa Claus or the Christkind, but the Julbock.
    Sweden 23 - Lithuania 31
##27,81,81,9,24,34,12,14,22,23 \\##
##2^n+7^n+8^n+18^n+19^n+24^n=3^n+4^n+12^n+14^n+22^n+23^n \; , \;(n=0,1,\ldots ,5)##

25. Ten DYK Christmas gifts.

##10##: The image of Santa Claus flying his sleigh began in ##1819## and was created by Washington Irving, the same author who dreamt up the Headless Horseman.

##9##: Clement Moore's poem introduced eight more reindeer for Santa's sleigh and their names were Dasher, Dancer, Prancer, Vixen, Comet, Cupid, Duner and Blixem (for the German words for thunder (Donner) and lightning (Blitz)). These later evolved into Donner and Blitzen.

##8##: Some leave food out for Santa Claus' reindeer as Norse children did, leaving hay and treats for Odin's eight-legged horse Sleipnir hoping they would stop by during their hunting adventures. Dutch children adopted this same tradition, leaving food in their wooden shoes for St. Nicholas' horse.

##7##: America's first batch of eggnog was made in the Jamestown settlement in ##1607##. Its name comes from the word "grog", meaning any drink made with rum. Non-alcoholic eggnog is popular as well.

##6##: Between the ##16##th and ##19##th centuries global temperatures were significantly lower than normal in what was known as a "little ice age". Charles Dickens grew up during this period and experienced snow for his first eight Christmases. This "White Christmas" experience influenced his writing and began a tradition of expectation for the holidays.

##5##: The Christmas wreath was originally hung as a symbol of Jesus. The holly represents his crown of thorns and the red berries the blood he shed.

##4##: Tinsel was invented in ##1610## in Germany and was once made of real silver.

##3##: A Christmas tree is a decorated tree, usually an evergreen conifer such as spruce, pine, or fir or an artificial tree of similar appearance, associated with the celebration of Christmas. The modern Christmas tree was developed in medieval Livonia (present-day Estonia and Latvia) and early modern Germany, where Protestant Germans brought decorated trees into their homes. It acquired popularity beyond the Lutheran areas of Germany and the Baltic countries during the second half of the ##19##th century, at first among the upper classes.

##2##: The tradition of hanging stockings comes from a Dutch legend. A poor man had three daughters for whom he could not afford to provide a dowry. St. Nicholas dropped a bag of gold down his chimney and gold coins fell out and into the stockings drying by the fireplace. The daughters now had dowries and could be married, avoiding a life on the streets.

##1##: In ##1914## during World War I there was a now famous Christmas truce in the trenches between the British and the Germans. They exchanged gifts across a neutral no man's land, played football together, and decorated their shelters.
 

Attachments

  • Malfatti_1.png
    Malfatti_1.png
    6.5 KB · Views: 652
Last edited:
  • Like
Likes YoungPhysicist, member 587159, DeathByKugelBlitz and 2 others
Physics news on Phys.org
  • #2
Problem 1:

1)

The partial sums

##
s_m = \sum_{n=1}^m a_n
##

are monotonic increasing as the ##a_n## are positive numbers. To show convergence we use the monotonic convergence theorem. "Every bounded monotonic sequence converges." (on this see for example the book "Introduction to metric and topological spaces" by W. A, Sutherland).

If

##
b_{n-1} {a_{n-1} \over a_n} - b_n \geq C
##

for ##C > 0## and for all ##n > N## then

##
b_N a_N - b_{N+1} a_{N+1} \geq C a_{N+1}
##
##
b_{N+1} a_{N+1} - b_{N+2} a_{N+2} \geq C a_{N+2}
##
##
b_{N+2} a_{N+2} - b_{N+3} a_{N+3} \geq C a_{N+3}
##
##
\vdots
##
##
b_{m-1} a_{m-1} - b_m a_m \geq C a_m
##

Adding together gives and dividing by ##C## (recall ##C > 0##):

##
\sum_{n=N+1}^m a_n \leq {b_N a_N \over C} - {b_m a_m \over C}
##

Therefore

##
s_m = \sum_{n=1}^N a_n + \sum_{n=N+1}^m a_n
##
##
\leq \sum_{n=1}^N a_n + {b_N a_N \over C} - {a_m b_m \over C}
##
##
< \sum_{n=1}^N a_n + {b_N a_N \over C}
##

which is a constant not dependent on ##m##. Implying that ##s_m \equiv \sum_{n=1}^m a_n## converges.

2)

From

##
b_{n-1} {a_{n-1} \over a_n} - b_n \leq 0 \quad \text{for all} \; n > N
##

we have

##
b_m a_m \geq b_{m-1} a_{m-1} \geq \cdots \geq b_N a_N \quad \text{for} \; m > N
##

so that

##
a_m \geq b_N a_N {1 \over b_m} \quad \text{for} \; m > N
##

and hence

##
\sum_{n=N+1}^\infty a_n \geq b_N a_N \sum_{n=N+1}^\infty {1 \over b_n}
##

therefore if ##\sum_{n=1}^\infty b_n^{-1}## diverges then so does ##\sum_{n=1}^\infty a_n##.

3)

From

##
b_n = \Big( n \cdot \Big( {a_n \over a_{n+1}} - 1 \Big) - 1 \Big) \log (n)
##

rearranged we obtain

##
n \log (n) {a_n \over a_{n+1}} - (n+1) \log (n+1)
##
##
= b_n + \log (n) + n \log (n) - (n+1) \log (n+1)
##
##
= b_n + \log (n) + n \log (n) - (n+1) \log \big(n (1 + {1 \over n} \big) \big)
##
##
= b_n + \log (n) + n \log (n) - (n+1) \big( \log (n) + \log \big( 1 + {1 \over n} \big) \big)
##
##
= b_n - (n+1) \log \big(1 + {1 \over n} \big)
##

This allows us to employ parts 1) and 2). So that:

##
\lim_{n \rightarrow \infty} \Big( n \log (n) {a_n \over a_{n+1}} - (n+1) \log (n+1) \Big)
##
##
= \lim_{n \rightarrow \infty} b_n + \lim_{n \rightarrow \infty} - (n+1) \log \big( 1 + {1 \over n} \big)
##
##
= \lim_{n \rightarrow \infty} b_n + \lim_{n \rightarrow \infty} - (n+1) \Big( {1 \over n} - {1 \over 2n^2} + {1 \over 3 n^3} - \dots \Big)
##
##
= B - 1 .
##

For ##B > 1## the right hand side is a number greater than ##0## and hence ##\sum_{n=1}^\infty a_n## converges.

For ##B < 1## the right hand side is less than ##0##. Also, it is known that ##\sum_{n=4}^\infty (n \log (n))^{-1}## divergences. Hence ##\sum_{n=1}^\infty a_n## diverges.

Here is a proof that ##\sum_{n=4}^\infty (n \log (n))^{-1}## divergences. We have that

##
\sum_{n=4}^\infty {1 \over n \log (n)} \geq \int_4^\infty {dx \over x \log (x)}
##

as ##1/x \log(x)## is monotonic decreasing function. Now

##
{d \over dx} (\log (\log (x))) = {1 \over x \log (x)}
##

as such

##
\sum_{n=4}^\infty {1 \over n \log (n)} \geq \lim_{N \rightarrow \infty} \int_4^{N+1} {dx \over x \log (x)}
##
##
= \lim_{N \rightarrow \infty} \big[ \log (\log (x)) \big]_4^{N+1}
##
##
= \lim_{N \rightarrow \infty} \big( \log (\log (N+1)) - \log (\log(4)) \big)\rightarrow \infty .
##
 
Last edited:
  • Like
Likes mfb
  • #3
julian said:
Problem 1:
Very nice, although I had hoped the third part to be more difficult.

For all who are interested: part 1 and 2 are Kummer's criterion, part 3 is Bertrand's criterion.
 
  • #4
Question 2, what is the date? 02/12/2018? :smile:
 
  • #5
DeathByKugelBlitz said:
Question 2, what is the date? 02/12/2018? :smile:
Damn, I should have postponed the question by eleven days. :wink:
 
  • Like
Likes DeathByKugelBlitz
  • #6
fresh_42 said:
Damn, I should have postponed the question by eleven days. :wink:
So, , for question 2, the actual date is 13/12/2018? Or the date is unknown to the reader?
 
  • #7
Thugles said:
So, , for question 2, the actual date is 13/12/2018? Or the date is unknown to the reader?
The date here is only the day, and yes, the actual date is not needed.
 
  • #8
fresh_42 said:
The date here is only the day, and yes, the actual date is not needed.

Thanks!

Problem 2:

36 can be fatorated into 2*2*3*3 = 36. Therefore, the possibilities are:
4, 3, 3 , day 10
6, 2, 3, day 11
9, 2, 2 day 13

There is when my English starts to itch my head on something: if that son is the "eldest" and not the "elder", does that mean he has another son who is also older than another son? If that's the case, if we consider "born at the same day" as "same age", they can't be twins.

So their ages are 6, 2 and 3.

(Quite embarassed if that whole thing I came up with the word "eldest" actually made me fail the question instead of solving it ahahaha)
 
  • #9
Thugles said:
Thanks!

Problem 2:

36 can be fatorated into 2*2*3*3 = 36. Therefore, the possibilities are:
4, 3, 3 , day 10
6, 2, 3, day 11
9, 2, 2 day 13

There is when my English starts to itch my head on something: if that son is the "eldest" and not the "elder", does that mean he has another son who is also older than another son? If that's the case, if we consider "born at the same day" as "same age", they can't be twins.

So their ages are 6, 2 and 3.

(Quite embarassed if that whole thing I came up with the word "eldest" actually made me fail the question instead of solving it ahahaha)
He has an oldest son. That's the information.
Your result isn't the solution. You skipped an information which is a bit hidden in the words.
 
  • #10
DeathByKugelBlitz said:
abc = 36
a+b+c = 13

We know that the factors of 36 are 1,2,3,4,6,9,12,18,36

The fact he said he has an eldest means that he is older than the other 2 (the larger number is not repeated)
Also the word younger was bolded in the question, meaning the smaller number is not repeated (?)

So we find the 3 factors of 36 that add up to 13 and none of the numbers are repeated.

Therefore the solution is 9, 3, and 1
##3\cdot 9\cdot 1 \neq 36## and you don't know anything about ##13##, at least not in an acceptable solution. In fact the date is only needed to exclude ##1\cdot 1 \cdot 36## as its sum would be ##38##, which is not a date. You can only use what is given by the original text. Don't skip an information!
 
  • #11
Problem 2a:

Given that there are 3 sons and the product of their ages is 36, the possible combinations of sons' ages are:

(1, 1, 36)
(1, 2, 18)
(1, 3, 12)
(1, 4, 9)
(1, 6, 6)
(2, 2, 9)
(2, 3, 6)
(3, 3, 4).

Note that the second mathematician did not have the solution once the first stated that the ages summed up to the date. This means that there is more than one combination of ages that sums to the date. Only two of these combinations result in the same sum:

(1, 6, 6) and (2, 2, 9).

Finally, the first mathematician reveals that he has one eldest son, which rules out (1, 6, 6).

Thus, the ages of the mathematician's sons are 2, 2, and 9.
 
  • Like
Likes member 587159, PeroK, YoungPhysicist and 1 other person
  • #12
4:

When n = 10, the number has to end with a zero, otherwise it's not divisible by 10.

I can start with 1, 2, 3, 4, 5, 6, 7, 8, or 9 (all are divisible by 1).

I can have a possible 50 numbers that fit the criteria for n=2 (all even 2 digit numbers). Since when n = 4, 6, 8 we need the number to be divisible by 4, 6, 8 respectively, and these numbers are divisible by 2, the 4th, 6th and 8th digit must be even.

For n = 5, the nth digit must be either 5 or 0

So when n = 10, the nth digit is 0
And for n = 2, 4, 6, and 8, we know that the nth digit is either 2, 4, 6, 8, or 0
For n = 5, the nth digit is 5 or 0

Will continue trying to figure the rest out, that's what I have so far :smile:
 
  • #13
DeathByKugelBlitz said:
4:

When n = 10, the number has to end with a zero, otherwise it's not divisible by 10.

I can start with 1, 2, 3, 4, 5, 6, 7, 8, or 9 (all are divisible by 1).

I can have a possible 50 numbers that fit the criteria for n=2 (all even 2 digit numbers). Since when n = 4, 6, 8 we need the number to be divisible by 4, 6, 8 respectively, and these numbers are divisible by 2, the 4th, 6th and 8th digit must be even.

For n = 5, the nth digit must be either 5 or 0

So when n = 10, the nth digit is 0
And for n = 2, 4, 6, and 8, we know that the nth digit is either 2, 4, 6, 8, or 0
For n = 5, the nth digit is 5 or 0

Will continue trying to figure the rest out, that's what I have so far :smile:

Using the above, and then just testing numbers (brute force) I reached 1,020,005,640
 
  • #14
DeathByKugelBlitz said:
Using the above, and then just testing numbers (brute force) I reached 1,020,005,640
Sorry that was my fault (and I will correct it immediately) and beg you a pardon, because I have been unclear. I meant that all 10 digits should actually occur as in 1234567890.
 
  • Like
Likes DeathByKugelBlitz
  • #15
fresh_42 said:
Sorry that was my fault (and I will correct it immediately) and beg you a pardon, because I have been unclear. I meant that all 10 digits should actually occur as in 1234567890.

I thought that would be the case, so each unique digit can only be used once :)
 
  • #16
DeathByKugelBlitz said:
I thought that would be the case, so each unique digit can only be used once :)
Yes. E.g. the last one has to be 0 and the second one has to be even, etc.
 
  • Like
Likes DeathByKugelBlitz
  • #17
When n = 10, the number has to end with a zero, otherwise it's not divisible by 10.

I can start with 1, 2, 3, 4, 5, 6, 7, 8, or 9 (all are divisible by 1).

I can have a possible 45 numbers that fit the criteria for n=2 (all even 2 digit numbers). Since when n = 4, 6, 8 we need the number to be divisible by 4, 6, 8 respectively, and these numbers are divisible by 2, the 4th, 6th and 8th digit must be even. However, the first digit must be odd, since all the even digits are now taken.

For n = 5, the nth digit must be either 5 or 0. But 0 is taken for n = 10, so must be 5.

So when n = 10, the nth digit is 0
And for n = 2, 4, 6, and 8, we know that the nth digit is either 2, 4, 6, or 8.
Therefore, we also know that for when n = 1, 3, 7, 9 the nth digit is either 1, 3, 7, 9
For n = 2, 6 nth digit is either 4 or 8
For n = 4, 8 nth digit is either 2 or 6
For n = 5, the nth digit is 5

all the allowed 2 digit numbers:

14, 18, 34, 38, 74, 78, 94, 98

For each of these we add an unused odd number to the end and see if the result is divisible by 3

147, 183, 189, 381, 387, 741, 783, 789, 981, 987

All possible 5 digit numbers (all possible 4 digit numbers, plus a 5 at n=5 since the 5 has to be there):

14725, 14765, 18325, 18365, 18925, 18965, 38125, 38165, 38725, 38765, 74125, 74165, 78325, 78365, 78925, 78965, 98125, 98165

All possible 6 digit numbers (if 2nd digit is 4 or 8, 6th digit must be 8 or 4), then checking if they are divisible by 6

147258, 183654, 189654, 381654, 387654, 741258, 783654, 789654, 981654

All possible 7 digit numbers:

1472583, 3816547, 7836549

All possible 8 digit numbers:

38165472

There is only 1 possible 8 digit number

The number after 9 digits becomes 381654729

And the 10 digit number is 3816547290
 
  • Like
Likes fresh_42 and YoungPhysicist
  • #18
It was fun although a bit brute force :-p
 
  • Like
Likes YoungPhysicist
  • #19
DeathByKugelBlitz said:
It was fun although a bit brute force :-p
Fun is important. Brute force? Maybe, but the exclusion principle is probably the by far most used thought in mathematics: "##P(x)## true. Imagine ##P(x)## fasle, then ..." and so all possibilities with a false property ##P(x)## are excluded. But it is also used directly, when solutions are narrowed down, e.g. in numerical analysis, whenever an initial condition in a differential equation system is applied, because it excludes all other trajectories, and probably a lot more.
 
  • Like
Likes DeathByKugelBlitz
  • #20
Re problem 2a:

Although, technically, he could have two sons of the same age that are not twins! Sorry, that's a real spoiler!
 
  • Like
Likes YoungPhysicist and mfb
  • #21
6. Show that ##(0,1) \subset \mathbb{R}## cannot be written as a countable disjoint union of closed intervals.
I am having some trouble with finding out what's wrong with the following assignment? I haven't written out precise description, but the idea should be clear.
I0 = [0.25,0.75]

I1 = [0.0625,0.1875]
I2 = [0.8125,0.9375]

I3 = [0.015625,0.046875]
I4 = [0.203125,0.234375]
I5 = [0.765625,0.796875]
I6 = [0.953125,0.984375]
...
 
  • #22
SSequence said:
I am having some trouble with finding out what's wrong with the following assignment? I haven't written out precise description, but the idea should be clear.
I0 = [0.25,0.75]

I1 = [0.0625,0.1875]
I2 = [0.8125,0.9375]

I3 = [0.015625,0.046875]
I4 = [0.203125,0.234375]
I5 = [0.765625,0.796875]
I6 = [0.953125,0.984375]
...

Sorry, I'm having trouble understanding what your idea is. Could you write down a formula (or algorithm) for the interval [itex]I_n[/itex]?
 
  • #23
I will try to explain in few words what I was trying to say. We can proceed in iterations in which we generate more intervals. For example, the zeroth iteration, we generate 20 intervals. In first iteration, we generate 21 intervals. In second iteration, we generate 22 intervals. In the n-th iteration we generate 2n intervals. So uptill the n-th iteration we generate total of 20+21+...+2n intervals (all of them disjoint).

The explicit intervals I wrote were for iteration-0,1,2 (so that makes total of 20+21+22=7 intervals).

Roughly the ideal is that after n iterations have passed (and the n+1-th iteration starts) and when we move from 0 to 1, we will encounter 2n+1 gaps (very roughly speaking) which we haven't covered yet (not covered by the union of intervals we have considered up till the n-th iteration).

For each gap of the form (a,b) that we encounter, we define the width to be ##d=b-a##. And we introduce a new interval [a+d/4,a+3d/4]. Hopefully that makes some sense. As I mentioned, I am having some trouble understanding why this assignment wouldn't count as disjoint union of closed and disjoint intervals which equal (0,1).
 
  • #24
You are missing 0.303030... in base 4, for example, which is 4/5 in the decimal system. It is behind the first interval, then in front of the second interval you put in there, then behind the next one, and so on.
 
  • Like
Likes Infrared
  • #25
Problem 8:
For every case that two person can be in front of their card, the need to both be ##n## steps away from their card, so when the turns exactly ##n## steps, their card will get in front of them.(n = 1~12)

But since 12 steps(a complete turn) away in the same as 0 steps away,that leads to only 11 ways of "how far they are from their cards".
So, in order for the probelm to not be true, everyone has to sit ##n## steps away from there card and everyone's ##n## cannot be the same.

But since there are 12 people choosing from 11 possibillities, there must be two person with the same ##n##.
 
  • #26
mfb said:
You are missing 0.303030... in base 4, for example, which is 4/5 in the decimal system. It is behind the first interval, then in front of the second interval you put in there, then behind the next one, and so on.
This is interesting. Are there infinite number of points missing? I am guessing so, because finite number of points missing can be fixed.
 
  • #27
Young physicist said:
Problem 8:

For every case that two person can be in front of their card, the need to both be ##n## steps away from their card, so when the turns exactly ##n## steps, their card will get in front of them.(n = 1~12)

But since 12 steps(a complete turn) away in the same as 0 steps away,that leads to only 11 ways of "how far they are from their cards".
So, in order for the probelm to not be true, everyone has to sit ##n## steps away from there card and everyone's ##n## cannot be the same.

But since there are 12 people choosing from 11 possibillities, there must be two person with the same ##n##.
What if one person is seated correctly, then there are only 11 persons for 11 possibilities?
 
  • #28
SSequence said:
This is interesting. Are there infinite number of points missing? I am guessing so, because finite number of points missing can be fixed.
Sure. You are missing all numbers with only 0 and 3 in their base 4 expansion where the expansion doesn't end. This is an uncountable set. It is a variation of the Cantor set.Edit: Concerning problem 8: Note that this can be impossible with 3 people. If A, B, C face cards A, C, B, then every rotation will only make one person seated correctly.
 
  • Like
Likes SSequence
  • #29
@fresh_42 Re Problem 8:

For every case that two person can be in front of their card, the need to both be n steps away from their card, so when the turns exactly ##n## steps, their card will get in front of them.(n = 0~11)

Now, inorder for a counter example to exist, they each must have different steps away from their cards(The step from the cards are clockwise).
Starting from Mr.0, he can only sit right in front of his card(0).That's our first person.(Mr.n needs to sit n steps away from his card)
For Mr.1, he can only sit at 2;(He should sat on 1 if he follows the card)(The position here is relative,counting from the first guy's point which is 0.Clockwise.)
For Mr.2, he can only sit at 4;
For Mr.3, he can only sit at 6;
For Mr.4, he can only sit at 8;
For Mr.5, he can only sit at 10;
For Mr.6, he can only sit at 12,which is the same as 0, which Mr.0 already sat there.Therefore, a counter example to the problem does not exist.

This proof is kind of weird and hard to understand, but it should work.
28D858F0-B6AA-4C61-B4FB-5C58BB8A8695.jpeg
 

Attachments

  • 28D858F0-B6AA-4C61-B4FB-5C58BB8A8695.jpeg
    28D858F0-B6AA-4C61-B4FB-5C58BB8A8695.jpeg
    18.9 KB · Views: 724
Last edited:
  • Like
Likes fresh_42
  • #30
mfb said:
Sure. You are missing all numbers with only 0 and 3 in their base 4 expansion where the expansion doesn't end. This is an uncountable set. It is a variation of the Cantor set.
Yes, I think I have gotten a bit of intuition (after working around for while) why we can have decimals that will escape this kind of construction (by considering a construction in parts of 10 instead of 4). Not certainly in a good enough manner, but at least enough to convince myself. Thanks for pointing out the problem.
 
Last edited:
  • #31
Young physicist said:
@fresh_42 Re Problem 8:

For every case that two person can be in front of their card, the need to both be n steps away from their card, so when the turns exactly ##n## steps, their card will get in front of them.(n = 0~11)

Now, inorder for a counter example to exist, they each must have different steps away from their cards(The step from the cards are clockwise).
Starting from Mr.0, he can only sit right in front of his card(0).That's our first person.(Mr.n needs to sit n steps away from his card)
For Mr.1, he can only sit at 2;(He should sat on 1 if he follows the card)(The position here is relative,counting from the first guy's point which is 0.Clockwise.)
For Mr.2, he can only sit at 4;
For Mr.3, he can only sit at 6;
For Mr.4, he can only sit at 8;
For Mr.5, he can only sit at 10;
For Mr.6, he can only sit at 12,which is the same as 0, which Mr.0 already sat there.Therefore, a counter example to the problem does not exist.

This proof is kind of weird and hard to understand, but it should work.
View attachment 235466

I think you have all necessary arguments in your solution, well done!

Let me add the solution that is a bit more "mathematical". It doesn't differ from your thoughts, I just want to add it, as I think it's a bit shorter:

If we denote the distance of a guest to his expected seat by ##\pi(n)-n## for the given permutation (distribution guests - seats) ##\pi \in S_{12},## then the question is: Are there always two numbers ##n,m## such that for any ##\pi \in S_{12}## we have a cycle (rotation) ##\sigma \in \mathbb{Z}_{12}## such that ##\sigma(\pi(n))-n=\sigma(\pi(m))-m\,?## (If we have a rotation such that two guests have the same distance to their seats after the rotation, then there is also a rotation which will make this difference zero.)

Assume this is not the case. Then ##\{\,\sigma(\pi(n))-n\,|\,0<n<13\,\} = \{\,1,2,\ldots ,12\,\} =: Set_{12}## and ##\sum_{k\in Set_{12}} k = \sum_{k=1}^{12} (\sigma(\pi(k))-k)=\sum_{k=1}^{12} (\pi(k)-k)=0\,.## On the other hand is ##\sum_{k\in Set_{12}} k= 78 \equiv 6 \operatorname{mod}12 ## which cannot both be true.
 
  • Like
Likes YoungPhysicist
  • #32
fresh_42 said:
I think you have all necessary arguments in your solution, well done!

Let me add the solution that is a bit more "mathematical". It doesn't differ from your thoughts, I just want to add it, as I think it's a bit shorter:

If we denote the distance of a guest to his expected seat by ##\pi(n)-n## for the given permutation (distribution guests - seats) ##\pi \in S_{12},## then the question is: Are there always two numbers ##n,m## such that for any ##\pi \in S_{12}## we have a cycle (rotation) ##\sigma \in \mathbb{Z}_{12}## such that ##\sigma(\pi(n))-n=\sigma(\pi(m))-m\,?## (If we have a rotation such that two guests have the same distance to their seats after the rotation, then there is also a rotation which will make this difference zero.)

Assume this is not the case. Then ##\{\,\sigma(\pi(n))-n\,|\,0<n<13\,\} = \{\,1,2,\ldots ,12\,\} =: Set_{12}## and ##\sum_{k\in Set_{12}} k = \sum_{k=1}^{12} (\sigma(\pi(k))-k)=\sum_{k=1}^{12} (\pi(k)-k)=0\,.## On the other hand is ##\sum_{k\in Set_{12}} k= 78 \equiv 6 \operatorname{mod}12 ## which cannot both be true.
Though I can’t fully understand that,but it seems way better than “Mr.n”:wink:
 
  • #33
Young physicist said:
Though I can’t fully understand that,but it seems way better than “Mr.n”:wink:
The trick is the same as yours:

If we cannot achieve at least two same distances, then all distances on the finite set ##\{\,1,2,\ldots ,12\,\}## have to occur. Then we sum them up twice, ##1+2+ \ldots +12=78##, and sum over possible permutations. Both summations have to have the same remainder when divided by ##12##, which is not the case.

I only encoded the difference a bit more explicitly: actual place (permutation of seats ##\pi(n)##) minus expected place (##n##) and wrote the rotation of the table as another special permutation (cycle ##\sigma##).

A cycle is a permutation that shifts numbers. In general ##\sigma = (n_1\,n_2\,\ldots\, n_k)## means ##n_1 \mapsto n_2 \mapsto n_3 \mapsto \ldots \mapsto n_{k-1} \mapsto n_k \mapsto n_1##. Here we have a cycle where ##n_i=n_{i-1}+k## for a certain fixed number ##k## and ##\{\,n_i\,\}=\{\,1,2,\ldots ,12\,\}##. This means, our rotation is of the form ##\sigma=(1\,2\,3\,\ldots\,12)^k## with ##\sigma^{12}=id##, so this is basically the group ##\mathbb{Z}_{12}## of all remainders by division with ##12##.
 
  • #34
fresh_42 said:
σ12=idσ12=id\sigma^{12}=id
Where does the id come from?
 
  • #35
Young physicist said:
Where does the id come from?
That means "identity". The neutral element, which in case of functions is the one that maps all ##n \mapsto n##. If you have a cycle ##\sigma## of length ##n##, then ##\sigma^n= id = 1##. E.g. ##(1,2,3)## maps ##1 \mapsto 2\, , \,2\mapsto 3\, , \,3 \mapsto 1##. Now if you apply this function three times on any of the numbers ##1,2,3## then you will end up where you began.

In case of our table it means: If we turn the table twelve times, always by the same amount of seats, then we will be back at where we started.
 
  • Like
Likes YoungPhysicist

Similar threads

  • Math Proof Training and Practice
2
Replies
61
Views
7K
  • Math Proof Training and Practice
3
Replies
93
Views
10K
  • Math Proof Training and Practice
3
Replies
80
Views
4K
  • Math Proof Training and Practice
2
Replies
60
Views
8K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Math Proof Training and Practice
2
Replies
61
Views
6K
  • Math Proof Training and Practice
2
Replies
42
Views
6K
  • Math Proof Training and Practice
3
Replies
86
Views
9K
  • Math Proof Training and Practice
2
Replies
67
Views
7K
  • Math Proof Training and Practice
2
Replies
48
Views
9K
Back
Top