[브금] 초등학교 수학문제 종결

a와 b 두 문자만으로 이뤄진 이상한 언어가 있다.

그리고 a는 한 단어라고 상정한다.

아래의 법칙에 따라서, 새로운 단어를 만들 수 있다 :

(1) 어떤 단어든, b를 덧붙임으로써 새로운 단어를 만들 수 있다.

(2) 만약 단어에 aaa라는 시퀀스(구획) 이 나타나면, 이 aaa는 b로 대체할 수 있다.

(3) 만약 단어에 bbb라는 시퀀스(구획) 이 나타나면, 이 bbb는 빼버릴 수 있다.

(4) 어떤 단어든, 그 주어진 단어 시퀀스를 2번 반복함으로써 새로운 단어를 만들 수 있다.

가령 (4)에 의해 aa는 단어이며, 또다시 (4)에 의해 aaaa 역시 단어이다.

이를 또 (2)에 의해 바꾸면 ba도 단어이며, (1)에 의해, bab도 단어이다. 

다시 또 (1)에 의해 babb도 단어이고, (4)에 의해 babbbabb도 단어이며,

이를 또 (3)으로 바꾸면 baabb도 단어이다.


baabaabaa 는 단어가 아님을 증명하시오.




국제수학영재발굴대회(IMTS) 44라운드 1번 문제라는듯.....

cms.math.ca/Olympiads/IMTS/imts44.html

a가 최초의 단어이므로 어떤수이든 a로부터 시작해야함. 따라서 역추적했을때 a가 나오지않는다면 그건 단어가 아니죠. 일단 역행할땐 모든게 반대가 되니

(1) 우측에 b가있다면 뺄수있다.
(2) b는 aaa로 대체가 가능하다.
(3) 아무데나 bbb를 만들수있다.
(4) 같은 구획이 반복될때 반을 없앨수있다.

이렇게 바뀜.
여기서 baabaabaa를 바꿔야하는데.

(3)을써서 b를 많이만들어봤자 가만히놔두면 최초의 언어a로 갈수가없기때문에 어떻게든 변형을해야하는데 변형방법은 (2)에의해서 a로 모두 전환하거나 (1)에 의해서 빼버리는 방법밖에없음. 하지만 (3)->(2)의 콤보는 a를 최소3개 최대9개나 만들게되고 이렇게 많이 생긴 a를 처리할 방법은 (4)뿐. 하지만 (4)를 쓸 조건이 되려면 a,b를 합친 갯수가 짝수가 되어야하는데 지금상태에서는 9개이고 (3)을 써도 12개. 거기서 b를 a로 변형하더라도 한번변형할때 갯수가 -1+3구조이기때문에 항상 홀수. 따라서 (4)를 쓸수없음. 고로 (3)은 쓸일이 없음.

(2)를 이용했을떄도 많은수의a가 생기는데 이를 없앨방법은 (4)밖에없음. 하지만 위에서 썼다시피 현재 9개인상태에서 (2)를 쓰면 갯수가 -1+3이 되기때문에 항상 홀수임. 고로 (2)를 쓸수없음.

(1)과 (4)는 지금상태에서 조건이 안되므로 쓸수없음.
따라서 baabaabaa는 영원히 a가 되지못함.

쓰고나니 생각이 났는데 역행하지않더라도 a에서 시작을했을때
짝수 홀수관계를 생각하면 될거같긴한데 생각하기 힘들어서 포기..

리플이 달리지 않는다

일단 초등학교 수학문제는 아닌거같은데 -0-ㅋㅋ 근데 왜 단어가 아닌거지..
일단 문제에 ba가 단어라고 했으니 여기서부터시작하면 그냥 (1)만 계속써서 옆에다가
a b a a b a a 붙여버리면되는거아님?

aaa->b, bbb->X랬으니까
baabaabaa를 단어라고 가정하면,
baabaabaa+a=baabaabb도 단어
baabaabb+b=baabaa도 단어
baabaa+a=baabb도 단어
baabb+b=baa도 단어
baa+a=bb도 단어
bb+b도 단어
근데 bbb=없음 이니까 단어가 아닌듯

baabaabaa=bbbbbb=bbbX2
bbb를 뺄수 잇으니 그걸 두번빼면 암것도안남으니까 단어로서의 기능 상실 아님?

으악 2초차이

아 원문을 봤더니 문제 해석이 잘못되었네요. (1) 에서 a나 b를 덧붙일수있는게 아니라 b만 덧붙일수있습니다. a는 여기서 쓰는 단어 a가아니예요.

귀찮=3

1번 조건 이상하지 않음?
ab 둘다 붙일 수 있으면
aabaabaab가 a에서 나올 수가 있어버림

Factor// 아 그런가여... 수정할게여

어라 진짜 해석 잘못되어있넹..

으앜 레이튼 교수 돋네

왠지 일케푸는게아닌거같아 근데 하게되넹
baabaabaa가 단어라면 뒤에 b 붙일수있음
baabaabaa
baabaabaab
baabaabaaaaa
baabaab(aaa)aa=baabaabbaa
baabaabbaab
baabaabbaaaaa
baabaabbbaa
baabaaaa
baabba
baabbab
baabbaaaa
baabbba
baaa
bb

단어라면 뒤에 또 b붙일수있음
bbb
없음

없으므로 단어가아님

baabaabaa
이 단어가 어떠한 나열에서 만들어졌다고 하자,
과정을 역추적하면 aaa->b 에서
aaa aa aaa aa aaa aa
a를 두배씩 뿔림으로써 새로운 단어를 만들 수 있는데
이때 가능한 a의 갯수는 a(1개) aa(2개) aaaa(4개)....로 2^n개이다
baabaabaa의 전단계라 볼 수 있는 aaa aa aaa aa aaa aa는 a가 15개
이런 조합은 나올수가 없어서 땡...
이라고 하기에는 너무 단순하게 접근한것같기도함

제가 풀어보면서 생각한건데 aaa->b로의 변형은 가능하다고 나와있지만
b->aaa로의 변형은 가능하다고 나와있지 않음. 그리고 사실 불가능한게
bbb->X에서 X->bbb라고 가정하면 x->aaaaaaaaa인거임 모든자리에 a 9개씩 붙일수있단소리

aaa aa aaa aa aaa aa는 (aaa)(aaa)(aaa)(aaa)(aaa)인데 이건 bbbbb고 뒤에 b 붙이면 없어져서 단어없음 이라고 봐도 되는것같기도 한데 관건은 b->aaa의 과정을 어떻게 설명해내느냐인듯

아 제 위로 3번째 리플 틀렸네요 본문에서 baabb도 단어랬는데 이것도 2^n만족을 안함,,

마지막이 b로 끝나지 않으므로 반복에 의한 단어라고 가정.
하지만 baabaabaa는 반복으로 만들어낼 수 없음.
baabaabaab나 baabaabaabb또한 반복으로 만들어낼 수 없으므로, baabaabaa는 만들어낼 수 없음.

baabaabaa + b = (aaa)aa(aaa)aa(aaa)aa + b = aaa(aaa)aaa(aaa)aaa + b = bbbbb+ b= 업ㅂ음...
이거 맞나..

baabaabaa가 baaaaaaabaa로부터 만들어졌다고 가정 -> 반복에 의해 만들기 불가
baabaaaaaaa -> 불가
baaaaaaaaaaaa -> 불가.. 하여간 다 안됨.

반복을 해서 만들었을때 뒤에 b 붙여서 없에는건 자유로우므로
baabaabaa와 baabaabaab와 baabaabaabb를 적당히 둘로 쪼개려면,
맨뒤에가 baa..로 끝나므로 뒤에도 ...baa로 끝나는 부분에서 적당히 짤라서 어쩌구..

b= aaa 임으로 baabaabaa = aaaaaaaaaaaaaaa
다시 바꾸기 시작하면 aaaaaa.......................
윙; 왜 조건상 단어라는게 증명되는거지;
다시 이번엔 역으로 baabaabaa가 단어라는걸 가정
b= aaa 임으로 baabaabaa = aaaaaaaaaaaaaaa
bbbbb 인데 3번 조건에 따르면 bb 가 되고 1번 조건에 따라 b를 붙엿을때 어떤 단어든 단어가 되어야 하는데 bbb 가 되어 삭제된다, 고로 baabaabaa 가 단어라는 가정이 틀렷다..?
근데 3번 조건이 강제성이 아니라 억지가 좀 있는데;

흐음....
대체로 국외 문제는 기존에 알려진 공식이나 이론을 적용하는것보다, 그 문제 안에서 공식이론을 찾는 문제가 되는군여 . . .
복잡해지기는한데...
아무래도 단어의 생성조건을 이해하는게 저 단어가 아니라는조건을 찾는것 보다 더 빠를듯??

(~~~)(~~~)의 구조가 성립해야되는데
맨앞의 ba...와 맨뒤의 ..aa에서 하나의 구절이 ba...aa라는걸 알아내야되는데
이런건 문자라고 가정하면..으로 풀어서 안됨을 보여줘야되는데

탁구 보고 있는 사이 아까는 망글 됬는데 흥하넼ㅋㅋ

a가 최초의 단어이므로 어떤수이든 a로부터 시작해야함. 따라서 역추적했을때 a가 나오지않는다면 그건 단어가 아니죠. 일단 역행할땐 모든게 반대가 되니

(1) 우측에 b가있다면 뺄수있다.
(2) b는 aaa로 대체가 가능하다.
(3) 아무데나 bbb를 만들수있다.
(4) 같은 구획이 반복될때 반을 없앨수있다.

이렇게 바뀜.
여기서 baabaabaa를 바꿔야하는데.

(3)을써서 b를 많이만들어봤자 가만히놔두면 최초의 언어a로 갈수가없기때문에 어떻게든 변형을해야하는데 변형방법은 (2)에의해서 a로 모두 전환하거나 (1)에 의해서 빼버리는 방법밖에없음. 하지만 (3)->(2)의 콤보는 a를 최소3개 최대9개나 만들게되고 이렇게 많이 생긴 a를 처리할 방법은 (4)뿐. 하지만 (4)를 쓸 조건이 되려면 a,b를 합친 갯수가 짝수가 되어야하는데 지금상태에서는 9개이고 (3)을 써도 12개. 거기서 b를 a로 변형하더라도 한번변형할때 갯수가 -1+3구조이기때문에 항상 홀수. 따라서 (4)를 쓸수없음. 고로 (3)은 쓸일이 없음.

(2)를 이용했을떄도 많은수의a가 생기는데 이를 없앨방법은 (4)밖에없음. 하지만 위에서 썼다시피 현재 9개인상태에서 (2)를 쓰면 갯수가 -1+3이 되기때문에 항상 홀수임. 고로 (2)를 쓸수없음.

(1)과 (4)는 지금상태에서 조건이 안되므로 쓸수없음.
따라서 baabaabaa는 영원히 a가 되지못함.

쓰고나니 생각이 났는데 역행하지않더라도 a에서 시작을했을때
짝수 홀수관계를 생각하면 될거같긴한데 생각하기 힘들어서 포기..

/포터윈터
해도 되요. 왜냐하면 aaaaaaaaaaaaaaa 가 단어가 아니면 baabaabaa 가 단어가 아니라는게 증명되거든요.. ㅇㅂㅇ;;

pres티아/ 아 지금 알아냈듬 리플 맨밑에 안된다고 한건 지웠음

pres티아// baabaabaa가 aaaaaaaaaaaaaaa말고 다른데서 파생될수 없다는걸 증명하셔야 aaaaaaaaaaaaaaa가 단어가 아닐때 baabaabaa가 단어가 아니라고 할 수 있습니다.

어라 풀린건가... 머릿속으로 나온 답안인데 일단 적어 갑니다.
대치법으로 바꿔서 생각
a->1 , b->3 , bbb = 9 ->0
(b를 3으로 대치 한건, aaa 가 b로 바뀌기 때문에)
일단 처음, 최초 기본 단어 시작은 a 이므로 1로 시작...
그 후에 무조건 추가될수 있는 단어는 b 이고, 이를 풀거나, 다른 조합으로 사용 가능 하지만 늘어 나지 않습니다.
위의 조건(a->1 , b->3) 을 생각 하면, 단어의 기본 성립 기준은
1+(3*n) 이라는 결과가 나오는데
baabaabaa = 311311311 = 15 이므로, 이 단어 기본 성립조건에 부합되지 않음으로 만들수 없는단어?

/factor 흠냐;; 그러고 보니까 -ㅛ- 무리가 있네요 ;; 흠냐; 이거 복잡하게 생각할수록 어렵네 ㅠ

baabaabaa
이 단어가 어떠한 나열에서 만들어졌다고 하자,
과정을 역추적하면 aaa->b 에서
aaa aa aaa aa aaa aa

a를 두배로 만듬으로써 새로운 단어를 만들 수 있는데
이때 가능한 a의 갯수는 a(1개) aa(2개) aaaa(4개)....로 2^n개이다
baabaabaa의 전단계라 볼 수 있는 aaa aa aaa aa aaa aa는 a가 15개

X->bbb b->aaa에서 X->aaa aaa aaa
즉 baabaabaa의 전단계에서 가능한 a의 갯수는 15+9n(n은 자연수)

근데 여기서 n=1이면 24인데 24->12->6->3이라서 안되고
3넣어서 15+27=42->21이라서 안되고
풀이를 살려볼려헀는데 안되네

제 답좀 누가 검토좀 해주세요 ㅠㅠ

15+9n을 2^m(m은 임의의 양의 정수)로 나눌때 항상 홀수가 된다는걸 증명해주실분 있나요

LoreSin// 흠 님말대로면 aa는 2지만 단어입니다.

ㄴ아 그렇군여 ㄳ

문제의 조건에서 부터 시작하면, '모든 단어'는 a에서부터 시작하고, 이로인해 만들 수 있는 '언어'는 무조건 a와 b로 이루어져 있다. <-- 공과에서 자주 나오는 컨셉인데 a와 b로만 이루어져 있으니 null문자 (빈 문자)가 존재하지 않는다고 봐야 합니다.
윗분들이 해놓으신 것 처럼 주어진 baabaabaa 를 단어라 가정하면, 조건을 이용해 만들 수 있는 모든 시퀀스들은 '단어'가 되어야 하는데,
aaa aaa aaa aaa aaa 로 변환하고 이는 다시
bbbbb -> bb -> bbb -> x 로 변환이 되는데, x, 즉 빈 문자는 위에서 정의한 '언어'가 될 수 없으므로 (a와b로 이루어지지 않았으므로) 단어가 될 수 없다. 즉 조건 (또는 주어진 사실 - 단어로 조건에 맞춰 만들 수 있는 새 단어들은 모두 단어들이다) 에서 빗나가게 되므로 주어진 문자 (baabaabaa) 는 단어가 아니다.

한글로 말해 십년아.

그렇네요 a로 전부 바꾼다음 생각하는게 맞을거같음
baabb를 전부 a로 바꾸면 aaa aa aaa aaa인데 aaa aaa aaa aa->aa이고 a라는 최초단어로 돌아갈수가 있네요. 문제는 빈자리에 9개 채워넣는거가 좀 맘에 걸리는데요 전..

그게모양// 제 머리로는 이해할슈없서여 aa는 1+3x꼴이아닌뎀

단어의 조건이라하면 a의 갯수를 N이라 할때, (N%3==2 || N%3==1)==1일때 될듯

그게모양,지나가던카미씨// 3x+1꼴하고 3x+2꼴이 있죠 (x=0,1,2,3...)

지나가던카미씨 // ㅈㅅ 착각했네요

포더윈터 / % 가 무슨 뜻이죠 ...?

아 %가 수학기호가 아니죠 ㅈㅅ.. 수학적으로 표현하면 b를 a로 치환해 센 a의 갯수가 N=2 (mod 3)과 N=1 (mod 3)을 만족할때 단어이다. 라고 할 수 있겠네요

여러분께서는 지금 공대XP를 보고 계십니다

ㄴ ㅋㅋㅋㅋ

% 가 아직 뭔지 감은 안잡히지만...

아까 제 답에서 빼먹었던 "시퀀스2번도 단어다" 라는것을 보충 하면
1+(3*n)*(2*k)
로 15를 만들수 없죠

식을 간소화 하니...
6*n*k 로 14를 만들수 있는가...
불가능이군요

제가 적은 답들 정리
기본 ) a = 1 , b = 3 , bbb = 9 = 0 으로 치환

규칙1) 1 + (3n) 으로 단어를 만든다
규칙2,3) 111 은 3, 333 은 9 (=0) 으로 치환
규칙4) 단어의 반복 (* 2) 으로 단어생성

위 규칙4개를 기본 단어 a 에 엇갈려 놓으면
1+3n*2k <-- 라는 식(n 은 추가되는 b 의 개수, k는 같은 시퀀스가 반복된 횟수)

baabaabaa = 15
위의 식으로 15를 만들어 낼수 없다.
그러므로, baabaabaa는 단어로 성립하지 않는다.

ㄴ 자꾸 생각을 햇는데요;; 님말대로면 (1+3n)*2k 로 봐야 하지 않을까요;;

%는 프로그래밍에 쓰이는 기호에요. 나머지를 구하는거죠. 위에 포터윈터님이 걸 살짝 해석하자면.. a의 갯수를 3으로 나눴을때의 나머지가 2랑 같은가 라는걸 의미하는겁니다. 포터윈터님은 아무래도 프로그래머이신듯...

ㄴ 그렇군요!! 제 정리의 오류를 발견 했습니다.
다시 정리

1이라는 숫자에서, 3을 더할수 있는 카드와, 2를 곱할수 있는 카드를 무한정 사용할수 있다고 가정 하면, 이것으로 15를 만들수 없는 이치 이지요
제 정리의 오점을 발견 해주셔서 더 정확한 답으로 만들어 지는군요 *_*;;

(1+3n)*2k = 15 가 성립해야 하므로
(1+3n)*k = 15/2 가 되어야 하는데 (1+3n)과 k 모두 정수이므로 단어가 성립하지 않는게 증명되겟네요.

풀린듯한데... 맞은거 같죠??

henro / 감사요 ㅎㅎ
더 정확하게 이해가 되네요

LoreSin pres티아//(1+3n)*2k이 아니라 (1+3n)*2^k이 아닐까요? 어쨌든 약간의 문제가 있습니다. +3과 *2는 순서가 없기때문에 식을 그렇게 쓸수없습니다.. 예를들어 1에서 3을 더해 4가 된뒤 곱하기 2 를 해서 8이 되고 다시 더하기 3을 하면 11이 됩니다. 이는 (1+3n)*2k나 (1+3n)*2^k의 식에 맞지않습니다... 하지만 1에서 +3과 *2를 아무리 이용해도 15가 안된다는걸 증명하면 증명이 될것 같은데..

Factor / 그러니까 카드게임으로 생각해서...
1의 숫자에 *2 의 카드와 +3의 카드를 어떤순서로 조합해도 15를 만들수 없다는것이죠 . . .
일단 큰수가 아니니까 이런게 가능하긴 한데 ㅋㄷ

/factor 흠냐 확실히 그렇네요 -ㅛ-;; 질못봣네요 ;; 졸려서 포기해야되나 -ㅅ- 이런거 잡음 잠 못잔다니까 ㅠㅠ

네 그렇죠..하지만 일단 저식만으로는 증명이 안된다는겁니다. 일단은 1로 시작하는 숫자에 +3카드와 *2카드를 아무이사용해도 15를 만들수없는건 맞는것같은데 이를 증명할 다른 수식이나 방법이 필요하겠죠.

제 수학 실력이 딸려서 더 자세한 수식으로는 표현이 어렵네요 ㅎㅎ;;;
어떻게 표현하면 가장 적절 할까요?

ㅋㅋㅋㅋ 자포자기지만 이거 보기보다 경우의수가 별로 없네요 ㅋㅋ 그냥 짜증나면 세버릴수도 있겟는데요 ㅋㅋㅋ

현재로서는 +3카드와 *2카드는 순서상관없이 아무때나 둘중하나가 올수있기때문에 수식적으로 표현이 가능한지 조차 의문입니다.. 아니면 수치적 계산으로 해야하는지; 역으로 계산했을때 15를 ÷2카드와 -3카드로 1을 만들수 없다는걸 보이는게 가장 빠를것 같은데 15에서 -3을하면 12. 12에서 ÷2를 하면 6. 여기서 6은 ÷2카드와 -3카드 아무거나 사용해도 3이 될수밖에없고 3에서 1이 되는 방법은 없다... 라고 하는 방법말고는 떠오르지가 않네요; 반대로 1에서 15를 만들수없다고 보여주는건 가능성이 너무많아서 쓰기가 힘들고..

기본숫자카드1 에서*2카드와 +3카드로 만드는 숫자집합을 찾는것도 방법이긴 한데

반대로 만들수 없는 숫자집합을 찾는게 훨신 빠르겟네요(그쪽이 경우가 적기도 하겟고...)

Factor님 ... 혹시 가능한가요?

리플이 왜이리 많나 해서 클릭해봤는데 설레였잖음

야밤에 이게 뭐하는짓들임!

ㄴ 지금보니 한시간반 지낫군요
슬슬 자긴 해야하는데... 눈감아도 이 문제가 아른거릴듯 ㅋㅋ

수형도로 그리면 가능합니다.. 그리다가 도중에 발견했는데.
(왼쪽이 *2한거 오른쪽이 +3한거입니다.. 보기어려울수도있어요. 그리시는게 빠를지도)
1에서 한개의 카드를 적용하면 2또는 4가 나오고
2또는 4에서 각각 한개의 카드를 적용하면 4,5,8,7이 나옵니다.
4,5,7,8에서 한개의 카드를 적용하면 8,7,10,8,16,11,14,10이 나옵니다.
일단 여기서 남은 숫자들은 순서대로 쓰면 7,8,10,11,14,16입니다.
16은 15를 초과했기때문에 탈락.(15를 넘으면 +3 *2를 해도 15가될수없죠)
14의 경우 17과 28이 되기때문에 탈락.
11의 경우 14와 22가 되는데 14가 안되는건 위에서 보였으므로 탈락.
10의 경우 13과 20이 되는데 이 경우 13에서 다시한번 적용하면 16과 26이되므로 탈락.
8의 경우 11과 16이 되는데 위에서 둘다 안됨을 보였으므로 탈락.
7의 경우 10 과 14가 되는데 이 또한 위에서 둘다 안됨을 보였으므로 탈락.

결과적으로 1에서 +3과 *2를 아무리이용해도 15를 만들수없습니다.

8,7,10,8,16,11,14,10 에서 8,7,10,8,14,10,16,11이라고 썻어야 보기 쉬운건데; 위에 (왼쪽이 *2한거 오른쪽이 +3한거입니다)라고 써놓고도 순서잘못썼네요. 어쩄든 계산은맞으니..

어쨌든 결과적으로 1로 +3과 *2를 이용해서 만들수있는 수의 집합은
{1,2,4,5,7,8,10,11,13,14,16.. 등등} 입니다. 따라서 15는 만들수없음..

factor님처럼 하시면 될꺼 같은데 -ㅛ-;;
15 에서 1로 줄어가는 식으로
조건상 숫자가 정수여만 하므로 처음에는 ÷2를 사용할수 없고 -3을 하면
12 .
1) 12에서는 ÷2 또는 -3 가능
÷2인경우 6 또다시 ÷2 또능 -3 가능하나 두경우 모두 3
3에서 ÷2를 사용할수 없으며 -3일경우 0이 됨으로 사용 불가
다시 1)로 돌아가서
12에서 -3을 하면 9
9에서 ÷2을 사용할수 없음으로 다시 -3
6은 ÷2과 -3을 사용할수 있으나 3이 나와서 위의 식과 같음;;;;;

수형도를 검색해보고 어떤건지 감이 오네요 ㅎㅎ
근데... 이 수형도, 그냥 경우의수를 직접 찾는거랑 비슷한 논리 같네요 ^^;;
다만 정리가 더 쉬울거 같군요!

아... 쓰고보니 왜 3의배수만 없지했는데
1은 3n+1꼴.
3k+1은 +3을 해도 3n+1꼴.
3k+1을 *2하면 6k+2로 3n+2꼴이 됨.
3k+2를 +3 해도 3n+2꼴이고
3k+2를 *2 해도 6k+4 = 3(2k+1)+1 이라서 3n+1꼴이 되죠.
따라서 3n+1꼴인 1에다가 +3 *2를 아무리 해봐도 무조건 3n+1또는 3n+2꼴이 되므로 3n꼴인 15는 절대로 나올수가 없습니다.

으잌 ㅋㅋ 어쩐지 3의 배수가 안나온다 싶었어...
만들수 없는 숫자 조합이 더 간단한 거였어...

네. 저도 결과를 보고서야 알아차렸는데.. 3의배수는 절대로 만들수없네요. 글자에 적용해도 b나 bb같은글자를 만들수없으니..

하지만 남는 의문 : 저걸 "수학적"으로 푼 초딩은 몇명일지... ㅋㄷ
약간의 추상적(카드라던가...)으로 푸는게 더 빠를듯 한데 ...
이제 자러 가죠 . . .
수고 하셨어요 Factor 님 ㅎㅎ

15에서 역행할때도 ÷2나 -3을 쓰면 반드시 3의배수인 수만나오네요.. 결과적으로 3의배수가아닌수에서 +3와*2를 이용하여 3의배수로 가는방법이나 3의배수에서 -3와÷2를 이용하여 3의배수가아닌수로 가는방법은 없네요.

저도 자러가야겠네요 =ㅅ=// LoreSin을 비롯해서 pres티아, 포더윈터님 등 많은 분들 수고하셨습니다.. 그리고 링크를 따라가보니 초등학교 문제는 아니고 이글에서 제목만 그렇게 붙인듯 싶네요 ㅋㅋ.. International Mathematical Talent Search 문제라는데 구글링해도 답지도 안나옴 -ㅅ-;;

뭐야이거 몰라 무서워

어라 이제 끝낫나여? 저는 걍 포기했는데 톨님 말처럼 그냥 초딩수학 종결할려고 멋대로 지어낸거엥여ㅋ

바바바 바바바 바바바 바바바바바바바바바바바바바바바바바바바바바바바바바ㅏ바바밥바바ㅏ밥바바바

테트리스네

답지도 없는 문제 였군요...
하지만 xper 들에게 불가능은 없다... 응?

이, 이게뭐야!

LoreSin님께서 처음에 가정을 할때 a->1 b->3으로 보고 푸셨고 결국 그걸로 어제밤엔 끝을냈는데... b를 3으로 볼수있는지가 계속 걸려서 (aaa->b는 되는데 b->aaa가 안되기때문에) 이래저래 생각하다가 완벽한 방법을 찾은것 같아서 마지막으로 쓰고갑니다.

주어진 법칙 4개 중 a의 갯수에 영향을 줄 수 있는 법칙은 (2)와 (4)뿐입니다.
a의 갯수만을 생각했을때 (2)와 (4)는 a의 갯수를 -3하거나 *2만 할 수 있습니다.

최초의 단어 a 로 부터 모든 언어가 파생되야 하는데 "최초의 단어 a"는 a의 갯수가 1개.
그리고 문제에서 주어진 단어 baabaabaa는 a의 갯수가 6개.
즉 1에서 -3과 *2를 아무리해도 6을 만들수 없다는 것을 증명하면 됩니다.(어차피 b는 a로 변환이 불가능하므로 a의 갯수에 영향을 줄 수 없음)

위 댓글에 수형도와 집합, 역행, 3의배수 등등 여러가지 방법으로 이와 비슷한 증명을 했었는데 이 중에서 가장 일반적이고 보편적으로 쓰일수 있는 3의배수를 이용한 방법으로 다시 한번 증명해보겠습니다.

모든 자연수는 3n, 3n + 1, 3n + 2 이렇게 3가지 꼴로 분류가 가능합니다.
여기서 3n + 1꼴인 1로부터
3n꼴인 6을 만들수 없다는걸 증명해봅시다.
(문자가 헷갈리지 않도록 '꼴'을 나타낼때는 n을, 그 외의 경우에는 k를 사용하겠습니다.)

3k + 1을 -3하면 3k - 2 = 3(k-1) + 1 따라서 3n + 1꼴.
3k + 1을 *2하면 6k + 2 = 3(2k) + 2 따라서 3n + 2꼴.
3k + 2를 -3하면 3k - 1 = 3(k-1) + 2 따라서 3n + 2꼴.
3k + 2를 *2하면 6k + 4 = 3(2k+1) + 1 따라서 3n + 1꼴.

즉, 3n+1꼴에서 -3과 *2를 아무리이용해도 3n+1꼴이나 3n+2꼴만 만들수 있고, 3n꼴은 만들수 없습니다.

결과적으로 주어진 4개의 법칙만으로는 a의 개수가 3의배수인 단어를 만들 수 없습니다.
(그 증거라고 하긴 뭐하지만 문제에서 예시로 준 단어들도 모두 a의 갯수가 3의배수가 아닙니다.)
따라서 주어진 baabaabaa는 단어가 아닙니다. ㅇㅅㅇ//

베플에 달려있는 조건부터 시작하면

(2) b는 aaa로 대체가 가능하다.

(2) 조건때문에 주어진 문자는 a로 표현이 가능하다.
주어진 문자에 들어있는 a의 갯수를 N으로 표시하면
주어진 조건은 아래와 같이 쓸 수 있다.
(1) 우측에 b가있다면 뺄수있다. => N = N - 3
(3) 아무데나 bbb를 만들수있다. => N = N + 9
(4) 같은 구획이 반복될때 반을 없앨수있다. => N = N / 2, (N은 짝수)

이 문제는 N이 주어졌을 때 (1), (3), (4)의 수식을 사용하여 N = 1이 되는지
판별하는 문제로 바꿀 수 있다.

(1), (3), (4) 수식을 아래와 같이 정리하면,
N = N - 3 ... (a)
N = N + 9 => N = N + 3과 동일 ... (b)
N = N / 2 , (N은 짝수) ... (c)

먼저, N = 3K (K는 양의 정수)인 경우
K가 홀수면 3K도 홀수 이기 때문에 (a)나 (b)의 수식만 사용할 수 있다.
(a) 수식을 사용하면 N = 3(K-1)의 형태가 되고 이것은 3K와 동일한 형태이기 때문에 N은 1이 될 수 없다.
(b)도 (a)와 마찬가지이다.
K가 짝수인 경우는 수식 (a)나 (b)를 사용하면 원 형태에서 변하지 않기 때문에 1이 될 수 없고
(c) 수식을 사용했을 경우 N = 3(K/2)의 형태가 되기 때문에 3K의 형태를 벗어나지 못한다.
즉, N = 3K인 경우는 1이 될 수 없다.

N = 3K + 1인 경우는 수식 (a)를 K번 적용하면 1이 된다.

N = 3K + 2인 경우는 수식 (a)를 K번 적용하고 수식 (c)를 1번 적용하면 1이 된다.


주어진 문자열은 N = 15 = 3*5 이기 때문에 단어가 아니다.

증명 끝.