Senadores en un senado utilizando el principio de encasillamiento. (NOTA: no es un duplicado, sólo una aclaración)

Question

Hay $30$ senadores en un senado. El senado tiene que estar dividido en $n$ comités de manera que cada senador esté en exactamente un comité. Cada senador odia exactamente $6$ otros senadores y es odiado exactamente por $6$ senadores. (Si el senador A odia al senador B, entonces el senador B no necesariamente odia al senador A). Encuentra el menor valor de $n$ de manera que siempre sea posible organizar las comisiones de forma que ningún senador odie a otro en su comisión.

Sí, lo sé, ya hay una pregunta hecha así, pero lo que REALMENTE quiero es aclarar la respuesta de la otra pregunta similar en el sitio: Encasillamiento: Comité de senadores que se odian entre sí

¿Siempre empieza con $7$ al adivinar el número de comités posibles? ¿O existe una fórmula o regla que indique por qué número hay que empezar a adivinar? La respuesta se refiere a algo llamado "hipótesis de inducción", pero no estoy familiarizado con ella, así que podría ser de gran ayuda si alguien explica estas cuestiones.

No se trata de encontrar la respuesta a la pregunta del primer párrafo, sino de profundizar en el método y la solución para resolver esta cuestión. Cualquier ayuda será maravillosamente apreciada.

)

Answer 1

La inducción es la idea de que para los números naturales $\Bbb N$ (así $1,2,3 \cdots$ ), si podemos demostrar que una afirmación es verdadera para cualquier número natural y también para el número genérico $n + 1$ , entonces es cierto para todos los números naturales. La hipótesis de inducción, concretamente, significa que demostramos para algún caso mínimo (en este problema, $7$ ), entonces asume (aka, hipotetizar ) que es cierto para algún número natural genérico $n$ . Si podemos entonces demostrar que si es cierto para $n$ siempre es cierto para $n + 1$ entonces es cierto para todos los números naturales (porque hemos demostrado que es cierto para $7$ , por lo que si dejamos que $n = 7$ entonces hemos demostrado que también es cierto para $8$ Así pues, para $9$ etc.)

Su otra pregunta, sobre por qué 7, se discute en los comentarios de la respuesta a su pregunta vinculada - la respuesta utiliza 7 porque la solución dada en la pregunta dice 7, y luego hay más discusión sobre cómo uno encontraría que es 7 sin ya saber eso - la respuesta de sTertooy da un enfoque muy intuitivo de por qué 6 o menos no funcionaría.