Ну с доказательством вроде просто. Разделим все пространство на 8 областей:
11233344
12223544
66275558
66777588
В каждой области должен быть хотя бы один лжец. В противном случае правдолюб, сидящий в "центре" это области не сможет обнаружить соседа-лжеца.