크루스칼 카운트
Kruskal count
크루스칼[1][2][7][8][9][10] 카운트(Kruskal count[3][4][5][6])[11]는 1970년대 초 수학자 마틴 데이비드 크루스칼이 다른 [12]문제를 연구하던 중 부차적인 산물로 재발견한 카드 [7][8][9][10]트릭입니다.그것은 그의 친구[13] 마틴[14][1] 가드너와 마술사 칼 풀브스에 의해 [15]1975년에 출판되었습니다.그것은 마술사 알렉산더 F. 크라우스가 1957년에 Sum[16][17][18] total로 발표했고 나중에 크라우스의 [2][12]원리라고 불린 비슷한 속임수와 관련이 있습니다.
카드 트릭으로 사용하는 것 외에도, 근본적인 현상은 암호화, 코드 파괴, 코드 자체 동기화 등에 응용됩니다.
카드 트릭
그 마술은 카드로 행해지지만, 전통적인 마술보다 더 마술처럼 보이는 효과입니다.마술사는 관객들에 의해 조작되는 카드에 접근할 수 없습니다.따라서 손놀림은 불가능합니다.오히려 효과는 특정 조건에서 마르코프 체인의 출력이 일반적으로 [19][20][21][22][6]입력과 독립적이라는 수학적 사실에 기초합니다.시계 바늘을 이용한 간단한 버전은 [23]다음과 같습니다.한 자원봉사자가 1에서 12까지의 숫자를 골라 마술사에게 공개하지 않습니다.자원봉사자들은 시계의 12시부터 시작해서 선택한 숫자가 철자를 쓸 때 가지고 있는 글자 수와 동일한 숫자만큼 시계 방향으로 움직이도록 지시를 받습니다.그런 다음 이 작업을 반복하여 새 숫자의 문자 수만큼 이동합니다.세 번 이상 이동한 후의 출력은 처음에 선택한 숫자에 따라 달라지지 않으므로 마술사가 예측할 수 있습니다.
참고 항목
레퍼런스
- ^ a b Gardner, Martin (February 1978). "On checker jumping, the Amazon game, weird dice, card tricks and other playful pastimes". Scientific American. Mathematical Games. Vol. 238, no. 2. pp. 19–32. ISSN 0036-8733.
- ^ a b 가드너, 마틴 (1989).Penrose Tiles to Trapdoor Ciphers... 그리고 Mr. Matrix의 귀환 (1st.).W. H. 프리먼 페이지 274; 가드너, 마틴 (1997)."19장.시허먼 주사위, 크루스칼 백작과 다른 호기심."Penrose 타일 투 트랩도어 암호... 그리고 Mr. Matrix (PDF)의 귀환.스펙트럼 시리즈(개정판).Washington, D.C., 미국: 미국 수학 협회. 페이지 265–280 [280].ISBN 0-88385-521-6. LCCN 97-70505.2023-08-19년 원본에서 보관(PDF).2023-08-19를 검색했습니다. (1+ix+319페이지)
- ^ 하가, 웨인; 로빈스, 시나이 [위키데이터에서] (1997년 6월) [1995-12-12]."크루스칼의 원리에 대하여"유기 수학.캐나다 수학 학회 회의 진행.제20권.캐나다 브리티시컬럼비아주 버너비의 사이먼 프레이저 대학:미국 수학회 407-411페이지.ISBN 978-0-8218-0668-5. LCCN 97-179.ISBN 0-8218-0668-8입니다.2023-08-19를 회수했습니다. (5페이지)
- ^ a b 폴라드, 존 M. (1978년 7월) [1977-05-01, 1977-11-18]."색인 계산을 위한 몬테카를로 방법 (modp)" (PDF).계산의 수학.영국 버크셔 메이든헤드 태플로 코트(Taplow Court), 플레시 텔레커뮤니케이션 연구소 수학과 32 (143): 918–924.ISSN 0025-5718.2013-05-03 원본에서 보관(PDF).2023-08-19를 회수했습니다. (7페이지)
- ^ a b Pollard, John M. (2000-08-10) [1998-01-23, 1999-09-27]."캥거루, 독점 및 이산 로그"(PDF).암호학 저널.영국, Tidmash, Manor Farm Lane, Tidmash Cottage, Tidmash, Reading: 국제 암호 연구 협회. 13 (4): 437–447. doi: 10.1007/s001450010010.ISSN 0933-2790.2023-08-18년 원본에서 보관(PDF).2023-08-19를 회수했다. (11페이지)
- ^ a b c Pollard, John M. (July 2000). "Kruskal's Card Trick" (PDF). The Mathematical Gazette. Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, UK: The Mathematical Association. 84 (500): 265–267. ISSN 0025-5572. JSTOR 3621657. 84.29. Archived (PDF) from the original on 2023-08-18. Retrieved 2023-08-19. (1+3페이지)
- ^ a b Barthe, Gilles [Wikidata] (2016)."암호화 및 개인 정보 보호를 위한 확률적 결합"(PDF).스페인 마드리드: IMDEA 소프트웨어 연구소.2023-08-19년 원본에서 보관(PDF).2023-08-19(66페이지); 바테, 길레스 [위키데이터에서](2016-09-13)을 검색했다."암호화 및 개인 정보 보호를 위한 확률적 결합"(PDF).스페인 마드리드: IMDEA 소프트웨어 연구소.2023-08-19년 원본에서 보관(PDF).2023-08-19를 회수했습니다. (49페이지
- ^ a b Barthe, Gilles [at Wikidata]; Grégoire, Benjamin [at Wikidata]; Hsu, Justin; Strub, Pierre-Yves (2016-11-07) [2016-09-21]. "Coupling Proofs are Probabilistic Product Programs". arXiv:1607.03455v5. Archived from the original on 2023-08-19. Retrieved 2023-08-19. (14페이지)
- ^ a b 바르테, 길레스 [위키다타];에스피타우, 토마스, 그레고아르, 베냐민[위키다타];쉬, 저스틴, 스테파네스코, 레오, 스트럽, 피에르 이브 (2017-07-12) [2015]."확률론적 결합을 통한 관계적 추론".프랑스 수바: LPAR. 페이지 387–401. doi: 10.1007/978-3-662-48899-7_27. hal-01246719v2.2023-08-19년 원본에서 보관.2023-08-19를 회수했습니다. (17페이지)
- ^ a b Hsu, Justin (2018) [2017-11-01]. "Probabilistic Couplings for Probabilistic Reasoning" (PDF) (Thesis). p. 34. Archived (PDF) from the original on 2023-08-19. Retrieved 2023-08-19. (304페이지)
- ^ Artymowicz, Pawel [in Polish] (2020-01-29) [2020-01-26]. "Codes for PHYD57 Advanced Computing in Physics, UTSC: Dynkin–Kruskal count - convergent Markov chains". Archived from the original on 2023-08-20. Retrieved 2023-08-20.
[…] We looked at the Markov chains, where a given random sequence of cards or numbers is traversed in a linked-list manner, that is when you see a value in a list of integers, you use it to determine the position of the next number in a sequence, and you repeat that until the list ends. This is the basis of a card trick with a magician correctly guessing the final number in a seemingly hidden/random sequence computed by a spectator in his/her mind (but using a given well-shuffled deck of 52 cards. […] Random sequences that converge when the length of element is used to create a jump to the next element are called Dynkin–Kruskal sequences, after Eugene Dynkin (1924–2014), a Russian-American mathematician, who mentioned them in his work, and American mathematician Martin David Kruskal (1925–2006). The nature of these Kruskal sequences is that they converge exponentially fast, and for N=52 there is already more than 90% chance that the two randomly started sequences converge at the end of the deck, that is the magician and the spectator independently arrive at the same last key card. I saw the trick demonstrated […] at one conference, but didn't know that these convergent, linked list-like, series are so common. Almost any books can be used to show that. Skip a number of words equal to the number of letters in a key word. By the end of the third line you normally converge to the same sequence forever after, no matter which word in the top line you start with. […]
[2][3][4] - ^ a b c d 니시야마, 유타카 (2013년 7월) [2012-12-10]."크루스칼 원리" (PDF).국제 순수 및 응용 수학 저널.일본 오사카 오사카 경제대학 정보경영학부 경영정보학과: 학술출판사 85(6): 983-992. doi: 10.12732/ijpam.v85i6.1. eISSN 1314-3395.ISSN 1311-8080.2023-08-19년 원본에서 보관(PDF).2023-08-19를 회수했습니다. (10페이지)
- ^ 파렐, 예레미야 (2010)."Foshee Magic Interpreted".인디애나폴리스, 인디애나, 미국 페이지 316쪽.2023-08-19년 원본에서 보관.2023-08-19 페이지 316: 크루스칼에게는 수학적 성향의 두 형제가 있었는데, 시카고 대학의 윌리엄과 벨 연구소의 조셉이었다.세 사람 모두 마틴 가드너의 친구들로, 그들의 어머니 릴리언 오펜하이머에 대해 일찍이 글을 쓴 적이 있다. (1페이지)
- ^ Gardner, Martin (June 1975). "The Kruskal Principle". The Pallbearers Review. Vol. 10, no. 8. L&L Publishing. pp. 967–, 985; Braunmüller, Rudolf, ed. (January 1984). "Das Kruskal-Prinzip" [The Kruskal Prinpicle]. intermagic - Ein Magisches Journal (in German). Vol. 10, no. 3 & 4. Munich, Germany. p. 125.
- ^ Fulves, Karl (June 1975). "Kruskal Phone Effect". The Pallbearers Review. Vol. 10, no. 8. L&L Publishing. pp. 970–.
- ^ Kraus, Alexander F. (December 1957). Lyons, P. Howard (ed.). "Sum Total". ibidem. No. 12. Toronto, Ontario, Canada. p. 7 (232). Part 1 (Problem).
- ^ Kraus, Alexander F. (March 1958). Lyons, P. Howard (ed.). "Sum Total". ibidem. No. 13. Toronto, Ontario, Canada. pp. 13–16 (255–258). Part 2 (Solution).
- ^ Ransom, Tom; Katz, Max (March 1958). Lyons, P. Howard (ed.). "Sum More". ibidem. No. 13. Toronto, Ontario, Canada. pp. 17–18 (258–259).
- ^ Lagarias, Jeffrey "Jeff" Clark; Vanderbei, Robert J. (1988). The Kruskal Count. Murray Hill, New Jersey, USA: AT&T Bell Laboratories.
- ^ a b 라가리아스, 제프리 "제프" 클라크, 레인스, 에릭 마이클, 밴더베이, 로버트 J. (2009) [2001-10-13].브람스, 스티븐, 게를린, 윌리엄 V., 로버츠, 프레드 S. (ed.)."크루스칼 백작".선호, 선택, 질서의 수학.피터 J를 기리는 에세이.피시번.베를린 / 하이델베르크, 독일: Springer-Verlag: 371–391. arXiv: 수학/0110143. doi: 10.1007/978-3-540-79128-7_23.ISBN 978-3-540-79127-0. (22페이지)
- ^ a b 야곱, 마티아스, 야쿠보스키, 마리우스 H., 벤카테산, [위키다타] (2007년 9월 20일-21일).통합 이진 실행 방향:중첩 명령 인코딩을 사용한 망각 해싱 구현(PDF).제9회 멀티미디어 & 보안 워크숍(MM&Multimedia & Security) 진행 상황;07절).미국 텍사스주 달라스: Association for Computing Machine. 129–140 페이지.SeerX 10.1.1.69.5258. doi:10.1145/1288869.128887을 인용한다.ISBN 978-1-59593-857-2입니다.S2CID 14174680.2018-09-04 원본에서 보관(PDF).2021-12-25 검색 완료. (12페이지)
- ^ Paulos, John Allen (November 1998). "An old card trick and new Biblical hoax". Once Upon a Number - The Hidden Mathematical Logic of Stories (1 ed.). Basic Books. p. 64. ISBN 978-0-46505159-5. Archived from the original on 2015-04-01.
- ^ Delbert, Caroline (2020-02-27). "How to Do the Math Magic Trick That Will Impress Everyone You Know - Here's the secret". Popular Mechanics. Archived from the original on 2021-10-19. Retrieved 2021-12-25.
- ^ Jakubowski, Mariusz H. (February 2016). "Graph Based Model for Software Tamper Protection". Microsoft. Archived from the original on 2019-10-31. Retrieved 2023-08-19.
진일보한 내용
- Marlo, Ed (1976-12-01). Written at Chicago, Illinois, USA. Hudson, Charles (ed.). "Approach & Uses for the "Kruskal Kount" / First Presentation Angle / Second Presentation Angle - Checking the Deck / Third Presentation Angle - The 100% Method / Fourth Presentation Angle - "Disaster"". Card Corner. The Linking Ring. Vol. 56, no. 12. Bluffton, Ohio, USA: International Brotherhood of Magicians. pp. 82, 83, 83, 84, 85–87. ISSN 0024-4023.
- Hudson, Charles (1977-10-01). Written at Chicago, Illinois, USA. "The Kruskal Principle". Card Corner. The Linking Ring. Vol. 57, no. 10. Bluffton, Ohio, USA: International Brotherhood of Magicians. p. 85. ISSN 0024-4023.
- 하빌, 줄리안 R. [독일어] (2008).무리인가반직관적인 수수께끼에 대한 놀라운 해결책 (1판).Princeton, New Jersey, 미국: Princeton University Press.ISBN 978-0-691-13131-3. JSTOR j.ctt7rnph.LCCN 2007051792.2023-08-19. (xii+235페이지);하빌, 줄리안 R. [독일어] (2009).Das gibts dochnicht – 수학자 Rettsel [불가능?반직관적인 수수께끼에 대한 놀라운 해결책] (독일어) (1판).Spektrum Academischer Verlag.ISBN 3-8274-2306-6입니다.ISBN 978-3-8274-2306-1입니다.
- Montenegro, Ravi [at Wikidata]; Tetali, Prasad V. (2010-11-07) [2009-05-31]. How Long Does it Take to Catch a Wild Kangaroo? (PDF). Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC 2009). pp. 553–560. arXiv:0812.0789. doi:10.1145/1536414.1536490. S2CID 12797847. Archived (PDF) from the original on 2023-08-20. Retrieved 2023-08-20.
- Grime, James [at Wikidata] (2011). "Kruskal's Count" (PDF). singingbanana.com. Archived (PDF) from the original on 2023-08-19. Retrieved 2023-08-19. (8페이지)
- Bosko, Lindsey R. (2011). Written at Department of Mathematics, North Carolina State University, Raleigh, North Carolina, USA. "Cards, Codes, and Kangaroos" (PDF). The UMAP Journal. Modules and Monographs in Undergraduate Mathematics and its Applications (UMAP) Project. Bedford, Massachusetts, USA: Consortium For Mathematics & Its Applications, Inc. (COMAP). 32 (3): 199–236. UMAP Unit 808. Archived (PDF) from the original on 2023-08-19. Retrieved 2023-08-19.
- Mannam, Pragna; Volkov, Jr., Alexander; Paolini, Robert; Chirikjian, Gregory Scott; Mason, Matthew Thomas (2019-02-06) [2018-12-04]. "Sensorless Pose Determination Using Randomized Action Sequences". Entropy. Basel, Switzerland: Multidisciplinary Digital Publishing Institute. 21 (2): 154. arXiv:1812.01195. doi:10.3390/e21020154. ISSN 1099-4300. PMC 7514636. PMID 33266870. S2CID 54444590.
