Abolf is on the second step of a stairway to heaven in every step of this stairway except the first one which is the hell there is a devil who is either a human, an elf or a demon and tempts Abolf. The devil in the second step is Satan himself as one of three forms. Whenever an elf or a demon tries to tempt Abolf he resists and walks one step up but when a human tempts Abolf he is deceived and hence he walks one step down. However if Abolf is deceived by Satan for the first time he resists and does not fall down to hell but the second time he falls down to eternal hell. Every time a devil makes a temptation it changes its form from a human, an elf, a demon to an elf, a demon, a human respectively. Prove that Abolf passes each step after some time. Proposed by Yaser Ahmadi Fouladi
Problem
Source: Iranian Combinatorics Olympiad 2020 P5
Tags: combinatorics
29.07.2021 23:08
First let Abolf first falls at stage n. Let Abolf fall to the stage n-k.th stage(there isn'tt any humman at (n-k)th stage) that means from nth to (n-k+1)th stage. There were all humans after the fight? they turned to elfs. So now Abolf can win all the elfs till nth stage. So they all turned to Damons. Now Adolf is in the stage n+1. If there is human than he will win the Damon at the stage n. And now he can win the elf there and now he stays at the n+1.th stage without falling.(Btw if there were not any human at stage n+1 that means he can stay there without falling.)After that, same things happen for n+1 and then after a finite number of steps he stays n+2th step without falling or maybe a higher step. It goes on like this till end. In this part we proved that no matter he falls much he can go further. Now there is a fact about Satan , for the second part we need prove that Abolf guarantee not to fall the Satan's place twice. Let's say Adolf first fall from mth stage to stage 2.(For m>=3) Abolf beats Satan for the first time but can't fall twice. Now stages from 3 to m is full of Elfs. Abolf beats them after beating mth stage.There is Devon on the mth stage. . If he didn't fall to mth place once then no problem then. But if he falls once let's say he first fall from the stage m+k to stage m. It means from m+1th stage to m+kth's are all Elfs right now.(After falling to mth stage). Now Abolf beats the Devon. And climb till m+k and after wining m+kth stage. There is Devon at m+k. The same scenere that we first got. Now Abolf guarantee no to fall to a stage before m+k. Because when he first fall to stage m+k he will climb again as in the previous scenere.(I meant Falling to m and climbing m+k) So now we proved that Abolf can quarantee not to fall the same place twice. So it is proven that Abolf won't fall the Satan's place twice. Because he is already at the stage 2 and going to stage 3. Problem is solved. Note : We accept that Abolf goes to stage 3 without resisting Satan because if so then he will first resist Satan and then go to stage 3 and if there is a human there then he is going to Stan's place twice. And this makes the question wrong. So we accept that he goes direclty to stage 3 without resisting Satan. Note