본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[슬기로운 수학생활] 슬26. 모든 전등의 불 켜기
수학동아 2022.06.01 09:47 조회 635

슬기로운 수학생활 26번

 

 

 

모든 전등의 불 켜기

 

 

 

문제 출제자 : 백진언 미시간 대학교 수학과 박사과정생

 

 

 

 

단순그래프 G가 있어요.

 

 

(단순그래프의 정의와 기초 용어는 대한수학회 12번 문제나 인터넷 검색을 참고하기 바랍니다.)

 

 

단순그래프 G의 각 점에는 전등과 스위치가 하나씩 있어요. 점 v에 있는 스위치를 누르면, 점 v에 있는 전등과 v와 인접한 모든 점들에 있는 전등이 상태를 바꿉니다. 즉 켜진 전등은 꺼지고, 꺼진 전등은 켜져요. 

 

 

처음엔 모든 전등의 불이 꺼져 있어요. 스위치 몇개를 잘 누르면 항상 모든 전등의 불을 켤 수 있음을 보이세요.

 

 

 

 

백진언 연구원의 팁

문제를 법 2에 대한 합동식(modulo 2)으로 생각하면 연립일차방정식으로 바꿀 수 있어요. 모르는 용어가 있어도 괜찮습니다. 용어를 찾아서 공부하는 것부터 시작해보세요!

 

 

 

 

  •  
    다시 도전
    RedoC Lv.5 2022.06.04 19:06 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      강지원 멘토 Lv.4 2022.06.07 11:20

      rank(H)=rank(H|X)이므로 해가 존재 <-- 이 부분에 대한 설명이 조금 더 이루어지면 좋을 것 같습니다.

      좋아요0
    •  
      RedoC Lv.5 2022.06.07 16:32

      으아 오타가 있었네요 수정 후 올리겠습니다

       

      좋아요0
  •  
    다시 도전
    RedoC Lv.5 2022.06.07 16:39 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      출제자(슬기) Lv.4 2022.06.09 06:12

      왜 하필 그래프를 표현한 행렬 H에 대해서 rank(H) = rank(H|B)인지에 대한 서술이 없어 보입니다. 이를테면 H가 영행렬이면 rank(H)랑 rank(H|B)랑 다른데, 이런 일이 왜 그래프에서 나오는 H에서는 일어나지 않는지 설명이 필요해요!

      좋아요0
  •  
    pure math Lv.6 2022.06.09 21:32 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    구머 Lv.5 2022.06.12 03:46

    수학적 귀납법으로 접근하자. 즉, node의 개수 n에 대해, n<=k-1일때 문제의 명제가 성립한다고 가정하자. 이때, k=2^r x t라고 하자.(t는 홀수)

    이제, node 2^r, node 2^r x 2, node 2^r x 3, ... , node 2^r x t에 대해, 각 node를 제외한 모든 node에 불이 들어오게 하는것이 귀납적 가정에 의해 가능하다. 이때 각 node 2^r x b를 제외한 모든 전구를 키게 하는 버튼의 조합을 Ab​​​​​​라고 하자. 만약 A1, A2, ..., At중 운좋게 모든 운좋가 다 켜지는 경우가 있다면, 명제가 자동으로 성립한다. 만약 모든 경우에 개해 각각 node 2^r, node 2^r x 2, ... , node 2^r x t가 불이 안들어온다면, A_1, A_2, ... A_t를 모두 mod 2에서 더한 조합을 누르면, t가 홀수이기 때문에 

    어라 홀짝성 안맞네... 이 방법은 k 짝수때만 되는걸로.

    홀수는 살짝 생각을 해봐야겠군요.

    댓글 작성하기 좋아요0 댓글수2
    •  
      구머 Lv.5 2022.06.12 03:50

      음, 위 방식 그대로 구멍 하나 난 배치로부터, 임의의 노드 2개를 텨지게 할 수 있다는 lemma가 나오고-

      이래서 짝수가 자명이고.

      홀수는 degree가 짝수인 점이 나오는 순간 바로 풀리군요

      좋아요0
    •  
      구머 Lv.5 2022.06.12 03:53

      아, 근데 degree합 특이 항상 짝수인데.

      Node개수 홀수 그래프가 모두 각 degree가 홀수이면 모순이 발생, 따라서 해결.

      좋아요0
  •  
    구머 Lv.5 2022.06.12 04:00
    확인요청중

    정리:

    귀납적으로 n<=k-1일때 명제가 성립한다 가정. 이제 node k개인 그래프 G에 대헤, 각 node 1, 2, ..., k에 대해 각 node i를 제외한 모든 node에 불이 들어오게 버튼을 누를 수 있음. 만약 이렇게 버튼을 눌렀는데 아다리가 잘 맞아서 node i도 같이 눌린다면 즉시 귀납적으로 명제가 성립.

    (가정 A) 이제, 위의 시행에서 각 노드 i에 대해 i가 눌리지 않았다고 가정. 이러면 각각 node i를 제외하고 모두 불이 들어오게 누르는 버튼 조합, node j를 제외하고 불이 들어오게 하는 버튼 조합을 합치면 임의의 node i, j에 불이 들어오게 할 수 있음. 따라서 k가 짝수인 경우는 자명하게 명제가 성립. K가 홀수인 경우, 각 node의 degree합이 짝수이므로 어떤 node i는 degree가 짝수, 즉 그 node를 누르면 홀수개의 node에 불이 들어옴. 이때 이제 남은 불 안켜진 node는 짝수개이고, 이는 위의 property로 인해 성립. 즉, 가정 A가 거짓, 즉 어떤 node i를 잘 고르면, node i를 제외하고 불이 모두 켜지게 했을 때 i도 슬쩍 꼽껴서 같이 켜진다.

     

    따라서 귀납적으로 문제의 명제가 성립. QED

    댓글 작성하기 좋아요1 댓글수2
    •  
      강지원 멘토 Lv.4 2022.06.17 01:31

      잘 풀었습니다!

      좋아요0
    •  
      구머 Lv.5 2022.06.17 23:57

      세상에, 술 먹고 쓴 탓에 중간중간 풀이에 이상한 단어들이 보이네요...

      심지어 이미 확인요청을 해서 수정이 불가능하군요. 혹시 풀이를 읽어보신 분들은 양해 부탁드립니다..  :<

      좋아요0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911