Eu costumo chamar a atenção dos alunos para os problemas interessantes de ciência da computação que são fáceis de explicar, tais como:
1) Torre de Hanói (eu também tenho o brinquedo que comprei para minha filha - quem sabe ela se interessa (:-))
2) problema da mochila
3)O problema das 8 moedas, onde uma delas é falsa e mais leve, e para te ajudar a descobrir você tem uma balança com dois pratos.
Eu também gosto de falar sobre problemas úteis na prática, tais como
1) aprendizagem por reforço (eu gosto do exemplo de precificação dinâmica de passagem aérea)
2) computação humana (problemas como rotular imagens, recaptcha)
3) o reconhecimento de padrões (por exemplo, o reconhecimento de faces)