ಹಗುರ ತಿಳಿಗಾಳಿ

ನಿಶ್ಚಳ ಹರಿವು, ಕಾಣದ ದೂರ,

ಮೊಳಗುತ್ತಿರುವ ಉತ್ಸಾಹದ ಹಾಡು,

ಮನದಾಳದ ಚಿಲುಮೆ,

ಕಳೆದ ಮನ್ವಂತರ,

ಇಲ್ಲದ ಮನೋರಮೆ,

ಬೃಹತ್ತದು, ಸಂಕೀರ್ಣ ನಾನು,

ಧಾಟಿಯ ಹವೆಯಲ್ಲಿ ಮಿಂದ ಹಬೆಯನ್ಮೀರಿ

ಹಗುರ ತಿಳಿಗಾಳಿ

Advertisements

Some unfi nished ideas about dense subsets of a discrete set

(pdf copy)

We define the notion of {\epsilon}-dense subsets and enumerate the number {\epsilon}-dense subsets of the finite set {[n]=\{1,2,\dots ,n\}}.

1. Basic

Definition. A subset {S} {(\ne \emptyset)} of {[n]} is said to be {\epsilon}-dense if {\forall \, a\in [n]\, \exists s\in S} such that {\mid s-a\mid \le \epsilon}.

Lemma. The number of compositions of {n} with not more than {p} parts and no part exceeding {\ell} is defined as {f(n,p,l)}. By Inclusion-Exclusion principle,

\displaystyle f(n,p,l)={n+p-1\choose {p-1}}-\sum_{i=1}^{\lfloor \frac{n}{\ell +1}\rfloor} (-1)^{i+1} {p\choose i}{n-(\ell +1)i +p-1\choose {p-1}} \ \ \ \ \ (1)

Definition. {C(n,\epsilon)} is defined as the number of {\epsilon}-dense subsets of {[n]} with least cardinality.

We observe that this least cardinality has to be {k=\lceil \frac{n}{2\epsilon +1}\rceil}.

\displaystyle C(n,\epsilon)=\left \{ \begin{array}{ll} \sum_{x=0}^{2\epsilon}f(x,2,\epsilon)\cdot f(n-k-x,k-1,2\epsilon) & \text{ if }k\ge 2\\ \left. \begin{array}{ll} n & \text{ if } \epsilon \ge n-1\\ \left. \begin{array}{ll} 2\epsilon +2-n & \text{ if }2\epsilon +2-n\ge 1\\ 1 & \text{ if }2\epsilon +2-n\le 1 \end{array} \right \} \text{if }\epsilon <n-1 \end{array} \right \} \text{if }k=1 \end{array} \right. \ \ \ \ \ (2)

2. The open problem

The following matrix shows the {C(n,\epsilon)} values with {1\le n\le 15, 1\le \epsilon \le 15}.

\bigskip

{\left( \begin{array}{ccccccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 1 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 4 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 3 & 1 & 3 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 1 & 9 & 2 & 4 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \\ 8 & 8 & 1 & 3 & 5 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ 4 & 6 & 16 & 2 & 4 & 6 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 \\ 1 & 3 & 15 & 1 & 3 & 5 & 7 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 \\ 13 & 1 & 13 & 25 & 2 & 4 & 6 & 8 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 5 & 27 & 10 & 24 & 1 & 3 & 5 & 7 & 9 & 11 & 11 & 11 & 11 & 11 & 11 \\ 1 & 18 & 6 & 22 & 36 & 2 & 4 & 6 & 8 & 10 & 12 & 12 & 12 & 12 & 12 \\ 19 & 10 & 3 & 19 & 35 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 13 & 13 & 13 \\ 6 & 4 & 1 & 15 & 33 & 49 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 14 & 14 \\ 1 & 1 & 64 & 10 & 30 & 48 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 15 \end{array} \right)}

Can we arrive at the values and the values of {\epsilon}‘s where the function maximizes?

(I will write more soon 🙂 )

ಕಾವೇರಿ

…ಒಮ್ಮೊಮ್ಮೆ ಘಟನೆಗಳು ಯಾವ ಶರವೇಗದಲ್ಲಿ ನಡೆದುಹೋಗ್ತಾವಂದ್ರೆ, ನಂತರ ಮೆಲುಕು ಹಾಕಬೇಕಷ್ಟೆ. ಆ ಸನ್ನಿವೇಷ ನಮ್ಮ ಕೈಮೀರಿ ಹತೋಟಿಯನ್ನ ತಪ್ತವೆ (ಹತೋಟಿ ಇದೆ ಅಥ್ವಾ ಇರತ್ತೆ ಅಂದುಕೊಂಡ್ರೆ ತಪ್ಪಾಗತ್ತೆ ಅನ್ನೋದು ಸಂಪೂರ್ಣ ವೈರಾಗ್ಯದ್ ಮಾತು)…
ಇತ್ತೀಚೆಗೆ ಅಂದ್ರೆ ಸುಮಾರು ಎರಡು ತಿಂಗಳ (ಸ್ವಲ್ಪ ಹೆಚ್ಚೆ ಇರ್ಬಹುದು)ಹಿಂದೆ ಶ್ರೀ ರಂಗಕ್ಕೆ (ಶ್ರೀ ರಂಗಂ, ತಮಿಳುನಾಡು) ಹೋಗಿದ್ದೆ. ನನ್ನದನ್ನ ಉಳುಸ್ಕೋಬೇಕು ಅಂತ … ಪಕ್ಷಿ ಹಾರಿತ್ತು, ಕಾಲ ಮಿಂಚಿತ್ತು... ನಿಜವಾಗ್ಯೂ ನನ್ನದೇನೂ ಇರ್ಲಿಲ್ಲ ಅಂತ ನನ್ನ ಕುಶಾಗ್ರ ಬುದ್ಧಿಗೆ ತೀರಾ ಲೇಟಗ್ ಹೊಳೀತು ಅನ್ನಿ, ಆಗ ಮಾತ್ರ ಮನಸ್ಸಿನೊಳಗೆ ರುದ್ರತಾಂಡವ. ನಾನ್ ಮಾತ್ರ ಹುಚ್ಚ ಆಗಿದ್ದೆ. ಈಗ ಇಲ್ಲದ ಸತ್ಯದ್ ಬಗ್ಗೆ ತಿಳ್ದಿದೆ, ಸಾಯೋ ಹುಮ್ಮಸ್ಸು ಬರ್ಲಿಲ್ಲ, ಬದುಕಿದ್ದೀನಿ.

ಆ ವಿಚಾರ ಇಲ್ಲಿಗ್ ಬಿಡೋಣ, ಸಮ್ಯ ಬಂದಾಗ ಎದೆ ಬಿರಿಯತ್ತೆ, ಮಾತು ಚೆಲ್ತವೆ.

ಆ ಸಮಯದಲ್ಲಾದ ಒಂದು ವಿಲಕ್ಷಣ ಘಟನೆ ಬಗ್ಗೆ ಹೇಳ್ತೀನಿ – ಶ್ರೀ ರಂಗನ ವಿಶಾಲ (ನಮ್ ದೇವಸ್ಥಾನಗಳ್ ಥರ ಅಲ್ಲ, ಭಾಳ್ ದೊಡ್ದಿರ್ತವ, ಒಂದ್ ಸಣ್ ಉರೇ ಅನ್ಬಹುದು) ಪ್ರಾಂಗಣವನ್ನೆಲ್ಲಾ ಸುತ್ತಿ ಬಂದಾಗ ಸುಮಾರು ಏಳಾಗಿರ್ಬೇಕು ಅನ್ನಿಸತ್ತೆ, ಸ್ವಲ್ಪ ಇನ್ನೂ ಕಮ್ಮಿ ಇರ್ಬಹುದು. ಮುರೂವರೇಗೇ ಎದ್ದಿದ್ರಿಂದ ಹಶ್ವೆ ಭಾಳ ಆಗ್ತಿತ್ತು, ಹೊರಗೆ ಇದ್ದ ಹೊಟ್ಲುಗಳಲ್ಲಿ ತಿನ್ನೋಕೇಕೋ ಮನಸ್ಸಾಗ್ಲಿಲ್ಲ. ಮನಸ್ಸು ಯಾರ್ಗಾಗಿಯೋ ಚಡಪಡಿಸ್ತಿತ್ತು. ದೊಡ್ಡ ಗರುಡನ (ಗರುಡಾಳ್ವರ್ – ಇವನು ಯಾರ ದೇವ್ರೋ ಗೊತ್ತಿಲ್ಲ, ಆರ್ಯನೋ,ದ್ರಾವಿಡನೋ? ಆಳ್ವರಲ್ಲಿ ಏಕೆ ಒಬ್ಬನಾದನೋ … ಯಾವುದೋ ಒಳಜಗಳದ ಬಲಿಪಶು ಇರ್ಬಹುದು) ಗಾತ್ರಾನ ಮೆಚ್ಚ್ತಾ ಒಡಾಡ್ತಿದ್ದೆ. ಪ್ರಸಾದದ ಕೌನ್ಟ್ರು ತೆಗೀತು ಅಂತ ಕಾಣತ್ತೆ, ನನ್ನಂತೆಯೇ ಹಸಿದವರು ಮುಗಿ ಬಿದ್ದು ಅದು ಇದು ತೊಗೊಳ್ತಿದ್ರು.ಪುಳಿಯೋಗ್ರೆ, ಮೊಸರನ್ನ ಮತ್ತು ಸೀ ಪೊಂಗಲ್ ಇದ್ವು. ಎರಡು ಬಿಲ್ಲೆ ಕೊಂಡು, ಸಾಲಿನಲ್ಲಿ ನಿಂತಿದ್ದಾಗ ಆಕೆಯ ಕಂಡಿದ್ದು. ಸುಮರು ಅರವತ್ತು ದಾಟಿರ್ಬಹ್ದು, ಕಣ್ಣಲ್ ತೇಜಸ್ಸಿರ್ಲಿಲ್ಲ, ಸೋತ ಅಥವ ಹತಾಶೆ ಇದ್ದಂತೆ ಕಂಡುಬಂತು. ವಿಚಿತ್ರವಾದ ರೀತಿಯಲ್ಲಿ ಕೈ ನೀಡಿಕೊಂಡು, ಮುಖಭಾವದಲ್ಲಿ ಜಡತ್ವದಿಂದ ಕೂಡಿದ ದೈನ್ಯ, ಯಾರದ್ರೂ ಒಂದು ಎಲೇನ ತಂದು ಕೈಲಿಡೀ ಅನ್ನೋಂತಿತ್ತು. ಜೊತೆಯಲ್ಲೊಂದು ಸಣ್ಣ ಬ್ಯಾಗು, ಪ್ರಯಾಣದ ಅಯಾಸ ಇರ್ಬಹುದು. ಎಲೇಲಿ ಪುಳಿಯೋಗ್ರೆ ಹಾಕಿಸ್ಕೊಂಡು ನೇರ ಆಕೆ ಹತ್ರ ನಡೆದೆ. ಆಕೆಯ ಗಮನವೆಲ್ಲಾ ಎಲೆಯನ್ನ ನನ್ನ ಕೈಯಿಂದ ತನ್ನ ಕೈಗೆ ತೆಗೆದುಕೊಳುವುದರಲ್ಲಿತ್ತು, ಮರುಕ್ಷಣ ಗಮನವೆಲ್ಲ ಆಹಾರದ ಮೇಲೆ.

ನಾನ್ಯಾವುದೇ ಕೃತಜ್ನತೆಯನ್ನ ನಿರೀಕ್ಷಿಸಿರ್ಲಿಲ್ಲ, ಇನ್ನೊಂದು ಬಿಲ್ಲೆ ಹಿಡ್ದು ಸಾಲಿನಲ್ಲಿ ನಿಂತೆ. ಏನೋ (ನೆನಪಾಗ್ತಿಲ್ಲ) ತೆಗೆದುಕೊಂಡು ಆಕೆಗಿಂತ ಅನತಿ ದೂರದಲ್ಲಿ ಒಬ್ಬನೇ ಕುಳಿತೆ. ಇತರ ಭಕ್ತರೆಲ್ಲರೂ ತಮ್ಮ ಗುಂಪುಗಳಲ್ಲಿ ಮಾತು ಮತ್ತು ಹೊಟ್ಟೆಯ ನಡುವೆ ಹಂಚಿಹೋಗಿದ್ದರು. ಆನೆಯೊಂದು ಬಾಲವಲ್ಲಾಡಿಸುತ್ತಾ, ದುಡ್ಡು ಕೊಟ್ಟವರಿಗೆ ಆಶೀರ್ವದಿಸುತ್ತಿತ್ತು, ಅಥವ ನಮಗೆ ಹಾಗೆ ಭಾಸವಾಗುತ್ತೋ …

… ನನ್ನ ಪರಿಸ್ಥಿತಿ ಆಕೆಯದ್ದಕ್ಕಿಂತ ಭಿನ್ನವಾಗಿರ್ಲಿಲ್ಲ. ನನ್ನದೇನನ್ನ ಉಳಿಸಿಕೊಳ್ಳೋಕೆ ಬಂದಿದ್ನೋ, ಅದು ಮತ್ತೊಂದು ದೃಷ್ಟಿಯಿಂದ ಕೃಪೆ ಅಥ್ವ ಭಿಕ್ಷೆ ಆಗಿತ್ತು. ಒಮ್ಮೆ ನಾನು ಕಿರಿದಾಗುತ್ತಾ, ಪ್ರಾಂಗಣದ ಕಲ್ಲಿನ ಮೇಲ್ಛಾವಣಿ ಅತಿ ಎತ್ತರದಲ್ಲಿದ್ದಂತೆ ಅನ್ನಿಸ್ತು. ಹತೋಟಿ ಇರ್ಲಿಲ್ಲ ಅನ್ನೋ ಖಿನ್ನ ಮಂದಹಾಸ ಮೂಡ್ತು. ಕೆಲವೇ ಗಂಟೆಗಳೊಳಗೆ ಜೀವನಸಂಗಾತಿ ಅಂತ ಭಾವಿಸಿದ್ದ ಹೆಣದ ದರ್ಶನಭಾಗ್ಯ ನನ್ನ ಹಣೇಲಿ ಬರ್ದಿತ್ತು. ಖಡಾಖಂಡಿತ ನಿರ್ಧಾರ ಇಲ್ದೆ, ಪರಿಸ್ಥಿತಿ ಸುಳಿಗಾಳಿಗ್ ಸಿಕ್ಕು ಹುಟ್ಟಲಾರದ ಕೂಸೊಂದು ಸತ್ತು ಹೋಯ್ತು. ನನ್ನ ಭಾಗವನ್ನ ಎನೋ ಒಂದು ಕಸಿದು ಅಮೇರಿಕಾಕ್ಕೆ ವಿಮಾನವೇರಿ ಹೋಯ್ತು…

ಆಕೆ ನನ್ನ ಕಡೆ ಅಗಾಗ ನೋಡುತ್ತ, ನಮ್ಮ ಕಣ್ ಸಂಧಿಸುವುದನ್ನು  ಪ್ರಜ್ನಾಪೂರ್ವಕವಾಗಿ ತಪ್ಪಿಸುವಂತಿತ್ತು. ನಾನು ಮುಗಿಸಿದ ಬಳಿಕ, ಆಕೆಗೆ ಮೊಸರನ್ನ ತಂದುಕೊಟ್ಟೆ. ಮತ್ತದೇ ಭಾವ. ನಾನು ಮತ್ತೊಂದು ಬಿಲ್ಲೆ ತೆಗೆದುಕೊಂಡು, ಮತ್ತೇನನ್ನೋ ತೆಗೆದುಕೊಂಡೆ. ಆಕೆ ಹೊಟ್ಟೆ ತುಂಬಿ ಎದ್ದು ಹೋಗಬಹುದುದಿತ್ತು ಅಥವ ನನ್ನನ್ನು ಒಮ್ಮೆ ಕಂಡು ಏನಾದ್ರೂ ಮಾತಾಡಿ ಹೋಗ್ಬಹುದಿತ್ತು (ಆಕೆ ತಮಿಳಿನಲ್ಲಿ ಏನಾದ್ರೂ ಹೇಳಿದ್ರೆ, ಹಾ ಹೂ ಬಿಟ್ಟು ಹೆಚ್ಚೇನೂ ಹೇಳಲಾರದೆ ಹೋಗ್ತಿದ್ನೇನೊ). ನಾನೇನೂ ಎಕ್ಸ್ಪೆಕ್ಟ್ ಮಾಡಿರ್ಲಿಲ್ಲ.

…ಮನಸ್ಸಿಗೆ ಬಂತು, ಮಾಡ್ದೆ, ಏನೂ ನಿರೀಕ್ಷೆ ಇರ್ಲಿಲ್ಲ … ಮುಗೀತು, ನನ್ನಾ ಆಕೇ ಋಣಾನುಬಂಧ…

ಎರಡೂ ಅಗ್ಲಿಲ್ಲ, ಆಕೆ ನನ್ ಹತ್ರ ಬಂದು,’ನೀವ್ ತಿಂದು ಮುಗ್ಸೀದ್ ಮೇಲೆ ಐದ್ ರುಪಾಯ್ ಕೊಡ್ರಿ, ಟೀ ಕುಡೀಬೇಕು’.
ಆಫ್.

ತಕ್ಷಣ ಇಹಲೋಕದ ಶಾಕ್.

…ಗೆರೆ ದಾಟಿಯಾಗಿತ್ತು. ನನ್ನ ಹುಚ್ಚು ಕುರುಡು ನಂಬಿಕೆ, ವಿಶ್ವಾಸಗಳು ನನ್ನನ ನಗ್ನಸತ್ಯದ ಕ್ಷುಲ್ಲಕತನದ ಅಂಚಿನವರಗೆ ತಂದಿದ್ವು …

ನಾನೇನೂ ಕೊಡ್ಲಿಲ್ಲ. ರಂಗನಾಥನ ವಿಚಿತ್ರ ನ್ಯಾಯ ಅವ್ನಿಗೇ ತಿಳೀಬೇಕು. ಸಾವರಿಸಿಕೊಂಡು ಹೊರಟೆ. ಎಂದಿನಂತೆ ಕಾವೇರಿ ತಾಯಿ ಹರೀತಿದ್ದಾಳೆ, ಕಂಡರಿಯದ ಸಾವಿರಾರು ಭಗ್ನಸತ್ಯಗಳಿಗೆ ಸಾಕ್ಷಿಯಾಗಿ…

೧೪ ಮಾರ್ಚ್,೨೦೧೦, ಸಮಯ:೧.೨೭

Another elementary enumeration

Let \varphi(n);n\in \mathbb{N} denote the number of integers 1\le k\le n such that (k,n)=1 (Euler’s Phi Function). I read a proof of the following fact about the function proved using group theory; indicating the power ofgroup theory in enumerative combinatorics.

\displaystyle\sum_{d|n}\varphi(d)=n

Direct Proof: We shall assume that the reader is aware of the fact that \varphi is multiplicative that is \varphi(p_1^{\alpha_1} \dots p_k^{\alpha_k})=\varphi(p_1^{\alpha_1})\dots \varphi(p_k^{\alpha_k}). We know that \varphi(p^k)=p^k-p^{k-1}. Let m=p^k, then

\displaystyle\sum_{d|m}\varphi(d)=1+\sum_{t=1}^{k}p^t-p^{t-1}=p^k

Considering the general case where n=p_1^{\alpha_1}\dots p_k^{\alpha_k},

\displaystyle \sum_{d|n}\varphi(d)=\sum_{d|n}\varphi\left( p_1^{\beta_1}\dots p_k^{\beta_n} \right) for every \beta_i\le \alpha_i;1\le i \le k.

\displaystyle \sum_{d|n}\varphi(n)=\sum_{\beta_1=0}^{\alpha_1} \dots\sum_{\beta_n=0}^{\alpha_n}\varphi(p_1^{\beta_1}) \dots \varphi(p_n^{\beta_n})

\displaystyle\sum_{d|n}\varphi(n)=\prod_{i=1}^{k}\sum_{\beta_i=0}^{\alpha_i}\varphi(p_i^{\beta_i})=n

 

Here is a simpler looking group theoretic proof.

There are exactly \varphi(d) generators of the subgroup \mathbb{Z}_d where d is a divisor of n. Every element of \mathbb{Z}_n is a generator of exactly one subgroup of \mathbb{Z}_d.

An elementary counting argument

At first when I read about this problem from a certain Indonesian olympiad, I was puzzled as to how would one solve it. It was a pretty nice revelation of strength of proof methods after I solved it.

Find a closed form for \sum x_1x_2\dots x_k where x_1+x_2+\dots +x_k=n. The summmation runs over every possible non negative solution of the equation.

ಓದನ್ನು ಮುಂದುವರೆಸಿ