Sprague-Grundy Theorem (1) - Grundy Number의 정의, theorem 증명

Grundy Number는 PS에서 굉장히 자주 쓰이는 데 비해 그 증명이나 수학적 배경이 잘 알려져 있지 않다. 앞으로 일련의 포스팅에서는 Sprague-Grundy Theorem에 대해 공부한 것을 PS 스타일로 정리하려 한다. 그 중에서 이 글은 Grundy Number의 정의와 Sprague-Grundy theorem의 증명에 대해 다룬다.

March 7, 2020 (Read More...)

Dimension of Vector space sum

Vector space 의 subspace 에 대해 다음의 결과는 잘 알려져 있다. 오늘은 이 결과를 증명하고, 이 정리의 확장과 관련된 유명한 반례를 소개한다.

March 5, 2020 (Read More...)

SEEMOUS 2019

SEEMOUS 2019를 풀어보았다. 몇몇 문제는 풀이를 검증하기 위한 배경 지식이 부족해서 나중에 자세히 다루기로 한다.

March 3, 2020 (Read More...)

ARC069 F. Flags

수직선상에 깃발 개를 놓되, 번째 깃발은 또는 에 놓아야 한다. 이 때 깃발들 사이의 최소 거리의 최댓값을 구하는 문제이다. 문제 링크

January 8, 2020 (Read More...)

Cayley’s theorem in combinatorics

조합론에서의 Cayley’s theorem은 완전그래프 의 서로 다른 spanning tree가 개라는 정리이다. 일반적으로는 그 쓰임보다도 아름다운 증명에 가치를 둔다. Functional graph를 알고 있다는 전제 하에 글을 작성했다.

December 11, 2019 (Read More...)