Test of Mathematics Solution Subjective 177 -The Famous Doors Problem

Test of Mathematics at the 10+2 Level

This is a Test of Mathematics Solution Subjective 177 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

 There are 1000 doors $ D_1, D_2, . . . , D_{1000}$ and 1000 persons $ P_1, P_2, . . ., P_{1000}$. Initially all the doors were closed. Person $ P_1$ goes and opens all doors. Then person $ P_2$ closes doors $ D_2, D_4, . . ., D_{1000}$ and leaves all odd numbered doors open. Next, $ P_3$ changes the state of every third door, that is, $ D_3, D_6, . . ., D_{999}$ by closing a door if it is open or opening a door if it is closed. Similarly, $ P_m$ changes the state of the doors $ D_m, D_{2m}, . . ., D_{nm}$, while leaving the other doors untouched. Finally, $ P_{1000}$ opens $ D_{1000}$ if it is closed or closes it if it is open. At the end how many doors remain open?

Solution

This particular problem requires careful analysis of the problem statements and decide what the problem is exactly asking us to solve.

Basically there are two possible states of the door, namely Open (denote by 'o') and Close (denote by 'c'), and initially all doors are in state 'c'.  Let us define the operation of changing the state of the door by  'F'. So if 'F' can be seen as a function where the variables are 'o' and 'c'  and we have:

F(o) = c

F(c) = o

So if a door is operated on 'n' times we represent it by $ F^n(c)$ as initially all the doors were closed. It is very trivial to state that if the door is operated even number of times it returns to the 'c' state and if it's operated odd number of times then it has a change to 'o' state.

Therefore, $ F^n(c)$ = c, if n is even, else $ F^n(c)$ = o, if n is odd.       ......(i)

As 'n' represents the number of times the operation has been performed on a particular door, as we understand from the problem that a door $ D_m$ is only operated by a person $ P_k$ iff k divides m. So whenever we have an divisor of 'm', we increment the value of 'n' by 1. Thus finally after all the counting the value of 'n' will be nothing but the number of divisors of 'm'.

We are to find which doors will remain in state 'o' after the whole procedure and for a door to be in state 'o' it has to be operated odd number of times (from (i)). Which implies that 'n' has to be odd. So all those doors which have odd number of divisors will be open after the process.

Now it can be shown very trivially that a number has odd number of divisors iff it is a perfect square. (Think!!)

So our solution will be all those doors that are marked with perfect square numbers ranging from 1 to 1000.

Solution Set: {$ D_1, D_4, D_9, D_{16}, D_{25}, . . ., D_{900}, D_{961}$}

Number Theory, Greece MO 2019, Problem 3

[et_pb_section fb_built="1" _builder_version="3.22.4"][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Understand the problem

[/et_pb_text][et_pb_text _builder_version="4.0" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]Find all positive rational $(x,y)$ that satisfy the equation :$$yx^y=y+1$$[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="3.22.4" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="4.0"]Greece MO 2019, Problem 3[/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]Number Theory[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]7/10[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="4.0" open="off"]Challenges and Thrills of Pre College Mathematics[/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Start with hints

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="3.22.4" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]Do you really need a hint? Try it first!

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]Let us the given equation in terms of rational numbers and simplify the equation. Let  $y=\frac{p}{q}$ and $x=\frac{r}{s}$ where $\gcd(p,q)=\gcd(r,s)=1$. We have$$p\cdot \left(\frac{r}{s}\right)^{\frac{p}{q}}=p+q \Longleftrightarrow p^q \cdot r^p=(p+q)^q \cdot s^p$$ And since $\gcd(p+q,p)=\gcd(r,s)=1$ we must have $p^q=s^p$ and $r^p=(p+q)^q$. Now, we have to find the solutions from these equations.[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]Observe both the equations are of the form \(x^a = y^b\). The idea is that due to the prime factorization theorem, we can specify that \(x^a = y^b\) leads to a special form of the x and y. Claim: If $x^a=y^b$ for some $x,y,a,b$ naturals , then there exists a natural $z$ such that $x=z^m$ and $y=z^n$ where $m=\frac{b}{\gcd(a,b)}$ and $n=\frac{a}{\gcd(a,b)}$.[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]Proof of Claim: Consider the prime factorization theorem of the x and y in \(x^a = y^b\). Observe that it implies x and y must have same set of primes by the prime factorization theorem. Let x and y contain the primes \(p_1, p_2, ..., p_k\). Let \( x = \prod_{i=1}^{k} x_i\) and \( y = \prod_{i=1}^{k} y_i\). The above equation implies that \( a.x_i = b.y_i \). This implies that \( y_i =  n.c \) and \( x_i = m.c \), where c is a natural number. Hence \( x = z^m, y = z^n\).

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]Using the intuitive claim, $p^q=s^p$ , there exists a $z$ such that $p=z^p$ , if $z \neq 1$ we have $p=z^p=z^{z^p}$ and continuing like this , $p$ is unbounded ,contradiction. So , we must have $z=1$ wich means $p=s=1$ and from $r^p=(p+q)^q$ we have $r=(q+1)^q$ So, the solutions come out to be  $x=(q+1)^q$ and $y=\frac{1}{q}$, where $q$ is any positive integer.[/et_pb_tab][/et_pb_tabs][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Watch video

[/et_pb_text][et_pb_code _builder_version="3.26.4"]
[/et_pb_code][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

[/et_pb_text][et_pb_blurb title="Math Olympiad Program" url="https://cheenta.com/matholympiad/" url_new_window="on" image="https://cheenta.com/wp-content/uploads/2018/03/matholympiad.png" _builder_version="3.23.3" header_font="||||||||" header_text_color="#e02b20" header_font_size="48px" link_option_url="https://cheenta.com/matholympiad/" link_option_url_new_window="on"]

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.[/et_pb_blurb][et_pb_button button_url="https://cheenta.com/matholympiad/" url_new_window="on" button_text="Learn More" button_alignment="center" _builder_version="3.23.3" custom_button="on" button_bg_color="#0c71c3" button_border_color="#0c71c3" button_border_radius="0px" button_font="Raleway||||||||" button_icon="%%3%%" background_layout="dark" button_text_shadow_style="preset1" box_shadow_style="preset1" box_shadow_color="#0c71c3"][/et_pb_button][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Similar Problems

[/et_pb_text][et_pb_post_slider include_categories="9" _builder_version="3.22.4"][/et_pb_post_slider][et_pb_divider _builder_version="3.22.4" background_color="#0c71c3"][/et_pb_divider][/et_pb_column][/et_pb_row][/et_pb_section]