한 자리 숫자는 증가, 감소, bouncy가 있을 수 없으므로 10부터 시작해서 솟자를 계속 키워나가면서 증가수, 감소수, bouncy number를 판별하게 구성하면 된다.
구성할 때 한 가지 고려할 것은 이전 숫자와 값이 같으면 아직 증가수인지 감소수인지 판별을 유보해야 한다는 것이다. 처음에 이 부분을 잘못 생각하고 유보할 때 증가수, 감소수 플래그를 무조건 True로 값을 넣도록 프로그램을 만들었는데, 3자리에서는 유효하지만 4자리 숫자에서 오류를 만들게 되어 있어서 판별할 숫자를 50%만 제시했으면 이유를 찾지 못할뻔 했다. (값이 같을 때 이전에 증가수/감소수로 판별된 경우 이전 판별을 유지해야 되는데 잘 못 생각해서 계속 유보하게 만든 것이 문제였다)
해결할 아이디어가 떠오르지 않아 찾아보니 고1 정도의 수학 지식을 필요로하는 문제였다. 벡터를 이용, 삼각형 면적 이용, 도형(삼각형)과 교차하는 점의 갯수, 무게중심좌표 등 해결하는 방법은 몇 가지가 있는데 개념은 알겠는데 실제 어떤 형태로 구현할 것인지는 쉽지 않았다.
이 중 무게중심좌표(Barycentric Coordinate System)를 이용한 해법으로 답을 구했다. 삼각형 세 꼭지점의 좌표를 (x1,y1), (x2, y2), (x3, y3)라 하고, 원점을(xp, yp)라 할 때, 다음과 같이 세 좌표를 계산해서 모두 0보다 크면 삼각형 내부에 있다고 한다.
그리고, 왜 이렇게 난이도가 올라갈까 싶었는데, 게임을 할 때 특정 좌표가 도형 내에 있는지 밖에 있는지 판단하는 방법으로 이 코드를 사용할 수 있다고 한다. 좌표가 보호막 내에 있는지 판단하거나, 게임 내의 비행체와 총알의 충돌을 판단하는 등에 사용할 것을 생각하면 이해가 필요한 것 같다.
프로젝트 오일러의 문제를 100번까지 모두 해결하는 것을 목표로 진행했는데, 몇 문제는 아이디어가 잘 떠오르지 않아 아직 해결하지 못했다. (특히 68번은 문제 자체를 이해할 수 없어 어떤 식으로 접근해야 할 지 오리무중이다) 이제는 난이도를 중심으로 해결되는 대로 포스팅할 예정이다.
100번대 이후 문제를 풀어보니, 난이도 5%도 문제대로 하면 코딩은 간단하지만 말도 안되는 수준으로 실행시간이 많이 필요하게 되어, 수학지식을 바탕으로 최적화하기를 요구하고 있는 등 적절한 방법으로 해결하는 것이 쉽지 않았다. 이제는 진짜 파이썬 공부인지 수학 공부인지 알 수 없어지는 상황이 되었지만, 그래도 최대한 해결해 볼 예정이다.
In the game,Monopoly, the standard board is set up in the following way:
A player starts on the GO square and adds the scores on two 6-sided dice to determine the number of squares they advance in a clockwise direction. Without any further rules we would expect to visit each square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.
In addition to G2J, and one card from each of CC and CH, that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.
At the beginning of the game, the CC and CH cards are shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH square.
Community Chest (2/16 cards):
Advance to GO
Go to JAIL
Chance (10/16 cards):
Advance to GO
Go to JAIL
Go to C1
Go to E3
Go to H2
Go to R1
Go to next R (railway company)
Go to next R
Go to next U (utility company)
Go back 3 squares.
The heart of this problem concerns the likelihood of visiting a particular square. That is, the probability of finishing at that square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing on it is zero, the CH squares will have the lowest probabilities, as 5/8 request a movement to another square, and it is the final square that the player finishes at on each roll that we are interested in. We shall make no distinction between "Just Visiting" and being sent to JAIL, and we shall also ignore the rule about requiring a double to "get out of jail", assuming that they pay to get out on their next turn.
By starting at GO and numbering the squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of squares.
Statistically it can be shown that the three most popular squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular squares can be listed with the six-digit modal string: 102400.
If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.
표준 보드 게임인 '모노폴리'는 위 그림과 같이 구성된다.
플레이어는 GO에서 시작하고, 육면체 주사위 2개를 굴려 나온 값만큼 시계방향으로 진행한다. 추가 규칙이 없으면 각 자리를 방문할 확률은 2.5%로 동일하다. 그러나, G2J(감옥으로 가시오), CC(보물상자), CH(기회)를 방문하면 확률은 바뀐다.
G2J를 방문하거나, CC, CH에 있는 한 장의 카드를 뽑으면 플레이어는 감옥으로 가야한다. 플레이어가 같은 숫자를 3번 연속으로 굴리지 못하면, 3번째 굴린 결과까지는 진행하지 못하고, 감옥으로 곧장 가게 된다.
게임을 시작할 때, CC, CH카드는 섞어 둔다. 플레이어가 CC, CH에 도착하면 각 파일 가장 위에 있는 카드를 뽑아, 지시사항을 따르고, 뽑은 카드는 가장 파일 가장 아래에 둔다. 각 파일에는 16개 카드가 있지만, 이번 문제의 목적을 위해 이동을 명령하는 카드만 고려하고, 이동과 관련없는 카드는 무시되고 플레이어는 CC/CH 자리에 남아있게 된다.
보물 상자 (2/16 카드):
GO로 이동하시오
감옥(JAIL)으로 가시오
기회 (10/16 카드):
GO로 이동하시오
감옥(JAIL)으로 가시오
C1로 가시오
E3으로 가시오
H2로 가시오
R1로 가시오
다음 R(열차 회사)로 가시오
다음 R로 가시오
다음 U(전력(utility) 회사)로 가시오
3칸 뒤로 가시오
이번 문제의 핵심은 특정 자리를 방문하게 될 것을 고려하는 것이다. 즉, 주사위를 굴린 후 특정 자리를 끝낼 확률을 말한다. 이런 이유로 끝낼 확률이 0인 G2J를 제외하고, CH는 5/8이 다른 자리로 이동하게 하므로 가장 낮은 확률을 가지고, 플레이어가 각 롤을 끝낼 때 우리가 관삼가지는 마지막 자리이다. 우리는 감옥의 단순 방문과 감옥으로 보내는 것에 차이를 두지 않을 것이고, 다음 순서에 나오기 위해 지불할 것이라 가정하고 "감옥에서 나오기 위한" 같은 숫자를 요구하는 규칙 또한 무시할 것이다.
GO에서 시작해서 각 자리에 번호를 00에서 39까지 매기면, 대응하는 자리 집합을 2자리 문자열을 결합하여 만들수 있다.
통계적으로, 가장 인기 있는 자리 3개를 순서대로 보면, 10번 자리인 감옥(6.24%), 24번 자리인 E3(3.18%), 0번 자리인 GO(3.09%)이다. 이 셋은 가장 인기있는 자리이고 6자리 숫자로 표현하면 102400이다.
육면체 대신 사면체 주사위를 굴릴 경우 (가장 인기있는 3자리를 결합한) 6자리 숫자를 구하시오.
부루마불이라 부르는 모노폴리를 단순화하여 문제를 만든 것인데, 문제에서 요구한 조건을 정리하면 다음과 같다.
주사위 결과에 따라 이동하는데, 같은 숫자가 3번 나오면 감옥으로 이동, 보물상자(CC)와 기회(CH)에서는 뽑은 카드 결과에 따라 이동, G2J에 가면 감옥으로 이동한다. 그 외 모노폴리에 있는 부동산 구매 등은 생략하고 이동 중심으로만 했으며, 감옥을 빠져나오는 조건도 따로 두지 않았다.
가장 많이 방문하는 3곳을 구하라는 것인데, 어떻게 할 것인지 고민하다가 주사위 2개를 랜덤하게 굴리는 형태로 많은 횟수를 실제 게임을 해서 방문하는 장소를 카운트하는 형태로 구하기로 했다. 나중에 찾아보니 이것을 몬테 카를로 방법이라 부른다고 한다.
여기까지 정리되고 나니 구현하는 것은 그렇게 어렵지 않았다. 다만, 기본값 설정 등에 있어 명확하게 하지 않은 부분에서 잘못 동작되어 처음에는 오답이 나왔었다.
If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.
The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.
By finding the first arrangement to contain over 1012= 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.
파란색 디스크 15장, 빨간색 디스크 6장으로 구성된 21장의 디스크가 있는 박스에서, 디스크 2장을 랜덤하게 선택하는 경우 2장의 파란색 디스크를 선택할 확률은 P(BB)=(15/21)x(14/20)=1/2이다.
동일한 구성으로 2장의 파란색 디스크를 랜덤하게 선택할 확률이 50%인 경우는 85장의 파란색 디스크와 35장의 붉은색 디스크로 구성된 경우이다.
총 1012= 1,000,000,000,000장 이상 디스크가 있을 때 동일한 구성으로 2장의 파란색 디스크를 랜덤하게 선택할 확률이 50%가 되는 경우는, 파란색 디스크가 몇 장 있을 때인가?
(중학생 이하 수준이지만) 갈수록 수학문제가 되고 있는 상황인데, 근의 공식을 이용하여 해결하기로 결정했다. 이전에 √를 바로 사용하면서 소숫점이 이하 자리 숫자가 있음에도 값이 너무 작아 정수로 판정되는 오류를 겪었기 때문에, 큰 수이지만 일단 제곱수인 상태에서 적용해 보기로 했다.
확률이 1/2일 때 총 디스크 수를 c, 파란색 디스크 수를 x라고 하면, P(BB)=(x/c)*((x-1)/(c-1))=1/2이며, 이것을 전개하면 2x2-2x=c(c-1), 2x2-2x-c(c-1)=0이 된다. 여기에 근의 공식을 적용하면 x=(2+(4+4*2*c(c-1))**0.5)/2*2가 되고, 루트 기호 부분 기준으로 정리하면 (4+8c(c-1))**0.5=4x-2이 되고, 양쪽을 제곱하여 루트를 없애면 1+2c(c-1)=(2x-1)2가 된다. 수학 기호를 html로 표기하는 방법이 익숙하지 않아 가독성이 나쁘게 적었지만 이와 같은 형태로 방정식을 구할 수 있다.
여기에서 c는 1조에서 시작하고, x는 좌변의 값보다 조금 작은 값이 나올 값에서 시작해서 양 변이 같을 때까지 c와 x값을 계속 키우면서 찾는 작업을 했다. 양변을 크게 보면 8*c^2와 16*x^2가 있어서 x의 시작값을 1부터 하지 않고 c/√2부터 시작해서 추적했다. 실행이 생각보다 오래 걸려서 상황을 보니 이 방법으로는 답을 구할 수 없을 것 같았다.
먼저 방법으로는 해결되지 않아 인터넷을 검색해 보니, 연분수와 비슷하게 x, c의 이전값을 통해 새 값을 찾을 수 있다고 되어 있었다. 문제에서는 (x, c) 값이 (15, 21), (85, 120)인 경우가 있었는데, (3, 4)인 경우에도 확률이 파란색 2개가 연속으로 나올 확률은 1/2가 된다.
이 (x,c)값 3쌍을 이용하여 x, c값의 다음 항에 대한 일차방정식을 유추해봤고(xn=3x+2c-2, cn=4x+3c-3), 그 공식으로 만든 숫자로 다음 값인 (493, 697) 또한 파란색 2개가 나올 확률이 1/2임을 확인해서 해당 공식을 통해 빠른 시간 내에 답을 구할 수 있었다.
일차방정식을 빨리 유추하기 위해 엑셀을 사용했는데, 엑셀로는 12자리 이상 숫자를 확인할 수 없다는 것 또한 알게 되었다.
